從根節點到葉子結點壹次經過的結點形成樹的壹條路徑,最長路徑的長度為樹的深度。根節點的深度為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
//?/?\
//23
///\?\
//?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");
}
出處:blogs.com/xwdreamer