c語言二叉樹的深度
㈠ c語言 什麼叫完全二叉樹
完全二叉樹是一種特殊的二叉樹。
定義：如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1~n的結點一一對應，這棵二叉樹稱為完全二叉樹。
例：
特點：
葉子結點只可能在最大的兩層上出現,對任意結點，若基鏈差其右分支下的子孫最大層次為L，則其左搏皮分支下的子孫的最大層次必為L 或 L+1。
完全二叉樹第i層至多有2^（i-1）個節點，共i層的完全二叉樹最多有喚昌2^i-1個節點。
滿二叉樹：除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點的二叉樹。
㈡ 二叉樹的基本操作 C語言版的
#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=t;p!=0;p=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=t;p->parent!=0;p=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);
}
㈢ C語言 二叉樹深度，解釋一下
葉子節點就是度為0的結點，比度為2的結點多一個，即度2的沒有，這樣度為1的結點就是11個，故深度為12（1度就是結點連著1個子樹，二叉樹最多倆子樹，即左右子樹）
㈣ 怎麼計算C語言的二叉樹中的葉子節點數
結點的度是指，該結點的子樹的個數，在二叉樹中，不存在度大於2的結點。
計算公式：n0=n2+1
n0
是葉子節點的個數
n2
是度為2的結點的個數
n0=n2+1=5+1=6
故二叉樹有5個度為2的結點，則該二叉樹中的葉子結點數為6。
(4)c語言二叉樹的深度擴展閱讀
葉子結點是離散數學中的概念。一棵樹當中沒有子結點（即度為0）的結點稱為葉子結點，簡稱「葉子」。
葉子是指度為0的結點，又稱為終端結點。
葉子結點
就是度為0的結點
就是沒有子結點的結點。
n0：度為0的結點數，n1:度為1的結點
n2：度為2的結點數。
N是總結點
在二叉樹中：
n0=n2+1；
N=n0+n1+n2
參考資料：葉子結點_網路
㈤ C語言中，二叉樹的深度指怎樣計算
二叉樹中結點的最大層數稱為二叉樹的深度。計算：就是結點最大層數的個數，這還用計算，一看就知道。
㈥ c語言 深度怎麼算
二叉樹的遍歷，利用遞歸函數
int Depth(BiTree T){
int depthval,depthleft,depthright;
if(T == NULL) depthval = 0;
else{
depthleft = Depth(T -> lchild);
depthright = Depth(T -> rchild);
depthval = 1 + (depthleft > depthright ? depthleft : depthright);
}//else
return depthval;
}//Depth
㈦ 關於C語言計算二叉樹深度的問題
這里其實有個很有去的問題，上帝終於把自己搬起來模或虛了。
在c中函數可以自己調用自己遞歸，所以在deep的函數裡面還有deep。
在第一次運行後，rd+1（如果rd較大）被賦值給了deep，然後rd=deep，所以rd就被+1了，要是一直有next就一直做下去，知道最後，每次+1.
加的：比如從頭節點開始，第一個結點為A，最開始T為指向都結點的指針，然後在if（！t）中判斷，因為t不為NULL（在ASCII中的值為0）所以！t為假，所以運行else，ld和rd在初始化時為1，然後運行id=deep（t->lchild）=1和rd=deep（t->rchild）=1此時的t->lchild將被帶回到t中，下次運行時此處變為t->lchild->旦燃child，這樣樹就往下搜索了(或指向左邊團仔這個在後面的循環種可能出現)、然後判斷if（ld>rd）然後運行return ld+1這個值被返回到外面的int deep（TREE t）中然後第二次循環時rd=deep（TREE t）的值就是ld+1這樣就相當於count+1了再循環是將再判斷，再+1，就可以得到結果了
㈧ 用C語言寫一個計算二叉樹的高度
思想：對非空二叉樹，其深度等舉信於頌消左子樹的最大深度加1。
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);
}