普通樹的深度遍歷c語言,樹的層次遍歷c語言

本文目錄一覽：

• 1、C語言用三種不同的方法遍歷二叉樹並用兩種方式排序
• 2、C語言創建二叉樹 遍歷 求深度 求解！！
• 3、C語言二叉樹的創建和遍歷
• 4、C語言二叉樹遍歷程序
• 5、C語言 樹的生成和遍歷

C語言用三種不同的方法遍歷二叉樹並用兩種方式排序

以下是我的數據結構實驗的作業：肯定好用，裏面還包括了統計樹的深度和葉子數！記住每次做完一個遍歷還要重新輸入你的樹哦！

#include “stdio.h”

#include “string.h”

#define NULL 0

typedef struct BiTNode{

char data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

BiTree Create(BiTree T){

char ch;

ch=getchar();

if(ch==’#’)

T=NULL;

else{

if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))

printf(“Error!”);

T-data=ch;

T-lchild=Create(T-lchild);

T-rchild=Create(T-rchild);

}

return T;

}

void Preorder(BiTree T){

if(T){

printf(“%c”,T-data);

Preorder(T-lchild);

Preorder(T-rchild);

}

}

int Sumleaf(BiTree T){

int sum=0,m,n;

if(T){

if((!T-lchild)(!T-rchild))

sum++;

m=Sumleaf(T-lchild);

sum+=m;

n=Sumleaf(T-rchild);

sum+=n;

}

return sum;

}

void zhongxu(BiTree T){

if(T){

zhongxu(T-lchild);

printf(“%c”,T-data);

zhongxu(T-rchild);

}

}

void houxu(BiTree T){

if(T){

houxu(T-lchild);

houxu(T-rchild);

printf(“%c”,T-data);

}

}

int Depth(BiTree T){

int dep=0,depl,depr;

if(!T) dep=0;

else{

depl=Depth(T-lchild);

depr=Depth(T-rchild);

dep=1+(depldepr?depl:depr);

}

return dep;

}

main(){

BiTree T;

int sum,dep;

T=Create(T);

Preorder(T);

printf(“\n”);

zhongxu(T);

printf(“\n”);

houxu(T);

printf(“\n”);

sum=Sumleaf(T);

printf(“%d”,sum);

dep=Depth(T);

printf(“\n%d”,dep);

}

在Turbo C的環境下，先按Ctrl+F9運行程序，此時就是建立二叉樹的過程，例如輸入序列ABC##DE#G##F###（其中的「#」表示空，並且輸入過程中不要加回車，因為回車也有對應的ASCII碼，是要算字符的，但是輸入完之後可以按回車退出），然後再按ALT+F5顯示用戶界面，這時候就能夠看到結果了。

另外你必須會手動建立一棵二叉樹，保證你輸入的序列能構成一棵二叉樹，否則你怎麼輸入，按最後按多少回車程序也不會結束！

C語言創建二叉樹 遍歷 求深度 求解！！

測試結果：

At the first,we create a tree

Please input nodes of tree

a

b

c

#

#

d

e

#

g

#

#

f

#

#

#

abcdegf

cbegdfa

cgefdba

The count of leaves is: 3

The height of tree is 5

請按任意鍵繼續. . .

【樓主】 建樹的函數是一個遞歸的過程

我上面測試的這顆樹

a

/

b

/ \

c d

/ \

e f

\

g

仔細看我的建樹的時候的輸入！

為了測試上面的5個函數，我把case去掉了。你補上去！

【你的CreateBinTree()】是沒有參數的，所以你後面的申明不能帶參數

測試代碼：

#includestdio.h

#includestdlib.h

typedef struct bnode{

char data;

struct bnode *lchild;

struct bnode *rchild;

}*BTree,Bnode;

BTree CreateBinTree()

