二叉树的遍历

关于二叉树的前序遍历、中序遍历、后序遍历要如何访问，那个开头，顺序是什么样的。请大家说说，大家一定要说详细点，因为这点我是完全不懂。

#include "stdafx.h"
#include "stdlib.h"

#define MAX_NODE 100
#define NODE_COUNT1 8
#define NODE_COUNT2 15

int TreeValue0[NODE_COUNT1][2] = {{'0',0},{'D',1},{'B',2},{'F',3},{'A',4},{'C',5},{'E',6},{'G',7}};
int TreeValue1[NODE_COUNT1][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7}};
int TreeValue2[NODE_COUNT2][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7},{'H',8},{'I',9},{'J',10},{'K',11},{'L',12},{'M',13},{'N',14}};
struct BTree
{
int data;
int order;
BTree *lchild;
BTree *rchild;
};

void Swap(int *p1,int *p2)
{
int t;
t = *p1;
*p1 = *p2;
*p2 = t;
}

BTree *CreateBTree(int data[][2],int n)
{
BTree *Addr[MAX_NODE];
BTree *p,
*head;
int nodeorder,//节点序号
noderoot, //节点的双亲
i;
if(n>MAX_NODE)
{
printf("参数错误！\n");
return(0);
}
for(i=1;i<=n;i++)
{
p = (BTree *)malloc(sizeof(BTree));
if(p==NULL)
{
printf("内存溢出错误！\n");
return(0);
}
else
{
p->data = data[i][0];
p->lchild = NULL;
p->rchild = NULL;
nodeorder = data[i][1];
p->order = nodeorder;
Addr[nodeorder] = p;
if(nodeorder>1)
{
noderoot = nodeorder/2;
if(nodeorder %2 == 0)
Addr[noderoot]->lchild = p;
else
Addr[noderoot]->rchild = p;
}
else
head = p;
printf("BTree[%d] = %c\t",p->order,p->data);
}
//free(p);
}
return(head);
}

void FirstOrderAccess0(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
top = top+1;
stack[top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top];
top = top-1;
p = p->rchild;//继续搜索节点P的右子树
}
}while((top!=0)||(p!=NULL));
}

void FirstOrderAccess1(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
printf("BTree[%d] = %c\t",p->order,p->data);
if(p->rchild!=NULL)
stack[++top] = p->rchild;
p = p->lchild;
}
if(top!=0)
p = stack[top--];
}while((top>0)||(p!=NULL));
}

void MiddleOrderAccess(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
stack[++top] = p;//节点P进栈
p = p->lchild; //继续搜索其左子树
}
if(top!=0)
{
p = stack[top--];//节点P出栈
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
p = p->rchild;//继续搜索其左子树
}
}while((top!=0)||(p!=NULL));
}

void LastOrderAccess(BTree * header)
{
BTree * stack[MAX_NODE];//节点的指针栈
int count[MAX_NODE];//节点进栈次数数组
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
stack[++top] = p;//节点P首次进栈
count[top] = 0;
p = p->lchild; //继续搜索节点P的左子树
}
p = stack[top--];//节点P出栈
if(count[top+1]==0)
{
stack[++top] = p;//节点P首次进栈
count[top] = 1;
p = p->rchild; //继续搜索节点P的左子树
}
else
{
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
p = NULL;
}
}while((top>0));
}

int IsLeafNode(BTree *node)
{
if((node->lchild==NULL)&&(node->rchild==NULL))
return(1);
else
return(0);
}

void PrintLeafNode(BTree *header)
{
BTree * stack[MAX_NODE];//节点的指针栈
BTree *p;
int top;
p = header;
top = 0;
do
{
while(p!=NULL)
{
stack[++top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top--];
if(IsLeafNode(p))
printf("LNode[%d] = %c\t",p->order,p->data);//访问叶子节点
p = p->rchild;//继续搜索节点P的右子树
}
}while(top>0||p!=NULL);
}

int HasTwoChildNode(BTree *node)
{
if((node->lchild!=NULL)&&(node->rchild!=NULL))
return(1);
else
return(0);
}

void SwapChildNode(BTree *header)
{
BTree * stack[MAX_NODE];//节点的指针栈
BTree *p;
int top;
p = header;
top = 0;
do
{
while(p!=NULL)
{
stack[++top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top--];
if(HasTwoChildNode(p))
Swap(&p->lchild->data,&p->rchild->data);//交换节点P的左、右孩子
p = p->rchild;//继续搜索节点P的右子树
}
}while(top>0||p!=NULL);
}

