設計演算法後序遍歷求深度

❶ 求高手編寫一用層次遍歷求二叉樹深度的程序,謝謝

數據結構實驗------二叉樹操作2008-12-04 19:07按層次輸入，這樣可以根據實際需要建如瞎立樹毀飢型，更為實用。但我的程序仍存在一個問題，就是遍歷（2）：輸出為空的孩子時都會多輸出兩個空孩子。不知道怎麼改。

//二叉樹結點類型為字元型的情況
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define null 0
#define MaxSize 1024
typedef struct tree
{ /*聲明樹的結構*/
struct tree *left; /*存放左子樹的指針*/
struct tree *right; /*存放又子樹的指針*/
char data; /*存放節點的內容*/
} treenode, * b_tree; /*聲明二叉樹的鏈表*/

b_tree Q[MaxSize];

/*建立二叉樹，按完全二叉樹的層次遍歷序列輸入*/
b_tree createbtree()
{
char ch;
int front,rear;
b_tree root,s;
root=NULL;
front=1;rear=0;
ch=getchar();
getchar();
while(ch!='?')
{
s=NULL;
if(ch!='.')
{
s=(b_tree)malloc(sizeof(treenode));
s->data=ch;
s->left=NULL;
s->right=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else
{
if(s&&Q[front])
if(rear%2==0)
Q[front]->left=s;
else
Q[front]->right=s;
if(rear%2==1)
front++;
}
ch=getchar();
getchar();
}
return root;
}

/*先序遍歷列印二叉排序樹*/
void preorder_btree(b_tree root)
{
b_tree p=root;
if(p!=null)
{
printf("%3c",p->data);
preorder_btree(p->left);
preorder_btree(p->right);
}
}

/* 中序遍歷列印二叉排序樹*/
void inorder_btree(b_tree root)
{
b_tree p=root;
if(p!=null){
inorder_btree(p->left );
printf("%3c",p->data );
inorder_btree(p->right );
}
}

/*後序遍歷列印二叉排序樹*/
void postorder_btree(b_tree root)
{
b_tree p=root;
if(p!=null)
{
postorder_btree(p->left );
postorder_btree(p->right );
printf("%3c",p->data );
}
}

/*求樹的高度*/
int treedepth(b_tree bt)
{
int hl,hr,max;
if(bt!=null)
{
hl=treedepth(bt->left);
hr=treedepth(bt->right);
max=(hl>hr)?hl:hr;
return (max+1);
}
else
return 0;
}

int count=0;
/*求葉子結點總數*/
int leafcount(b_tree bt)
{
if(bt!=null)
{
leafcount(bt->left);
leafcount(bt->right);
if(bt->left==null&&bt->right==null)
count++;
}
return count;
}

void paintleaf(b_tree bt)
{
if(bt!=null)
{
if(bt->left==null&&bt->right==null)
printf("%3c"纖橡返,bt->data);
paintleaf(bt->left);
paintleaf(bt->right);
}
}

typedef b_tree ElemType ;

/*定義隊列結點類型*/
typedef struct QueueNode
{
ElemType data;
struct QueueNode *next;
} QueueNode;

/*定義隊列*/
typedef struct linkQueue
{
QueueNode * front;
QueueNode * rear;
}linkQueue;

/*初始化隊列*/
void initQueue(linkQueue * q)
{
q->front=q->rear =null; //----無頭結點
}

/*判斷隊列是否為空*/
int QueueEmpty(linkQueue * Q)
{
return (Q->front==null)&&(Q->rear==null);
/*實際上只須判斷隊頭指針是否為空即可*/
}

/*入隊操作*/
void EnQueue(linkQueue *Q,ElemType x)
{ /*將元素x插入鏈隊列尾部*/

QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode)); /*申請新結點*/
p->data=x; p->next=null;
if(QueueEmpty(Q)) /*將x插入空隊列*/ //----無頭結點
Q->front=Q->rear=p;
else
{ /*x插入非空隊列的尾*/
Q->rear->next=p; /*p鏈到原隊尾結點後*/
Q->rear=p; /*隊尾指針指向新的尾*/
}
}

