本文目录一览：
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***
其中*代表空格
