二叉树的遍历

Question

对二叉树的遍历的（1）前序遍历、（2）中序遍历、（3）后序遍历；我有点不理解，书上举得例子树的深度太浅，看不出规律，哪位好心人能举个树的深度有5的满二叉树，最好能截图啊，不要讲概念。

Answer 1

二叉树遍历的顺序：如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。
前序遍历的规则如下：
若二叉树为空，则退出。否则
⑴访问处理根结点；
⑵前序遍历左子树；
⑶前序遍历右子树；
特点：由左而右逐条访问由根出发的树支 （回溯法的基础）
中序遍历的规则：
若二叉树为空，则退出；否则
⑴中序遍历左子树；
⑵访问处理根结点；
⑶中序遍历右子树；
后序遍历的规则如下：
若二叉树为空，则退出；否则
⑴后序遍历左子树；
⑵后序遍历右子树；
⑶访问处理根结点；追问

这个我能背上，就是不知道什么意思，，你能给我弄个五层的树走一下吗（低于五层就不要写了）。。。。。

Answer 2

1
2 3
4 5 6 7
其实就够了。
前序（根左右）：1 2 4 5 3 6 7
中序（左根右）：4 2 5 1 6 3 7
后序（左右根）：4 5 2 6 7 3 1
我感觉编程自己实践一些就可以了。直接把代码抄计算机上实践一下，比在这里问要直接。追问

我不要实践下，我不是学数据结构的，也用不到，我就是二级考的时候它问我怎么走我知道怎么走就行，你能给我弄个五层的数吗？就三层，看不出规律。

追答

1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
前序：1 2 4 8 16 17 9 18 19 5 10 20 21 11 22 23 3 6 12 24 25 13 26 27 7 14 28 29 15 30 31
中序：16 8 17 4 18 9 19 2 20 10 21 5 22 11 23 1 24 12 25 6 26 13 27 3 28 14 29 7 30 15 31
后序：16 17 8 18 19 9 4 20 21 10 22 23 11 5 2 24 25 12 26 27 13 6 28 29 14 30 31 15 7 3 1
希望你能懂呀……

本回答被提问者采纳

Answer 3

给你贴出来整个程序你应该就能看懂了吧……

你也可以去这个地方下载CPP文件自己调试：http://www.fleaf.net/thread-233-1-1.html

//程序员：张圣超
//班级：网络工程
//***********************************************************
//头文件
#include<stdio.h>
#include<stdlib.h>
//***********************************************************
//宏定义
#define OK 1
#define ERROR 0
#define OVERFLOW 0

//***********************************************************

typedef struct BiTNode{
//二叉树二叉链表存储结构
char data;
struct BiTNode *lChild,*rChild;
}BiTNode,*BiTree;
//***********************************************************
int CreateBiTree(BiTree &T){
//按先序次序输入二叉中树结点的值，空格表示空树
//构造二叉链表表示的二叉树T
char ch;
fflush(stdin);
scanf("%c",&ch);
if(ch==' ')T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
return(OVERFLOW);
T->data=ch;
CreateBiTree(T->lChild);
CreateBiTree(T->rChild);
}
return(OK);
}
//***********************************************************
void PreOrderTraverse(BiTree T){
//采用二叉链表存储结构，先序遍历二叉树的递归算法
if(T){
printf("%c",T->data);
PreOrderTraverse(T->lChild);
PreOrderTraverse(T->rChild);
}
}
//***********************************************************
void InOrderTraverse(BiTree T){
//采用二叉链表存储结构，中序遍历二叉树的递归算法
if(T){
InOrderTraverse(T->lChild);
printf("%c",T->data);
InOrderTraverse(T->rChild);
}
}
//***********************************************************
void PostOrderTraverse(BiTree T){
//采用二叉链表存储结构，后序遍历二叉树的递归算法
if(T){
PostOrderTraverse(T->lChild);
PostOrderTraverse(T->rChild);
printf("%c",T->data);
}
}
//***********************************************************
void main(){
//主函数分别实现建立并输出先、中、后序遍历二叉树
BiTNode *Tree;
CreateBiTree(Tree);
printf("\n先序遍历二叉树:");
PreOrderTraverse(Tree);
printf("\n中序遍历二叉树:");
InOrderTraverse(Tree);
printf("\n后序遍历二叉树:");
PostOrderTraverse(Tree);
}

参考资料：http://www.fleaf.net/thread-233-1-1.html

Answer 4

先序遍历
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define StackSize 1200
typedef struct node
{
char data;
struct node *lchild, *rchild;
}BiTree;

typedef struct
{
BiTree *data[StackSize];
int top;
}Stack;
void StackInit(Stack *s)
{
s->top=-1;
}
int StackEmpty(Stack s)
{
if(s.top==-1)
return 1;
else
return 0;
}

int push(Stack *s,BiTree *e)
{
if(s->top==StackSize-1)
return 0;
else
{
(s->top)++;
s->data[s->top]=e;
return 1;
}
}
BiTree *pop(Stack *s)
{
BiTree *e;
if(s->top==-1)
return NULL;
else
{
e=s->data[(s->top)--];
return e;
}
}

BiTree * CreateBiTree()
{
char ch;
BiTree *b;
ch = getchar();
getchar();
if(ch == '@')
{
b = NULL;
}
else
{
if(!(b = (BiTree *)malloc(sizeof(BiTree)))) exit(-1);

b->lchild = CreateBiTree();
b->data = ch;
b->rchild = CreateBiTree();
}
return b;
}

void PreOrderUnrec(BiTree *t)
{
Stack s;
StackInit(&s);

while (t!=NULL||!StackEmpty(s))
{
if(t!=NULL)
{
printf("%c ",t->data);
push(&s,t);
t=t->lchild;
}

else
{
t=pop(&s);
t=t->rchild;
}

}
}

int BiTreeDepth(BiTree *t)
{
if(!t)
return 0;
else
return
BiTreeDepth(t->lchild) > BiTreeDepth(t->rchild) ?
(BiTreeDepth(t->lchild)+1) : (BiTreeDepth(t->rchild)+1);
}
int leaf(BiTree *t)
{

if(t==NULL)
return 0;
else if(t->lchild==NULL && t->rchild==NULL)
return 1;
else return leaf(t->lchild)+leaf(t->rchild);

}

void main()
{
BiTree *T;
int height,leafcount;
printf("Please Create a Tree!\n");
T=CreateBiTree();
PreOrderUnrec(T);
height=BiTreeDepth(T);
leafcount=leaf(T);
printf("The number of Tree's leaf is %d!\n",leafcount);
printf("The height of Tree is %d!\n",height);
}追问

你弄个五层的树走一下，多方便，你说你写这么多，我也不会看，看了也看不懂，多麻烦。。。

追答

你不是要遍历吗？你运行程序要多少层就多少层，你不会看那是你的事，我按自己的理解给出自己的答案有何不可