数据结构教程第二十三课二叉树的存储结构
文章作者 100test 发表时间 2007:03:10 18:28:59
来源 100Test.Com百考试题网
教学目的: 掌握二叉树的两种存储结构
教学重点: 链式存储结构
教学难点: 链式存储二叉树的基本操作
授课内容:
一、复习二叉树的定义
二叉树的基本特征:每个结点的度不大于2。
二、顺序存储结构
#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE].
SqBiTree bt.
结点编号 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
结点值 |
1 |
2 |
3 |
4 |
5 |
0 |
0 |
0 |
0 |
6 |
7 |
0 |
0 |
0 |
0 |
第i号结点的左右孩子一定保存在第2i及2i 1号单元中。
缺点:对非完全二叉树而言,浪费存储空间
三、链式存储结构
一个二叉树的结点至少保存三种信息:数据元素、左孩子位置、右孩子位置
对应地,链式存储二叉树的结点至少包含三个域:数据域、左、右指针域。
也可以在结点中加上指向父结点的指针域P。