“二叉树深度”程序详细解释！！！

整个程序的意思就是如果是空二叉树，深度就是0

否则，就是左子树与右子树的最大深度加上1

如图就是左子树的B的深度与右子树C的深度相比较，其中的最大值加上A本身的高度1

二叉树的深度算法：

一、递归实现基本思想：

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

算法：

1 int FindTreeDeep(BinTree BT){

2 int deep=0

3 if(BT){

4 int lchilddeep=FindTreeDeep(BT->lchild)

5 int rchilddeep=FindTreeDeep(BT->rchild)

6 deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1

7 }

8 return deep

9 }

二、非递归实现基本思想：

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

算法的执行步骤如下：

（1）当树非空时，将指针p指向根节点，p为当前节点指针。

（2）将p压入栈S中，0压入栈tag中，并令p执行其左孩子。

（3）重复步骤（2），直到p为空。

（4）如果tag栈中的栈顶元素为1，跳至步骤（6）。从右子树返回

（5）如果tag栈中的栈顶元素为0，跳至步骤（7）。从左子树返回

（6）比较treedeep与栈的深度，取较大的赋给treedeep，对栈S和栈tag出栈 *** 作，p指向NULL，并跳至步骤（8）。

（7）将p指向栈S栈顶元素的右孩子，d出栈tag，并把1压入栈tag。（另外一种方法，直接修改栈tag栈顶的值为1也可以）

（8）循环（2）~（7），直到栈为空并且p为空

（9）返回treedeep，结束遍历

1 int TreeDeep(BinTree BT ){

2 int treedeep=0

3 stack S

4 stack tag

5 BinTree p=BT

6 while(p!=NULL||!isEmpty(S)){

7 while(p!=NULL){

8 push(S,p)

9 push(tag,0)

10 p=p->lchild

11 }

12 if(Top(tag)==1){

13 deeptree=deeptree>S.length?deeptree:S.length

14 pop(S)

15 pop(tag)

16 p=NULL

17 }else{

18 p=Top(S)

19 p=p->rchild

20 pop(tag)

21 push(tag,1)

22 }

23 }

24 return deeptree

25 }

从根节点到叶子结点一次经过的结点形成树的一条路径，最长路径的长度为树的深度。根节点的深度为1。

解体思路：

1.如果根节点为空，则深度为0，返回0，递归的出口。

2.如果根节点不为空，那么深度至少为1，然后我们求他们左右子树的深度，

3.比较左右子树深度值，返回较大的那一个

4.通过递归调用

#include<iostream>

#include<stdlib.h>

using namespace std

struct BinaryTreeNode

{

    int m_nValue

    BinaryTreeNode* m_pLeft

    BinaryTreeNode* m_pRight

}

//创建二叉树结点

BinaryTreeNode* CreateBinaryTreeNode(int value)

{

    BinaryTreeNode* pNode=new BinaryTreeNode()

    pNode->m_nValue=value

    pNode->m_pLeft=NULL

    pNode->m_pRight=NULL

    return pNode

}

//连接二叉树结点

void ConnectTreeNodes(BinaryTreeNode* pParent,BinaryTreeNode* pLeft,BinaryTreeNode* pRight)

{

    if(pParent!=NULL)

    {

        pParent->m_pLeft=pLeft

        pParent->m_pRight=pRight

    }

}

//求二叉树深度

int TreeDepth(BinaryTreeNode* pRoot)//计算二叉树深度

{

    if(pRoot==NULL)//如果pRoot为NULL，则深度为0，这也是递归的返回条件

        return 0

    //如果pRoot不为NULL，那么深度至少为1，所以left和right=1

    int left=1

    int right=1

    left+=TreeDepth(pRoot->m_pLeft)//求出左子树的深度

    right+=TreeDepth(pRoot->m_pRight)//求出右子树深度

    return left>right?left:right//返回深度较大的那一个

}

void main()

{

//            1

//         /      \

//        2        3

//       /\         \

//      4  5         6

//           /

//        7

    //创建树结点

    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1)

    BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2)

    BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3)

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4)

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5)

    BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6)

    BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7)

    //连接树结点

    ConnectTreeNodes(pNode1, pNode2, pNode3)

    ConnectTreeNodes(pNode2, pNode4, pNode5)

    ConnectTreeNodes(pNode3, NULL,   pNode6)

    ConnectTreeNodes(pNode5, pNode7,  NULL )

    int depth=TreeDepth(pNode1)

    cout<<depth<<endl

    system("pause")

}

出处：http://www.cnblogs.com/xwdreamer

---