/*出隊操作*/
ElemType DeQueue (linkQueue *Q)
{
ElemType x;
QueueNode *p;
if(QueueEmpty(Q))
{
printf("Queue underflow");/*下溢*/
exit(1) ;
}
p=Q->front; /*指向對頭結點*/
x=p->data; /*保存對頭結點的數據*/
Q->front=p->next; /*將對頭結點從鏈上摘下*/
if(Q->rear==p)/*原隊中只有一個結點，刪去後隊列變空，此時隊頭指針已為空*/
Q->rear=NULL;
free(p); /*釋放被刪隊頭結點*/
return x; /*返回原隊頭數據*/
}

void visit(b_tree p)
{
printf("%3c",p->data);
}

void breadthFirst2(b_tree root)
{
b_tree p,tmp;
linkQueue * q;
tmp=(treenode *)malloc(sizeof(treenode));
q=(linkQueue *)malloc(sizeof(linkQueue));
tmp->data='?';
initQueue(q);
p=root;
if(p!=null)
{
EnQueue(q,p);
while(!QueueEmpty(q))
{
p=DeQueue(q);
visit(p);
if(p->data!='?')
{
if(p->left!=null)
EnQueue(q,p->left);
else
EnQueue(q,tmp);
if(p->right!=null)
EnQueue(q,p->right);
else
EnQueue(q,tmp);
}
}
}
}

void breadthFirst(b_tree root)
{
b_tree p;
linkQueue * q;
q=(linkQueue *)malloc(sizeof(linkQueue));
initQueue(q);
p=root;
if(p!=null)
{
EnQueue(q,p);
while(!QueueEmpty(q))
{
p=DeQueue(q);
visit(p);
if(p->left!=null)
EnQueue(q,p->left);
if(p->right!=null)
EnQueue(q,p->right);
}
}
}

int main()
{
char nodelist[MaxSize];
int len,flag;
char cmd;
b_tree root;
printf("\n\n----------------------------------------------------\n");
printf("\n****歡迎測試和修正本程序！本程序用以研究二叉樹。****\n");
printf("\n----------------------------------------------------\n\n");
do
{
printf("\n\n 請選擇你要執行的操作:\n\n");
printf(" c,C......創建一棵二叉排序樹\n");
printf(" a,A......結束本程序\n\n");
flag=0;
do
{
if(flag!=0)
printf("選擇操作錯誤！請重新選擇！\n");
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A');
if(cmd=='c'||cmd=='C')
{
printf("請輸入那你所要創建的二叉樹的結點的值,以『？』結束）：\n");
getchar();
root=createbtree();
do
{
flag=0;
printf("\n\n 請選擇你要對這棵二叉樹所做的操作:\n\n");
printf(" x,X......先序遍歷這棵二叉樹\n");
printf(" z,Z......中序遍歷這棵二叉樹\n");
printf(" h,H......後序遍歷這棵二叉樹\n");
printf(" b,B......層次遍歷這棵二叉樹\n");
printf(" d,D......求這棵二叉樹的高度\n");
printf(" y,Y......求這棵二叉樹的葉子總數\n");
printf(" j,J......輸出這棵二叉樹的葉子結點\n");
printf(" q,Q......結束對這棵二叉樹的操作\n\n");
do
{
if(flag!=0)
printf("選擇操作錯誤！請重新選擇！\n");
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='x'&&cmd!='X'&&cmd!='z'&&cmd!='Z'&&cmd!='h'&&cmd!='H'&&cmd!='b'&&cmd!='B'&&cmd!='d'&&cmd!='D'&&cmd!='y'&&cmd!='Y'&&cmd!='j'&&cmd!='J'&&cmd!='q'&&cmd!='Q');
switch(cmd)
{
case 'x':
case 'X':
printf("\n先序遍歷開始:\n");
preorder_btree(root);
printf("\n先序遍歷結束\n\n");
break;
case 'z':
case 'Z':
printf("\n中序遍歷開始:\n");
inorder_btree(root);
printf("\n中序遍歷結束\n\n");
break;
case 'h':
case 'H':
printf("\n後序遍歷開始:\n");
postorder_btree(root);
printf("\n後序遍歷結束\n\n");
break;
case 'b':
case 'B':
printf("\n層次遍歷開始:\n");
printf("遍歷（1）：不輸出為空的孩子\n");
breadthFirst(root);
printf("\n");
printf("遍歷（2）：輸出為空的孩子\n");
breadthFirst2(root);
printf("\n層次遍歷結束\n\n");
break;
case 'd':
case 'D':
printf("\n這棵二叉樹的高度：\n%d\n\n",treedepth(root));
break;
case 'y':
case 'Y':
count=0;
count=leafcount(root);
printf("\n這棵二叉樹的葉子總數為:\n%d\n\n",count);
count=0;
break;
case 'j':
case 'J':
printf("\n這棵二叉樹的葉子結點為：\n");
paintleaf(root);
printf("\n");
break;
}
}while(cmd!='q'&&cmd!='Q');
}
}while(cmd!='a'&&cmd!='A');
printf("\n\n----------------------------\n\n");
printf("****謝謝使用！歡迎指正！****\n\n");
printf("----------------------------\n\n");
printf("作者：Remainder 學號：07082107 時間：2008.11.23\n\n\n\n");
return 0;
}

/*（10
（8 5 3 34 23 73 15 34 56 32）。。。。。。結點數據整型時
6
1 2 3 4 5 6
4
a b c d
*/

上面是我寫的程序，希望對你有用！
http://hi..com/yy_christine 我的網路空間

❷ 用遞歸演算法先序中序後序遍歷二叉樹

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

printf(「%d 」, BT->Data); //對節點做些訪問比如列印

PreOrderTraversal(BT->Left); //訪問左兒子

PreOrderTraversal(BT->Right); //訪問右兒子

}

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d ", BT->Data);

