th.jpg
非递归求深度有两种算法：1，现将算法改成先序遍历，在改写成非递归方式。先序遍历遍历是：遍历一个节点前，先算出当前节点在哪一层，层数最大就等于二叉树的深度。
typedef struct Node
{
char data;
struct Node* lchild;
struct Node* rchild;
struct Node* parent;
}BNode, *BTree;
int max(int a, int b)
{
return a>b?a:b;
}
int getDepthPreorder(BTree root)
{
struct Info
{
const BTree TreeNode;
int level;
};
deque<Info> dq;
int level = -1;
int TreeHeight = -1;
while(1)
{
while(root)
{
++level;
if(root->rchild)
{
Info info = {root->rchild, level};
dq.push_back(info);
}
root = root->lchild;
}
TreeHeight = max(TreeHeight, level);
if(dq.empty())
break;
const Info& info = dq.back();
root = info.TreeNode;
level = info.level;
dq.pop_back();
}
return TreeHeight;
}
