C语言二叉树的深度指什么？怎么求？

Python012

C语言二叉树的深度指什么？怎么求？,第1张

从根节点到叶子结点一次经过的结点形成树的一条路径，最长路径的长度为树的深度。根节点的深度为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

从根节点到叶子节点的每一个分支中，最长分支的节点的总数。(深度)

比如:

某二叉树共有7个结点，其中叶子结点只有1个，只有一种可能，就是所以非叶子节点都只有一个分支。这样从根到叶要走7个节点。

http://zhidao.baidu.com/question/94976942.html?si=1

建议楼主到这里看看，其实每一层都是有一个return函数，不知道楼主注意到了没有，其次，reutrn函数初始返回0， 接着有 return (m>n?m:n)+1也就是一个一个一层一层加上去，所以会返回，而最后返回的就是答案