char data; } DNODE; DNODE a[MAXN]; int n,m;
(10,A),(20,B),(30,D),(30,E),(40,H),(40,I),(30,F),(35,J) (20,C),(23,G),(25,K),(25,L)
10 A
20 B
20
C
30
30
30
D
E
F
40
H
NODE *lev_tree(a,m,n) DNODE a[ ]; int m,n; { int i,j;
NODE *root,*p,*q; if (n<1) return(NULL); root=(NODE*)malloc(sizeof(NODE)); root->lev=a[0].lev; root->data=a[0].data; for(i=0;i<m;i++)
EF
G
H
F2 G1 D0
C的孩子进栈
2 G1 D0
输出F,F出栈
void s_preorder(t,m) NODE *t; int m; { NODE *s[100];
int top,i; if (t= =NULL) return; s[0]=t; top=1;
while (top>0) { t=s[--top];
40
35
I
J
23
G
25
K
25
L
(10,A),(20,B),(30,D),(30,E),(40,H),(40,I),(30,F),(35,J) (20,C),(23,G),(25,K),(25,L)
P 10 A ^ ^ ^ ^
q
20 B ^ ^ ^ ^ q
30 D ^ ^ ^ ^
30 E ^ ^ ^ ^
printf(“%c”,t->data); for(i=m-1;i>=0;i--)
if (t->child[i]!=NULL) s[top++]=t->child[i];
} }
树的后序遍历
• 首先按后序遍历根结点的各棵子树,然后访问根结点
A
B
C
D
EF
G
H
EBFHGCDA
一棵3次有序树其前序,后序的遍历结果为:
EF
G
H
head
tail
q
BCD
A的孩子进队
树的层次遍历
A
head
tail
B
C
D
EF
G
H
q
Hale Waihona Puke CDhead输出B,B出队 tail
q
CDE
B的孩子进队
树的层次遍历
A
head
tail
B
C
D
q
EF
G
q H
DE
输出C,C出队
head
tail
DEF G C的孩子进队
void levorder(t,m) NODE *t; int m; { NODE *q[100],*p;
树的遍历
• 按照一定的规则将树中所有结点的数据 信息排列成一个线性序列
– 树的前序遍历 – 树的后序遍历 – 树的层次遍历 – 获得树中所有叶子结点
树的前序遍历
• 首先访问根结点,然后按前序遍历根结点 的各棵子树
– 所得结点序列是唯一的
A
– 前序遍历的定义是递归的
B
C
D
ABECFGHD
EF
G
H
#include <stdio.h> #define MAXM 10 struct node { char data;
root->child[i]=NULL; root->parent=NULL;p=root;
}
树的前序遍历
A
B
C
D
EF
G
2 1 A地址 0
B2 C1 D0
输出A,A出栈
H A的孩子D,C,B进栈
树的前序遍历
A
B
C
D
EF
G
2 C1 D0
输出B,B出栈 H
E2 C1 D0
B的孩子进栈
树的前序遍历
A
B
C
D
EF
G
2 C1 D0
输出E,E出栈 H
2 1 D0
输出C,C出栈
树的前序遍历
A
B
C
D
int head,tail,i; q[0]=t; head=0; tail=1; while(head<tail)
{ p=q[head++]; printf(“%c”,p->data); for(i=0;i<m;i++)
if (p->child[i]!=NULL) q[tail++]=p->child[i];}
}
获得树中所有叶子结点
• 如树中只有一个结点,则此结点就是此树的叶子结点 • 树中的叶子结点就是根结点的各棵子树的叶子结点
A
B
C
D
EFHD
EF
G
H
树的线性表示
• 把树的结点输入计算机中,从而建立树的 结构
– 树的层号表示 – 树的括号表示
树的层号表示
• 结点k的层号lev(k):
– 如果k’是k的子结点,则 lev(k’)>lev(k)
– 如果k’和k”同是结点k的子结点,则 lev(k”)=lev(k’)
• 结点的层号不是唯一的 • 结点所在的层次是唯一的
10
0
A
20 B 1
20
1C
30
30
30
D
E
F
40
H
40
35
I
J
23
G
25
K
25
L
按前序写出树中全部结点,并在结点之前带上结点的层号
(10,A),(20,B),(30,D),(30,E),(40,H),(40,I)……..(25,L) (0,A),(1,B),(1,C),(2,D),(2,E),(3,H),(3,I)……….(4,L)
#include <stdio.h> #define MAXM 10 #define MAXN 100 struct node { int lev;
char data; struct node *child[MAXM]; struct node *parent; }; typedef struct node NODE; typedef struct dnode { int lev;
前序: ABCDEFGHI 后序:BCGHFEIDA
则该3次有序树用图形表示应为什么?
树的层次遍历
• 首先访问处于第0层上的根结点,然后访问处于
第一层上的结点,再访问处于第二层上的结点,
再依次访问以下各层上的结点
A
B
C
D
ABCDEFGH
EF G H
树的层次遍历
A
head
tail
B
C
qA D
输出A,A出队
struct node *chile[MAXM]; }; typedef struct node NODE; int m; NODE *t;
void r_preorder (t,m) NODE *t; int m;
{ int i; if (t!=NULL) {printf(“%c”,t->data); for (i=0;i<m;i++) if(t->child[i]!=NULL) r_preorder(t->child[i],m); }