Int Depth(BinTree *T)
{
int dep1,dep2
if(T==Null) return(0)
else
{
dep1=Depth(T->lchild)
dep2=Depth(T->rchild)
if(dep1>dep2) return(dep1+1)
else return(dep2+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
#include <iostream.h>typedef struct BiTNode
{
char data
int bit
struct BiTNode *lchild,*rchild,*parent
}BiTNode
void InitBT(BiTNode *&t)//1、初始化，不带头结点
{
t=NULL
}
/*void InitBT(BiTNode *t)//初始化，带头结点
{
t=new BiTNode
t->lchild=t->rchild=t->parent=NULL
}*/
int EmptyBT(BiTNode *t)//判断队空
{
if(t==0)
return 1
else
return 0
}
BiTNode *creatBT(BiTNode *t,int b)//2、创建二叉树
{
BiTNode *p
char ch
cin>>ch
if(ch=='#')return 0
else
{
p=new BiTNode
p->data=ch
p->parent=t
p->bit=b
t=p
t->lchild=creatBT(t,0)
t->rchild=creatBT(t,1)
}
return t
}
void preorder(BiTNode *t)//3、先序遍历
{
if(!EmptyBT(t))
{
cout<<t->data
preorder(t->lchild)
preorder(t->rchild)
}
}
void inorder(BiTNode *t)//中序遍历
{
if(!EmptyBT(t))
{
inorder(t->lchild)
cout<<t->data
inorder(t->rchild)
}
}
void postorder(BiTNode *t)//后序遍历
{
if(!EmptyBT(t))
{
postorder(t->lchild)
postorder(t->rchild)
cout<<t->data
}
}
void coutBT(BiTNode *t,int &m,int &n,int &i)//4、计算二叉树中叶子结点、度为2的结点和度为1的结点的个数
{
if(!EmptyBT(t))
{
if((t->lchild==0) &&(t->rchild==0))
m++//叶子结点
else if((t->lchild!=0) &&(t->rchild!=0))
i++//度为2的结点
else
n++//度为1的结点
coutBT(t->lchild,m,n,i)
coutBT(t->rchild,m,n,i)
}
}
void coutNode(BiTNode *t,int &k)//5、求二叉树中结点个数
{
if(!EmptyBT(t))
{
k++
coutNode(t->lchild,k)
coutNode(t->rchild,k)
}
}
int BTdepth(BiTNode *t)//6、求二叉树的深度
{
int i,j
if(EmptyBT(t))
return 0
else
{
i=BTdepth(t->lchild)
j=BTdepth(t->rchild)
return (i>j?i:j)+1
}
}
int Xdepth(BiTNode *t,char x)//7、查找x的层数
{
int num1,num2,n
if(t==NULL)
return 0
else{
if(t->data==x)
return 1
num1=Xdepth(t->lchild,x)
num2=Xdepth(t->rchild,x)
n=num1+num2
if(num1!=0||num2!=0)
n++
return n
}
}
static int flag
void SearchChild(BiTNode *t,int k)//8、查找第k个结点的左右孩子
{
if(!EmptyBT(t))
{
if(k==0)
{
cout<<"位置不能为0!"<<endl
return
}
else
{
flag++
if(flag==k)
{
if(t->lchild==0)
cout<<"无左孩子! "
else
cout<<"左孩子为："<<(t->lchild->data)<<" "
if(t->rchild==0)
cout<<"无右孩子!"<<endl
else
cout<<"右孩子为："<<(t->rchild->data)<<endl
}
else
{
SearchChild(t->lchild,k)
SearchChild(t->rchild,k)
}
}
}
}
int Xancestor(BiTNode *t,char x)//9、查找x结点祖先
{
int n,num1,num2
if(t==NULL)
return 0
else
{
if(t->data==x)
return 1
num1=Xancestor(t->lchild,x)
num2=Xancestor(t->rchild,x)
n=num1+num2
if(n!=0)
{
n++
cout<<t->data<<" "<<endl
}
}
}
void BTNodePath(BiTNode *t)//10、输出所有叶子结点路径
{
if(!EmptyBT(t))
{
if((t->lchild==0) &&(t->rchild==0))
{
cout<<t->data<<"的路径为："
for(BiTNode *p=tp!=0p=p->parent)
cout<<p->data
cout<<endl
}
else
{
BTNodePath(t->lchild)
BTNodePath(t->rchild)
}
}
}
void BTNodebit(BiTNode *t)//11、输出所有叶子结点编码
{
if(!EmptyBT(t))
{
if((t->lchild==0) &&(t->rchild==0))
{
cout<<t->data<<"的编码为："
for(BiTNode *p=tp->parent!=0p=p->parent)
cout<<p->bit
cout<<endl
}
else
{
BTNodebit(t->lchild)
BTNodebit(t->rchild)
}
}
}
void main()
{
BiTNode *t
int m,n,i,d,q,k
char x
cout<<"1、初始化..."<<endl
InitBT(t)
cout<<"2、创建二叉树..."<<endl
t=creatBT(t,0)
cout<<"3.1、先序遍历..."<<endl
preorder(t)
cout<<endl
cout<<"3.2、中序遍历..."<<endl
inorder(t)
cout<<endl
cout<<"3.3、后序遍历..."<<endl
postorder(t)
cout<<endl
m=n=i=0
cout<<"4、计算叶子结点，度为1的结点和度为2的结点的个数..."<<endl
coutBT(t,m,n,i)
cout<<"叶子结点个数为："<<m<<endl
cout<<"度为1的结点个数为："<<n<<endl
cout<<"度为2的结点个数为："<<i<<endl
q=0
cout<<"5、计算结点个数..."<<endl
coutNode(t,q)
cout<<"结点个数为："<<q<<endl
d=0
cout<<"6、计算深度..."<<endl
d=BTdepth(t)
cout<<"深度为："<<d<<endl
cout<<"7、求x的层数..."<<endl
cout<<"输入x："
cin>>x
if(Xdepth(t,x)==0)
cout<<"x不存在！"<<endl
else
cout<<Xdepth(t,x)<<endl
cout<<"8、输入要查找孩子的结点在先序遍历中的位置k（不等于0）："
cin>>k
SearchChild(t,k)
if(k>flag)
cout<<"位置超出长度!"<<endl
cout<<"9、查询结点的所有祖先，请输入结点x："
cin>>x
int num
num=Xancestor(t,x)
if(num==0)
cout<<"结点不存在！"<<endl
if(num==1)
cout<<"根结点无祖先！"<<endl
cout<<"10、输出所有叶子结点路径（叶→根）："<<endl
BTNodePath(t)
cout<<"11、输出所有叶子结点编码（叶→根）："<<endl
BTNodebit(t)
}
