北工大初试复试数据结构复习.pptx

1

复习：树和二叉树

2

第六章树主要内容

6.1树的类型定义

6.2二叉树的类型定义

6.3二叉树的存储结构

6.4二叉树的遍历

6.5线索二叉树

6.6树和森林的表示方法

6.7树和森林的遍历

6.8哈夫曼树与哈夫曼编码

3

6.1树的相关概念

结点:

结点的度:分支的个数

树的度:

叶子结点:

分支结点

路径：

孩子结点、双亲结点

兄弟结点、堂兄弟

祖先结点、子孙结点

结点的层次

树的深度:树中叶子结点所在的最大层次

A

B

C

D

E

F

G

H

I

J

M

K

L

4

树与广义表的对应

A

B

C

D

E

F

G

H

I

J

M

K

L

A(B(E,F(K,L)),C(G),D(H,I,J(M)))

T1

T3

T2

树根

5

有序树：子树之间存在确定的次序关系。

无序树：子树之间不存在确定的次序关系。

10

4

15

3

6

12

17

20

5

7

示例是一个二叉排序树。该示例表明：利用有序树可以明确的表示所有元素之间的关系

6

6.2二叉树

1）二叉树的5种基本形态

1)空树

2)只含根结点

N

3)右子树为空树

N

L

4)左子树为空树

N

R

N

R

L

5)左右均不为空树

7

2）二叉树的性质

性质1：二叉树的第i层上至多有2i-1个结点。(i≥1)

性质2：深度为k的二叉树上至多含2k-1个结点

性质3：对任何一棵二叉树，若它含有

n0个叶子结点、n2个度为2的结点，则：

n0=n2+1。

性质4：具有n个结点的完全二叉树的深度为

log2n+1。

8

2）二叉树的性质

性质5：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

11

12

i

i/2

i+1

2i

2i+1

2i+2

2i+3

9

6.3二叉树的链式存储表示

1)二叉链表

2)三叉链表

3)双亲链表

4)线索链表

10

6.4二叉树的遍历

四种访问顺序：

DLR

LDR

RLD

层次访问

前三种的递归和非递归算法

层次访问的队列算法

11

中序遍历算法的非递归描述

voidInOrderTraverse(BiTreeT,

void(*visit)(TElemType)){

InitStack(S);p=T;//从根结点开始

}//InOrderTraverse

while(p||!StackEmpty(S)){

if(p){

Push(S,p);p=p-lchild;}

else{

Pop(S,p);visit(p-data);

p=p-rchild;}

}//while

12

先序遍历算法的非递归描述

voidPreOrderTraverse(BiTreeT,

void(*visit)(TElemType)){

InitStack(S);p=T;//从根结点开始

if(T)Push(S,T);

}//InOrderTraverse

while(!StackEmpty(S)){

Pop(S,p);visit(p-data);

if(p-rchild)Push(S,p-rchild);

if(p-lchild)Push(S,p-lchild);

}//while

13

后序遍历算法的非递归描述

voidPosOrderTraverse(BiTreeT,

void(*visit)(TElemType)){

InitStack(S);p=T;//从根结点开始

}//InOrderTraverse

while(p||!StackEmpty(S)){

if(p){Push(S,p);p=p-lchild;}

else{t=NULL;flag=1;

while(!StackEmpty(S)flag){

p=GetTop(S);

if(p-rchild==t)/