汉扬编程 C语言入门 求这个二叉树的前中后遍历

求这个二叉树的前中后遍历

  这里的“先根”也叫做先序,“中”和“后”也一样。
先序遍历是先访问当前节点,然后再遍历左子树,最后是右子树。
中序遍历是先遍历左子树,再访问当前节点,最后是右子树。
后序遍历是先遍历左子树,再遍历右子树,最后访问当前节点。
  
例:
一棵二叉树的先根遍历为ABCDEFG,中根遍历为CBDEAGF,则其后根遍历为

1、先序遍历的第一个当前节点一定是根节点,所以A是根
2、由于中序遍历是先遍历完左子树再访问当前节点,所以可以看出中序序列在A之前的都是A的左子树中的节点,而在A之后是A的右子树的节点。
  
3、这样就分成了(cbde)a (GF),三个集合。
4、我们分别再看各个集合。cbde集合中最先在先序序列中出现的是B,这说明b在这个集合中应该是第一个出现的。所以右可以再分
********a
**b********(gf)
c**(de)
5、再看de,在先序序列中因为D在E前方,所以D肯定是E的父节点,现在剩下的就是判断E是D的左孩子还是右孩子。
  从中序序列中看,D仍然是在E的前方,说明E是D的右孩子。
********a
**b********(gf)
c***d
******e
6、最后剩下gf。
  和DE相似的判断方法,在先序序列中F在G前方,说明F是父节点,而在中序当中G在F前方,说明G是F的左孩子。
所以这颗二叉树应该是
********a
**b********f
c***d*****g
******e
7、二叉树出来了,后序的原理最上方讲了,剩下的就好办了。
  先左孩子,然后右孩子,最后当前节点。
8、当前节点为A时由于左右两个子树还没有访问所以要先访问完左右子树才能访问A。
9、b同A
10、c没有左右孩子,所以它是第一个。
11、c访问完了在访问b的右子树。
  
12、先访问d的孩子e,然后再是D。
13、b的左右孩子都访问完了,所以下一个是B。
14、访问完B,A的左子树访问完了,但是还是不能访问A,因为A的右子树还没有访问。
15、A的右子树中,G是F的孩子,所以先G再F。
  
16、最后是根节点A。

如何用队列层序遍历二叉树?

  #include
