【答案解析】计算二叉树的深度，一般都是用后序遍历，采用递归算法，先计算出左子树的深度，再算出右子树的深度，最后取较大者加1即为二叉树的深度。算法示例如下：
typedef struct Node
{
char data;
struct Node *LChild;
struct Node *RChild;
struct Node *Parent;
}BNode,*BTree;
∥后序遍历求二又树的深度递归算法
int PostTreeDepth(BTree root)
{
int leftheight,rightheight,max;
if(root!=NULL)
{
leftheight=PostTreeDepth(root-＞LChild);
rightheight=PostTreeDepth(root-＞RChild);
max=leftheight＞rightheight?leftheight:rightheight;
return(max+1);
}
else
retum 0;
}
但如果直接将该算法改成非递归形式是非常烦琐和复杂的。考虑到二叉树深度与深度的关系，可以有下面两种非递归算法实现求解二叉树深度。
方法一：先将算法改成先序遍历再改写非递归形式。先序遍历算法：遍历一个结点前，先算出当前结点是在哪一层，层数的最大值就等于二叉树的深度。算法示例如下：
typedef struct Node
{
char data;
struct Node*LChild;
struct Node *RChild;
struct Node *Parent;
}BNode,*BTree;
int GetMax(int a, int b)
return a＞b?a:b;
int GetTreeTreeHeightPreorder(const BTree root)
{
struct Info
{
const BTree TreeNode;
int leve1;
};
deque＜Info＞ dq;
int leve1=-1;
int TreeHeight=-1;
while(1)
{
while(root)
{
++leve1;
if (root-＞RChild)
{
Info info ={root-＞RChild, leve1};
dq.push_back(info);
}
root=root-＞LChild;
}
TreeHeight=GetMax (TreeHeight, leve1);
if (dq.empty())
break;
const Info& info = dq.back();
root = info.TreeNode;
leve1= info.leve1;
dq.pop_back();
}
retum TreeHeight;
}
方法二：修改上面提到的迭代算法。上例中，所用到辅助栈(或双端队列)的大小达到的最大值减去1就等于二叉树的深度。因而只需记录在往辅助栈放入元素后(或者在访问结点数据时)，辅助栈的栈大小达到的最大值。算法示例如下：
typedef struct Node
{
char data;
struct Node *LChild;
struct Node *RChild;
street Node *Parent;
}BNode,*BTree;
int GetMax(int a,int b)
{
return a＞b?a:b;
}
int GetTreeTreeHeightPostorder(const BTree root)
{
deque＜const BTree＞ dq;
int TreeHeight=-1;
while(1)
{
for (;root!=NULL;root=root-＞LChild)
dq.push_back(root);
TreeHeight=GetMax(TreeHeight,(int)dq.size()-1);
while (1)
{
if (dq.empty()) return TreeHeight;
const BTree parrent=dq.back();
const BTree RChild=parrent-＞RChild;
if (RChild && root!=RChild)
{
root=RChild;
break;
}
root=parrent;
dq.pop_back();
}
}
return TreeHeight;
}