二叉树的深度，递归和非递归实现

递归实现基本思想&＃xff1a;

为了求得树的深度&＃xff0c;可以先求左右子树的深度&＃xff0c;取二者较大者加1即是树的深度&＃xff0c;递归返回的条件是若节点为空&＃xff0c;返回0

算法&＃xff1a;

int FindTreeDeep(BinTree BT){int deep&＃61;0;if(BT){int lchilddeep&＃61;FindTreeDeep(BT->lchild);int rchilddeep&＃61;FindTreeDeep(BT->rchild);deep&＃61;lchilddeep>&＃61;rchilddeep?lchilddeep&＃43;1:rchilddeep&＃43;1;}return deep;
}

非递归实现基本思想&＃xff1a;

受后续遍历二叉树思想的启发&＃xff0c;想到可以利用后续遍历的方法来求二叉树的深度&＃xff0c;在每一次输出的地方替换成算栈S的大小&＃xff0c;遍历结束后最大的栈S长度即是栈的深度。

算法的执行步骤如下&＃xff1a;

&＃xff08;1&＃xff09;当树非空时&＃xff0c;将指针p指向根节点&＃xff0c;p为当前节点指针。

&＃xff08;2&＃xff09;将p压入栈S中&＃xff0c;0压入栈tag中&＃xff0c;并令p执行其左孩子。

&＃xff08;3&＃xff09;重复步骤&＃xff08;2&＃xff09;&＃xff0c;直到p为空。

&＃xff08;4&＃xff09;如果tag栈中的栈顶元素为1&＃xff0c;跳至步骤&＃xff08;6&＃xff09;。从右子树返回

&＃xff08;5&＃xff09;如果tag栈中的栈顶元素为0&＃xff0c;跳至步骤&＃xff08;7&＃xff09;。从左子树返回

&＃xff08;6&＃xff09;比较treedeep与栈的深度&＃xff0c;取较大的赋给treedeep&＃xff0c;对栈S和栈tag出栈操作&＃xff0c;p指向NULL&＃xff0c;并跳至步骤&＃xff08;8&＃xff09;。

&＃xff08;7&＃xff09;将p指向栈S栈顶元素的右孩子&＃xff0c;弹出栈tag&＃xff0c;并把1压入栈tag。&＃xff08;另外一种方法&＃xff0c;直接修改栈tag栈顶的值为1也可以&＃xff09;

&＃xff08;8&＃xff09;循环&＃xff08;2&＃xff09;~&＃xff08;7&＃xff09;&＃xff0c;直到栈为空并且p为空

&＃xff08;9&＃xff09;返回treedeep&＃xff0c;结束遍历

int TreeDeep(BinTree BT ){int treedeep&＃61;0;stack S;stack tag;BinTree p&＃61;BT;while(p!&＃61;NULL||!isEmpty(S)){while(p!&＃61;NULL){push(S,p);push(tag,0);p&＃61;p->lchild;}if(Top(tag)&＃61;&＃61;1){deeptree&＃61;deeptree>S.length?deeptree:S.length;pop(S);pop(tag);p&＃61;NULL;}else{p&＃61;Top(S);p&＃61;p->rchild;pop(tag);push(tag,1);}}return deeptree;
}