InOrderTraversal(BT->Right);

}

}

3、後序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d ", BT->Data);

}

}

(2)設計演算法後序遍歷求深度擴展閱讀：

注意事項

1、前序遍歷

從整棵二叉樹的根結點開始，對於任意結點VV，訪問結點VV並將結點VV入棧，並判斷結點VV的左子結點LL是否為空。若LL不為空，則將LL置為當前結點VV；若LL為空，則取出棧頂結點，並將棧頂結點的右子結點置為當前結點VV。

2、中序遍歷

從整棵二叉樹的根結點開始，對於任一結點VV，判斷其左子結點LL是否為空。若LL不為空，則將VV入棧並將L置為當前結點VV；若LL為空，則取出棧頂結點並訪問該棧頂結點，然後將其右子結點置為當前結點VV。重復上述操作，直到當前結點V為空結點且棧為空，遍歷結束。

3、後序遍歷

將整棵二叉樹的根結點入棧，取棧頂結點VV，若VV不存在左子結點和右子結點，或VV存在左子結點或右子結點，但其左子結點和右子結點都被訪問過了，則訪問結點VV，並將VV從棧中彈出。若非上述兩種情況，則將VV的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。

❸ 二叉樹的深度演算法怎麼算啊

二叉樹的深度演算法：
一、遞歸實現基本思想：
為了求得樹的深度，可以先求左右子樹的深度，取二者較大者加1即是樹的深度，遞歸返回的條件是若節點為空，返回0
演算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非遞歸實現基本思想：
受後續遍歷二叉樹思想的啟發，想到可以利用後續遍歷的方法來求二叉樹的深度，在每一次輸出的地方替換成算棧S的大小，遍歷結束後最大的棧S長度即是棧的深度。
演算法的執行步驟如下：
（1）當樹非空時，將指針p指向根節點，p為當前節點指針。
（2）將p壓入棧S中，0壓入棧tag中，並令p執行其左孩子。
（3）重復步驟（2），直到p為空。
（4）如果tag棧中的棧頂元素為1，跳至步驟（6）。從右子樹返回
（5）如果tag棧中的棧頂元素為0，跳至步驟（7）。從左子樹返回
（6）比較treedeep與棧的深度，取較大的賦給treedeep，對棧S和棧tag出棧操作，p指向NULL，並跳至步驟（8）。
（7）將p指向棧S棧頂元素的右孩子，彈出棧tag，並把1壓入棧tag。（另外一種方法，直接修改棧tag棧頂的值為1也可以）
（8）循環（2）~（7），直到棧為空並且p為空
（9）返回treedeep，結束遍歷
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}

❹ python演算法系列—深度優先遍歷演算法