int main(int argc, char* argv[])
{
BTree * TreeHeader;
printf("二叉树创建数据结果：\n");
TreeHeader = CreateBTree(TreeValue1,NODE_COUNT1-1);
//TreeHeader = CreateBTree(TreeValue2,NODE_COUNT2-1);
if (TreeHeader==0)
{
printf("二叉树创建失败！\n");
return(0);
}
else
{
printf("\n二叉树前序遍历结果：\n");
FirstOrderAccess1(TreeHeader);
printf("\n二叉树中序遍历结果：\n");
MiddleOrderAccess(TreeHeader);
printf("\n二叉树后序遍历结果：\n");
LastOrderAccess(TreeHeader);
//printf("\n二叉树的所有叶子节点：\n");
//PrintLeafNode(TreeHeader);
//SwapChildNode(TreeHeader);
//printf("\n二叉树交换孩子的结果：\n");
//MiddleOrderAccess(TreeHeader);
printf("\n程序运行完毕!\n");
return 0;
}
}

　　

2.两个重要的概念： 　　(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树； 　　(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。 　　如下图： 　　　　　　　　　　　　 　　　

完全二叉树

　

满二叉树 　　3.二叉树的性质 　　 (1) 在二叉树中，第i层的结点总数不超过2^(i-1)；

(2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点； 　　 (3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，

则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为int（log₂n）+1 　　 (5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系： 　　　　若I为结点编号则 如果I<>1，则其父结点的编号为I/2； 　　　　如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子； 　　　　如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。 　　4.二叉树的存储结构： 　　　(1）顺序存储方式

type node=record

data:datatype

l,r:integer;

end;

var tr:array[1..n] of node;

　　(2)链表存储方式，如： 　　　　　 type btree=^node；

node=record

data:datatye;

lchild,rchild:btree;

end;

　 　　5.普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。 　　　　　 　　6.二叉树的遍历运算（递归定义） 　　　(1)先序遍历 　　　　　　访问根；按先序遍历左子树；按先序遍历右子树 　　　(2)中序遍历 　　　　　　按中序遍历左子树；访问根；按中序遍历右子树 　　　(3)后序遍历 　　　　　　按后序遍历左子树；按后序遍历右子树；访问根 例1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。 program erchashu1; var b:array[1..31] of char; e:array[1..63] of byte; n,h,i,k:integer; procedure tree(t:integer); begin if e[t]=0 then exit else begin write(b[t]);e[t]:=0; t:=2*t;tree(t); t:=t+1;tree(t); end; end; begin repeat write('n=');readln(n); until (n>0) and (n<6); fillchar(e,sizeof(e),0); k:=trunc(exp(n*ln(2)))-1; for i:=1 to k do e[i]:=1; for i:=1 to 26 do b[i]:=chr(64+i); for i:=1 to 5 do b[26+i]:=chr(48+i); h:=1 ;tree(h); writeln; end.

　　

例2.用顺序存储方式建立一棵如图所示的二叉树，并对其进行先序遍历。

program tree1; const n=15; type node=record data:char; l,r:0..n; end; var tr:array[1..n] of node; e:array[1..n] of 0..1; i,j:integer;

procedure jtr; var i:integer; begin for i:=1 to n do with tr[i] do readln(data,l,r); end; procedure search(m:integer); begin with tr[m] do begin write(data); if l<>0 then search(l); if r<>0 then search(r); end; end; begin jtr;search(1);writeln; end.

例3 用链表存储方式生成上述二叉树，中序遍历之。

1.将上述二叉树用广义表表示为A(B(D,E(G)),C(F(,H)))

2.根据广义表串（以#结束）生成二叉树。

program ltree; const n=8; type trlist=^node; node=record da:char; l,r:trlist; end; var s:array[1..n] of trlist; p,root:trlist; ch:char; top,k:integer; procedure creat(var head:trlist); begin read(ch); top:=0; while ch<>'#' do begin case ch of 'A'..'Z':begin new(p);p^.da:=ch;p^.l:=nil;p^.r:=nil; if top<>0 then case k of 1:s[top]^.l:=p; 2:s[top]^.r:=p; end end; '(':begin top:=top+1;s[top]:=p;k:=1;end; ')': top:=top-1; ',': k:=2; end; read(ch); end; head:=s[1]; end; procedure inorder(head:trlist); begin if head^.l<>nil then inorder(head^.l); write(head^.da); if head^.r<>nil then inorder(head^.r); end; begin write('Input tree string:'); creat(root); inorder(root); end.