普通树的深度遍历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***

其中*代表空格