二叉树的深度
文章目录
//查找二叉树的深度,也就是从根节点到叶子节点所有路径中,最长路径的节点数目
#include <iostream>
using namespace std;
struct BinaryTreeNode{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
//构建二叉树
BinaryTreeNode* ContrustCore(int* startpreorder,int* endpreorder,int* startinorder,int* endinorder){
//根据先序确定第一个数值确定根节点
//BinaryTreeNode *root;
int rootValue=startpreorder[0];
BinaryTreeNode* root=new BinaryTreeNode();//为链表申请空间
root->m_nValue=rootValue;
root->m_pLeft=root->m_pRight=NULL;
if(startpreorder==endpreorder){
if(startinorder==endinorder && *startpreorder==*endpreorder)//z只有一个根节点
return root;
else
throw std::exception();
}
//在中序找到根节点所在位置
int*rootinoder=startinorder;
while(rootinoder<=endinorder && *rootinoder!=rootValue)
rootinoder++;
if(rootinoder==endinorder && *rootinoder!=rootValue)//在中序中没有找到根节点
throw exception();
int leftLength=rootinoder-startinorder;
int* leftPreorderEnd=startpreorder+leftLength;
if(leftLength>0)//左子树的长度,构建左子树
{
root->m_pLeft=ContrustCore(startpreorder+1,leftPreorderEnd,startinorder,rootinoder-1);
}
if(leftLength<endpreorder-startpreorder)//存在右子树
root->m_pRight=ContrustCore(leftPreorderEnd+1,endpreorder,rootinoder+1,endinorder);
return root;
}
BinaryTreeNode* Contrust(int* preorder,int* inorder,int length){
if(preorder==NULL||inorder==NULL||length<=0)
return NULL;
return ContrustCore(preorder,preorder+length-1,inorder,inorder+length-1);
}
//二叉树的深度:如果树只有一个节点,那么树的深度就是1;如果没有右子树,
//那么就等于左子树的深度+1;没有左子树的情况类似;如果左右子树都存在,那么就等于两个子树路径较大的那个+1
int TreeDepth(BinaryTreeNode* pRoot){
if(!pRoot)
return 0;
// if(!pRoot->m_pLeft && !pRoot->m_pRight)//不需要
// return 1;
//else{
int nLeft=TreeDepth(pRoot->m_pLeft);
int nRight=TreeDepth(pRoot->m_pRight);
return (nLeft>nRight)?(nLeft+1):(nRight+1);
// }
}
int main()
{
BinaryTreeNode* Btree;
int preorder[]={10,5,4,7,12};
int inorder[]={4,5,7,10,12};
Btree= Contrust(preorder,inorder,5);
cout<<TreeDepth(Btree);
return 0;
}