Chương trình C++ tìm lá trái sâu nhất trong cây nhị phân

Cây nhị phân là cây có tối đa hai con, chỉ định là con trái và con phải. Đây là chương trình C++ tìm lá trái sâu nhất (Deepest Left Leaf) trong cây nhị phân.

Thuật toán

Bắt đầu.
  Hàm deepestLLeafutil() tìm lá trái sâu nhất trong cây nhị phân:
    lvel là level của nút hiện tại.
    maxlvel con trỏ đến nút lá trái sâu nhất tìm được.
    isLeft chỉ ra nút này là con trái của cha.
    resPtr con trỏ kết quả.
    Nếu root == NULL thì Return.
    Cập nhật kết quả nếu nút này là lá trái và level > max level hiện tại.
    Gọi đệ quy deepestLLeafutil() cho cây con trái và phải.
Kết thúc.

Mã ví dụ

#include <iostream>
using namespace std;

struct n {
    int v;
    n *l, *r;
};

void deepestLLeafutil(n *root, int lvel, int *maxvel, bool isLeft, n **resPtr) {
    if (root == NULL)
        return;
    if (isLeft && !root->l && !root->r && lvel > *maxvel) {
        *resPtr = root;
        *maxvel = lvel;
        return;
    }
    deepestLLeafutil(root->l, lvel + 1, maxvel, true, resPtr);
    deepestLLeafutil(root->r, lvel + 1, maxvel, false, resPtr);
}

n* deepestLLeaf(n *root) {
    int maxlevel = 0;
    n *res = NULL;
    deepestLLeafutil(root, 0, &maxlevel, false, &res);
    return res;
}

n *newnode(int d) {
    n *t = new n;
    t->v = d;
    t->l = t->r = NULL;
    return t;
}

int main() {
    n* root = newnode(9);
    root->l = newnode(7);
    root->r = newnode(10);
    root->l->l = newnode(6);
    root->r->l = newnode(8);
    root->r->r = newnode(19);
    root->r->l->r = newnode(4);
    root->r->r->r = newnode(20);
    n *res = deepestLLeaf(root);
    if (res)
        cout << "Lá trái sâu nhất là " << res->v;
    else
        cout << "Không có lá trái trong cây đã cho";
    return 0;
}

Kết quả

Lá trái sâu nhất là 6