#include
#define m 100
typedef char etype;
typedef struct bitnode
{
etype data;
struct bitnode *lch,*rch;
}bitnode,*bitree;
bitree que[m];
int front=0,rear=0;
bitnode *creat_bt1();
bitnode *creat_bt2();
void preorder(bitnode *p);
void inorder(bitnode *p);
void postorder(bitnode *p);
void enqueue(bitree);
bitree delqueue();
void levorder(bitree);
int treedepth(bitree);
void prtbtree(bitree,int);
void exchange(bitree);
int leafcount(bitree);
void paintleaf(bitree);
bitnode *t;
int count=0;
void main()
{
char ch;int k;
do{
printf(\”

\”);
printf(\”

==========主菜单==============\”);
printf(\”

1。
  建立二叉树方法 1\”);
printf(\”

2。建立二叉树方法 2\”);
printf(\”

3。先序递归遍历二叉树\”);
printf(\”

4。中序递归遍历二叉树\”);
printf(\”

5。
  后序递归遍历二叉树\”);
printf(\”

6。层次遍历二叉树\”);
printf(\”

7。计算二叉树的高度\”);
printf(\”

8。计算二叉树中叶结点个数\”);
printf(\”

9。
  交换二叉树的左右子树\”);
printf(\”

10。打印二叉树\”);
printf(\”

0。
  结束程序运行\”);
printf(\”

===============================\”);
printf(\”

请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)\”);
scanf(\”%d\”,&k);
switch(k)
{case 1:t=creat_bt1();break; case 2:printf(\”

请输入二叉树各节点的值:\”);fflush(stdin); t=creat_bt2();break; case 3:if(t) {printf(\”先序遍历二叉树:\”); preorder(t); printf(\”

\”); }
else printf(\”二叉树为空!

\”);
break;
case 4:if(t)
{printf(\”中序遍历二叉树:\”); inorder(t); printf(\”

\”); }
else printf(\”二叉树为空!

\”);
break;
case 5:if(t)
{printf(\”后序遍历二叉树:\”); postorder(t); printf(\”

\”); }
else printf(\”二叉树为空!

\”);
break;
case 6:if(t)
{printf(\”层次遍历二叉树:\”); levorder(t); printf(\”

\”); }
else printf(\”二叉树为空!

\”);
break;
case 7:if(t)
{printf(\”二叉树的高度为:%d\”,treedepth(t)); printf(\”

\”); }
else printf(\”二叉树为空!

\”);
break;
case 8:if(t)
{printf(\”二叉树的叶子结点数为:%d

\”,leafcount(t)); printf(\”二叉树的叶结点数为:\”);paintleaf(t); printf(\”

\”); }
else printf(\”二叉树为空!

\”);
break;
case 9:if(t)
{printf(\”二叉树的左右子树:

\”); exchange(t); prtbtree(t,0); printf(\”

\”); }
else printf(\”二叉树为空!

\”);
break;
case 10:if(t)
{printf(\”逆时针旋转90度输出的二叉树:

\”); prtbtree(t,0); printf(\”

\”); }
else printf(\”二叉树为空!

\”);
break;
case 0:exit(0);
}
}while(k>=1&&kdata=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if(i==1)t=p;
else
{j=i/2;if(i%2==0) v[j]->lch=p;elsev[j]->rch=p;}
printf(\”

请继续输入二叉树各结点的编号和对应的值:\”);
scanf(\”%d,%c\”,&i,&e);
}
return(t);
}
bitnode *creat_bt2()
{
bitnode *t;etype e;
scanf(\”%c\”,&e);
if(e==\’#\’)
t=NULL;
else
{
t=(bitnode *)malloc(sizeof(bitnode));
t->data=e;
t->lch=creat_bt2();
t->rch=creat_bt2();
}
return(t);
}
void preorder(bitnode *p){
if(p)
{
printf(\”data);
preorder(p->lch);
preorder(p->rch);
}
}
void inorder(bitnode *p)
{
if(p){

inorder(p->lch);
printf(\”data);
inorder(p->rch);
}
}
void postorder(bitnode *p)
{
if(p)
{
postorder(p->lch);
postorder(p->rch);
printf(\”data);
}
}
void enqueue(bitree T)
{
if(front!=(rear 1)%m)
{rear=(rear 1)%m;que[rear]=T;}
}
bitree delqueue()
{
if(front==rear)return NULL;
front=(front 1)%m;
return(que[front]);
}
void levorder(bitree T)
{
bitree p;
if(T)
{
enqueue(T);
while(front!=rear)
{
p=delqueue();
printf(\”data);
if(p->lch!=NULL)enqueue(p->lch);
if(p->rch!=NULL)enqueue(p->rch);
}
}
}
int treedepth(bitree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=treedepth(bt->lch);
hr=treedepth(bt->rch);
max=(hl>hr)? hl:hr;
return(max 1);
}
else
return(0);
}
void prtbtree(bitree bt,int level)
{
int j;
if(bt){
prtbtree(bt->rch,level 1);
for(j=0;jdata);
prtbtree(bt->lch,level 1);
}
}
void exchange(bitree bt)
{
bitree p;
if(bt)
{p=bt->lch;bt->lch=bt->rch;bt->rch=p;exchange(bt->lch);exchange(bt->rch);}
}
int leafcount(bitree bt)
{
if(bt!=NULL)
{
leafcount(bt->lch);
leafcount(bt->rch);
if((bt->lch==NULL)&&(bt->rch==NULL))
count ;
}
return(count);
}
void paintleaf(bitree bt)
{
if(bt!=NULL)
{
if(bt->lch==NULL&&bt->rch==NULL)
printf(\”data);
paintleaf(bt->lch);
paintleaf(bt->rch);
}
}。

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/cjia/6421.html

C语言编程之二叉树的遍历图解

C函数前加extern是什么意思?

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部