一、什麼是深度優先遍歷
深度優先遍歷演算法是經典的圖論演算法。從某個節點v出發開始進行搜索。不斷搜索直到該節點所有的邊都被遍歷完，當節點v所有的邊都被遍歷完以後，深度優先遍歷演算法則需要回溯到v以前驅節點來繼續搜索這個節點。
注意：深度優先遍歷問題一定要按照規則嘗試所有的可能才行。

二、二叉樹

2.二叉樹類型
二叉樹類型：空二叉樹、滿二叉樹、完全二叉樹、完美二叉樹、平衡二叉樹。

空二叉樹：有零個節點
完美二叉樹：每一層節點都是滿的二叉樹（如1中舉例的圖）
滿二叉樹：每一個節點都有零個或者兩個子節點
完全二叉樹：出最後一層外，每一層節點都是滿的，並且最後一層節點全毀行歷部從左排列
平衡二叉樹：每個節點的兩個子樹的深度相差不超過1.

註：國內對完美二叉樹和滿二叉樹定義相同
3.二叉樹相關術語
術語 解釋
度 節點的度為節點的子樹個數
葉子節點 度為零的節點
分支節點 度不為零的節點
孩子節點 節點下的兩個子節點
雙親節點 節點上一層的源節點
兄弟節點 擁有同一雙親節點的節點
根 二叉樹的源頭節點
深度 二叉樹中節點的層的數量