{

char ch;

BTree t;

ch=getchar();

getchar();

if(ch==’#’)

t=NULL;

else

{

t=(BTree)malloc(sizeof(Bnode));

t-data=ch;

t-lchild=CreateBinTree();

t-rchild=CreateBinTree();

}

return t;

}

void PreOrder(BTree t)

{

if(t)

{

printf(“%c”,t-data);

PreOrder(t-lchild);

PreOrder(t-rchild);

}

}

void InOrder(BTree t)

{

if(t)

{

InOrder(t-lchild);

printf(“%c”,t-data);

InOrder(t-rchild);

}

}

void PostOrder(BTree t)

{

if(t)

{

PostOrder(t-lchild);

PostOrder(t-rchild);

printf(“%c”,t-data);

}

}

int Height(BTree t)

{

int h1,h2;

if(t==NULL)

return 0;

else

{

h1=Height(t-lchild);

h2=Height(t-rchild);

if(h1h2)

return h1+1;

else

return h2+1;

}

}

int LeafCount(BTree t)

{

int count1,count2;

if(t==NULL)

return 0;

else

{

if(t-lchild==NULLt-rchild==NULL)

return 1;

else

{

count1=LeafCount(t-lchild);

count2=LeafCount(t-rchild);

return count1+count2;

}

}

}

main()

{ BTree root;/*定義指向樹的指針*/

int t=1;

printf(“At the first,we create a tree\n”);

printf(“Please input nodes of tree\n”);

root=CreateBinTree();//調用函數創建樹

if (root==NULL) printf(“It’s an empty tree!\n”);

else

{

PreOrder(root); printf(“\n”);

InOrder(root); printf(“\n”);

PostOrder(root); printf(“\n”);

printf(“\nThe count of leaves is: %d \n”,LeafCount(root));

printf(“\nThe height of tree is %d \n”,Height(root));

system(“pause”);

}

}

C語言二叉樹的創建和遍歷

我寫了一個二叉樹 你給看看 一定能行的 我自己用了

#include “stdio.h”

#include “malloc.h”

#include “string.h”

#include “stdlib.h”

#define Max 20 //結點的最大個數

typedef struct BinTNode{

char data;

struct BinTNode *lchild,*rchild;

}BinTNode,*BinTree; //自定義二叉樹的結點類型

//定義二叉樹的指針

int NodeNum,leaf; //NodeNum為結點數，leaf為葉子數

//==========以廣義表顯示二叉樹==============

void DisTree(BinTree T)

{

if(T)

{

printf(“%c”,T-data);

if((T-lchild)||(T-rchild))

{

if(T-lchild)

{

printf(“%c”,'(‘);

DisTree(T-lchild);

}

if(T-rchild)

{

printf(“%c”,’,’);

DisTree(T-rchild);

printf(“%c”,’)’);

}

}

}

}

//==========基於先序遍歷算法創建二叉樹==============

//=====要求輸入先序序列，其中加入虛結點”#”以示空指針的位置==========

BinTree CreatBinTree(BinTree T)

{

char ch;

ch=getchar();

if(ch==’#’)

T=NULL;

else

{

if(!(T=(BinTNode *)malloc(sizeof(BinTNode))))

printf(“Error!”);

T-data=ch;

T-lchild=CreatBinTree(T-lchild);

T-rchild=CreatBinTree(T-rchild);

}

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=hlhr? hl:hr; //取左右深度的最大值

NodeNum=NodeNum+1; //求結點數

if(hl==0hr==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 T,root;

int i,depth;

printf(“\n”);

printf(“輸入完全二叉樹的先序序列:”); //輸入完全二叉樹的先序序列，

// 用#代表虛結點，如ABD###CE##F##

root=CreatBinTree(T); //創建二叉樹，返回根結點

DisTree(root);

printf(“\n”);

do //從菜單中選擇遍歷方式，輸入序號。

{

printf(“\t********** 菜單 ************\n”);

printf(“\n”);

printf(“\t1: 先序遍歷\n”);

printf(“\t2: 中序遍歷\n”);

printf(“\t3: 後序遍歷\n”);

printf(“\t4: 該樹的深度,結點數,葉子數\n”);

printf(“\t5: 層次遍歷\n”); //按層次遍歷之前，先選擇4，求出該樹的結點數。

printf(“\t0: 退出\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(“樹深=%d 樹總結點數=%d”,depth,NodeNum);

printf(” 樹葉子數=%d”,leaf);

}break;

case 5: {printf(“LevePrint Bin_Tree: “);

Levelorder(root); //按層次遍歷

}break;

default: exit(1);

}

}while(i=0i6);

}

兄弟你看看 不懂再往下留言 記得給我的勞動成果一點點獎勵哦！！

C語言二叉樹遍歷程序

先看下creat這個函數:

status creat(bitnode *t)/*先序建立二叉樹*/

{

char ch;

ch=getch();putch(ch);

if(ch==’0′) t=NULL;

else

{

t=(bitnode *)malloc(sizeof(bitnode));

if(!t)

exit(OVERFLOW);

t-data=ch;

creat(t-lchild);

creat(t-rchild);

}

return OK;

}

其中有句代碼是t=(bitnode *)malloc(sizeof(bitnode));

這是給t賦值，由於t是參數，這樣做是不能返回的。

我知道你的意思是想通過指針返回，但是那樣的用法應該是對t所指向的變量賦值，也就是對*t賦值。

如果你還沒理解的話看下函數里的遞歸調用：creat(t-lchild);調用函數後，本意是要給t-lchild賦值的，但是是做不到的，因為要改變一個變量的值的話，應該傳的是它的地址。

可能你覺得有點亂了，我舉個函數中用指針做參數來返回的例子：

假如要用指針返回一個整型的變量，那麼指針應該是指向整型變量的，即int*

這裡應該是要返回一個struct bitnode *類型的，也就是返回的值就是個指針，那麼參數就應該是一個指向這種指針的指針，即struct bitnode **

可以這麼修改：

status creat(bitnode **t) //多了個*

{

char ch;

ch=getch();putch(ch);

if(ch==’0′) *t=NULL; //多了個*

else

{

*t=(bitnode *)malloc(sizeof(bitnode)); //多了個*

if(!*t) //多了個*

exit(OVERFLOW);

(*t)-data=ch;

creat((*t)-lchild); //注意不同

creat((*t)-rchild);

}

return OK;

}

主函數這麼改

status main()

{

bitnode* t1; //多了個*

creat(t1);

pre(t1,print); //少了個

getch();

return 0;

}

另外一個編譯錯誤就是

int pre(bitnode *t,status (*visit)())

指針函數後面應該帶參數，改為

int pre(bitnode *t,status (*visit)(bitnode *))

C語言 樹的生成和遍歷

#include //頭文件

#include

typedef struct BiTNode

{

char data;

struct BiTNode *lchild,*rchild;

}

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

BiTree CreateBiTree()//創建樹

{

char p;BiTree T;

scanf(“%c”,p);

if(p==’ ‘)

T=NULL;

else

{

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

T-data=p;

T-lchild=CreateBiTree();

T-rchild=CreateBiTree();

}

return (T);

}

void PreOrder(BiTree T)//先序

{

if(T!=NULL)

{

printf(“%c”,T-data);

PreOrder(T-lchild);

PreOrder(T-rchild);

}

}

void InOrder(BiTree T)//中序

{

if(T!=NULL)

{

InOrder(T-lchild);

printf(“%c”,T-data);

InOrder(T-rchild);

}

}

void PostOrder(BiTree T)//後序

{

if(T!=NULL)

{

PostOrder(T-lchild);

PostOrder(T-rchild);

printf(“%c”,T-data);

}

}

void main()//主函數

{

BiTree Ta;

Ta=CreateBiTree();

printf(“先序遍歷:”);

printf(“\n”);

PreOrder(Ta);

printf(“\n”);

printf(“中序遍歷:”);

printf(“\n”);

InOrder(Ta);

printf(“\n”);

printf(“後序遍歷:”);

printf(“\n”);

PostOrder(Ta);

}

給你個簡單的例子：

AB***

其中*代表空格

複雜點的例子

ABC**DE*f**g***

其中*代表空格