【精品】树和二叉树.ppt

文档介绍：树和二叉树
树的概念
存储结构和运算
树和二叉树的性质
二叉树的概念
第五章
二叉树的五种基本形态:
空树
N
只含根结点
N
L
右子树为空
N
R
左子树为空
N
R
L
左右子树均不为空树
E

A
D
B
C
F






root
left data right
结点结构:
二叉链表
先(根)序的遍历算法
DLR
中(根)序的遍历算法
LDR
后(根)序的遍历算法
LRD
先右后左的遍历算法
RLD RDL DRL
A
B
C
G
F
H
E
I
D
A, B, C, D, E, F, G, H, I
层次遍历序列:
前序遍历递归算法
void Preorder(BTreeNode* BT)
{ if(BT!=NULL)
{ cout<<BT->data<<' '; //D访问根结点
Preorder(BT->left); //L遍历左子树
Preorder(BT->right); //R遍历右子树
}
}
由二叉树的先序和中序序列建树
先序序列
中序序列
左子树
左子树
右子树
右子树
根
根
建立二叉树
以字符串的形式定义一棵二叉
树
采用广义表表示的输入法定义
一棵二叉树
A
B
C
D
E
F
G
A
B
C
E D
F
G
root
A
B
C
E D
F
G
二叉链表(孩子-兄弟)存储
树的遍历
树的遍历可有三条搜索路径:
先根(次序)遍历:
后根(次序)遍历:
按层次遍历: