資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式語言
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時裝設計
法律C++ 程式查詢二叉樹中最深的左葉
一顆二叉樹至多有 2 個子節點，指定為左子節點和右子節點。這是一個 C++ 程式，用於查詢二叉樹中最深層的左葉。
演算法
Begin. function deepestLLeafutil() find the deepest left leaf in a given binary tree: lvel is level of current node. maxlvel is pointer to the deepest left leaf node found so far isLeft Indicates that this node is left child of its parent resPtr is Pointer to the result If root is equal to Null then Return. Update result if this node is having a left leaf and its level is more than the max level of the current result. Recursively call function deepestLLeafutil() for left and right subtrees. End.
程式碼示例
#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 << "The deepest left leaf is " << res->v;
else
cout << "There is no left leaf in the given tree";
return 0;
}輸出結果
The deepest left leaf is 6
更新時間：2019 年 7 月 30 日
瀏覽量：148
廣告