DLR（先序）：
LDR（中序）：
LRD(後序）：
注意：L代表左子樹R代表右子樹；D代表根

6.深度優先遍歷和廣度優先遍歷
深度優先遍歷：前序、中序和後序都是深度優先遍歷
從根節點出發直奔最遠節點，
廣度優先遍歷：首先訪問舉例根節點最近的節纖搜點，按層次遞進，以廣度優先遍歷上圖的順序為：1-2-3-4-5-6-7
三、面試題+勵志
企鵝運維面試題：帶局
1.二叉樹遍歷順序：看上文
2.用你熟悉的語言說說怎麼創建二叉樹？ python看上文

❺ c語言 數據結構 求1、二叉樹的深度；2、求二叉子樹的深度 演算法！！！不勝感激~~~

//遞歸調用求樹的深度
int shen(tree *bt){ //tree是一個結構體 有一個數據域和兩個指針域（rchlib lchlib）
int h,h1,h2;
if(bt==NULL) //節點讓念為空節點 這說明這個節點是子節點
h=0;
else{
h1=shen(bt->洞殲rchlib);
h2=shen(bt->坦顫困lchlib);
h=(h1>h2?h1:h2)+1;
}
return h;
}

❻ 用遞歸的方法設計一個建立二叉樹並求其深度的演算法,求完整的。

先序遍歷求二叉樹高度int PreTreeDepth(BiTree root)
#define null 0
typedef struct node
{
elementtype data;
struct node *RChild,*LChild;
}BitNode,*BiTree;
int PreTreeDepth(BiTree root)
{/*先序遍歷求二叉樹高度，root為指向二叉樹根結點的指針*/
int lc,rc,max=0;
if(root==null)
return max;
lc=PreTreeDepth(root->LChild);
rc=PreTreeDepth(root->RChild);
max=lc>rc?lc:rc;
return max+1;
}
後序遍歷求二叉樹高度int PostTreeDepth(BiTree root)
#define null 0
typedef struct node
{
elementtype data;
struct node *RChild,*LChild;
}BitNode,*BiTree;
int PostTreeDepth(BiTree root)
{/*後序遍歷二叉樹，root為指向二叉樹（或某一子樹）根結點的指針*/
int max=0;
if(root!=null)
{
max=PostTreeDepth(root->LChild)+1;
if(max<=PostTreeDepth(root->RChild))
max=PostTreeDepth(root->RChild)+1;
}
return max;
}

❼ 先序遍歷和後序遍歷是什麼

1、先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。

首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。

例如，下圖所示二叉樹的遍歷結果是：ABDECF

（1）後序遍歷左子樹

（2）後序遍歷右子樹

（3）訪問根結點

如右圖所示二叉樹

後序遍歷結果：DEBFCA

已知前序遍歷和中序遍歷，就能確定後序遍歷。

(7)設計演算法後序遍歷求深度擴展閱讀：

圖的遍歷演算法主要有兩種，

一種是按照深度優先的順序展開遍歷的演算法，也就是深度優先遍歷；

另一種是按照寬度優先的順序展開遍歷的演算法，也就是寬度優先遍歷。寬度優先遍歷是沿著圖的深度遍歷圖的所有節點，每次遍歷都會沿著當前節點的鄰接點遍歷，直到所有點全部遍歷完成。

如果當前節點的所有鄰接點都遍歷過了，則回溯到上一個節點，重復這一過程一直到已訪問從源節點可達的所有節點為止。

如果還存在沒有被訪問的節點，則選擇其中一個節點作為源節點並重復以上過程，直到所有節點都被訪問為止。

利用圖的深度優先搜索可以獲得很多額外的信息，也可以解決很多圖論的問題。寬度優先遍歷又名廣度優先遍歷。通過沿著圖的寬度遍歷圖的節點，如果所有節點均被訪問，演算法隨即終止。寬度優先遍歷的實現一般需要一個隊列來輔助完成。

寬度優先遍歷和深度優先遍歷一樣也是一種盲目的遍歷方法。也就是說，寬度遍歷演算法並不使用經驗法則演算法， 並不考慮結果的可能地址，只是徹底地遍歷整張圖，直到找到結果為止。圖的遍歷問題分為四類：

1、遍歷完所有的邊而不能有重復，即所謂「歐拉路徑問題」（又名一筆畫問題）；

2、遍歷完所有的頂點而沒有重復，即所謂「哈密頓路徑問題」。

3、遍歷完所有的邊而可以有重復，即所謂「中國郵遞員問題」；

4、遍歷完所有的頂點而可以重復，即所謂「旅行推銷員問題」。

對於第一和第三類問題已經得到了完滿的解決，而第二和第四類問題則只得到了部分解決。第一類問題就是研究所謂的歐拉圖的性質，而第二類問題則是研究所謂的哈密頓圖的性質。

❽ 利用層序遍歷非遞歸地求解樹的深度

  求解樹的深度如果用遞歸的話那就很簡單，思想就是樹的深度等於左子樹深度+1和右子樹深度+1的最大值，這里不再贅述，但如果用非遞歸的話那就可以利用層序遍歷了，這個演算法是在王道的數據結構書上看到的。

接下來以這個圖為例解釋一寬閉氏下這個演算法。

下面我們來進慎散行循環：

進入循環前:front=-1,rear=0,level=0,last=0
第一次：front+1=0,rear+2=2,last=front=0,level+1=1,last=rear=2；A出隊態核，BC入隊。

第二次：front+1=1,rear+2=4,last=2!=front=1 ；本次B出隊，DE入隊。

第三次：front+1=2,rear=4,last=front=2,level+1=2,last=rear=4；本次C出隊。

第四次：front+1=3,rear+1=5,last=4!=front=3；本次D出隊，F入隊。

第五次：front+1=4,rear=5,last=front=4,level+1=3,last=rear=5；本次E出隊。

第六次：front+1=5,rear=5,last=front=5,level+1=4,last=rear=5；本次F出隊。

  循環中的關鍵就是這個if語句，if(front==last)其實就是問這層的所有節點有沒有都出隊，如果都出隊了，自然level+1，此時在進行last=rear操作前，rear-last的值其實就表示下一層的總節點數，因為此時該層的最後一個節點都出隊了，那說明下一層的所有節點都已經進入了隊中，rear-last(上一次循環的rear)就表示新進來的節點數即下一層的總節點數，所以要進行last=rear操作，使last指向該層的最後一個節點。循環結束時，樹的深度自然就求出了。

❾ 1、建立二叉樹，並進行先序、中序和後序遍歷。 2、求二叉樹的深度及葉子結點的個數。 3、構造哈夫曼樹及哈

0是初始節點數
輸入時請一次性輸完ABCффDEфGффFффф在按ENTER鍵 不要輸入一個按一下

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define Max 20 //結點的最大個數
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定義二叉樹的結點類型
typedef BinTNode *BinTree; //定義二叉樹的指針
int NodeNum,leaf; //NodeNum為結點數，leaf為葉子數
//==========基於先序遍歷演算法創建二叉樹==============
//=====要求輸入先序序列，其中加入虛結點"#"以示空指針的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())==' ')
return(NULL); //讀入#，返回空指針
else{
T=(BinTNode *)malloc(sizeof(BinTNode));//生成結點
T->data=ch;
T->lchild=CreatBinTree(); //構造左子樹
T->rchild=CreatBinTree(); //構造右子樹
return(T);
}
}
//========NLR 先序遍歷=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //訪問結點
Preorder(T->lchild); //先序遍歷左子樹
Preorder(T->rchild); //先序遍歷右子樹
}
}
//========LNR 中序遍歷===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍歷左子樹
printf("%c",T->data); //訪問結點
Inorder(T->rchild); //中序遍歷右子樹
}
}
//==========LRN 後序遍歷============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //後序遍歷左子樹
Postorder(T->rchild); //後序遍歷右子樹
printf("%c",T->data); //訪問結點
}
}
//=====採用後序遍歷求二叉樹的深度、結點數及葉子數的遞歸演算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求結點數
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度為0，即為葉子。
return(max+1);
}
else return(0);
}
//====利用"先進先出"（FIFO）隊列，按層次遍歷二叉樹==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定義結點的指針數組cq
cq[1]=T; //根入隊
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出隊
printf("%c",p->data); //出隊，輸出結點的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子樹入隊
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子樹入隊
}
}
}
//==========主函數=================
void main()
{
BinTree root;
int i,depth;
printf("NodeNum:%d\n",NodeNum);
printf("Creat Bin_Tree； Input preorder:"); //輸入完全二叉樹的先序序列，
// 用#代表虛結點，如ABD###CE##F##
root=CreatBinTree(); //創建二叉樹，返回根結點
do { //從菜單中選擇遍歷方式，輸入序號。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //先判斷節點數是否已有。不用再先選擇4，求出該樹的結點數。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //輸入菜單序號（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍歷
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍歷
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //後序遍歷
break;
case 4: depth=TreeDepth(root); //求樹的深度及葉子數
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5:
if(!NodeNum)
TreeDepth(root);
printf("LevePrint Bin_Tree: ");
Levelorder(root); //按層次遍歷
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}

❿ 用C實現二叉樹的建立，先序、中序、後序歷遍，深度演算法。緊急！！

#include<stdio.h>//頭文件

#include<stdlib.h>

#include<malloc.h>

typedefstructBiTNode

{

chardata;

structBiTNode*lchild,*rchild;

}

BiTNode,*BiTree;//定義結點類型

BiTreeCreateBiTree()//創建樹

{

charp;BiTreeT;

scanf("%c",&p);

if(p=='')

T=NULL;

else

{

T=(BiTNode*)malloc(sizeof(BiTNode));//為結點開辟空間

T->data=p;

T->lchild=CreateBiTree();

T->rchild=CreateBiTree();

}

return(T);

}

voidPreOrder(BiTreeT)//先序

{

if(T!=NULL)

{

printf("%c",T->data);

PreOrder(T->lchild);

PreOrder(T->rchild);

}

}

voidInOrder(BiTreeT)//中序

{

if(T!=NULL)

{

InOrder(T->lchild);

printf("%c",T->data);

InOrder(T->rchild);

}

}

voidPostOrder(BiTreeT)//後序

{

if(T!=NULL)

{

PostOrder(T->lchild);

PostOrder(T->rchild);

printf("%c",T->data);

}

}

intDepth(BiTree態頃T)/*深度*/

{

if(T==NULL)

return(0);

else

return1+(Depth(T->lchild)>Depth(T->rchild)?Depth(T->lchild):Depth(T->rchild));

}

voidmain()//主函數

{

BiTreeTa;

渣梁Ta=CreateBiTree();

printf("先序遍歷:");

printf(" ");

PreOrder(Ta);

printf(" ");

printf("中序遍歷:");

printf(" ");

InOrder(Ta);

printf(" "帆梁陸);

printf("後序遍歷:");

printf(" ");

PostOrder(Ta);

printf(" ");

printf("深度為：%d",Depth(Ta));

}

根據你給的樹，你輸入如下：

ABD**EG*J***C*FHK**L**IM***

（其中*代表空格，輸入時*代表空格）

有問題聯系！