先序递归生成树
void CreateBinTree (struct BinTNode **T) {char ch； if((ch=getchar())=='') *T=NULL； else{ *T=(BinTNode *)malloc(sizeof(BinTNode))； //生成结点 (*T)->data=ch； CreateBinTree(&(*T)->lchild)； //构造左子树 CreateBinTree(&(*T)->rchild)； //构造右子树 } }
二叉树 定义 二叉树存储 二叉树应用
二叉树存储
顺序存储 链式存储
以完全二叉树方式存！
结点编号完全的二叉树
1 A 2 B 4 D 8 H 16 P 17 Q C 3
E 5 910 I J
6 F
G 7 13 14 15 M N O
11 12 K L
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 17 A B C D E F G H I J K L M N O 素之间的逻辑关系 两种结构： 线性结构 非线性结构 Lists, Stacks, Queues, Vectors
数据结构
第6节 树和二叉树
树 二叉树
例子：家族
张源 张明 张林 张维 张亮 张平 张华 张晶 张磊 张群 张丽
术语
结点(node)
二叉树性质
性质1 若二叉树的层次从0开始, 则在二叉树的第 i 层最多有 2i 个结点。(i 0)
性质2 高度为 k 的二叉树最多有 2k+1-1个结点。(k -1)
性质3 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非 叶结点个数为 n2, 则有: n0＝n2＋1
性质4 具有 n 个结点的完全二叉树的高度为 log2n +1或 log2(n+1)
二叉树的定义
• 每个节点最多有2个孩子的有序树
A
满二叉树
B
C E F K L G MN O
D
H I J
一棵深度为k且有2k－1个结点的二又树称为满二叉树。
完全二叉树
A B D H I J C B G H D I J
A C E K F
L G
E
K L
F
完全二叉树
非完全二叉树
若一棵二叉树至多只有最下面的两层上结点的度数可以小 于2，并且最下一层上的结点都集中在该层最左边的若干位置 上，则此二叉树称为完全二叉树。
哈夫曼树应用——哈夫曼编码
前缀码： 任何一个字符的编码,不能是另一个编码的前缀。这 种编码称为前缀码
利用哈夫曼树构造出的前缀码称为哈夫 曼编码
二叉树应用
哈夫曼树 二叉排序树
定义
1. 空树 2. 或者是具有下述性质的二又树： 其左子树上所有结点的数据值均小 于根结点的数据值，右子树上所有结点 的数据值均大于或等于根结点的数据值。 左子树和右于树又各是一棵二又排序树。
内部(inside)结点 分支(branch)结点
根结点(Root) 叶(leaf)结点 双亲(parent)结点 子女(child)结点 兄弟(sibling)结点 祖先(ancestor)结点 子孙(descendant)结点
术语 结点的度(degree) 树的度(degree of tree) 结点所处层次(level) 路 径 空树 森林
WPL计算
如何构造哈夫曼树
(1) 由给定的 n 个权值{w0, w1, w2, …, wn-1}，构造具有 n 棵扩充二叉树的森林F = { T0, T1, T2, …, Tn-1 }，其中每一 棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、 右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： ① 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做 为左、右子树构造一棵新的二叉树。置新的二叉树的根 结点的权值为其左、右子树上根结点的权值之和。 ② 在 F 中删去这两棵二叉树。 ③ 把新的二叉树加入 F。
后序
void PostOrder(struct BinTNode *T) { if (T == NULL) { return; } PostOrder(T->lchild); PostOrder(T->rchild); printf("%c ", T->data); }
二叉链表的操作 由底向上建立 遍历 递归生成树
总结
• 树的特点是有多个直接后继，最多一个直接前驱 • 二叉树是特别研究的，非二叉树可以转化为二叉 树来处理
树的定义
空树 或者一个根，几个子树。子树也是一颗树
树的特点
树中任一结点都可以有零个或多个直接后继 (即孩子)结点，但至多只能有一个直接前趋 (即双亲)结点。 有序树中，同一组兄弟结点从左到右有长幼 之分
数据结构
第6节 树和二叉树
树 二叉树
二叉树 定义 二叉树存储 二叉树应用
一般二叉树存储
A
补成完全树！
Ø B
Ø
Ø
Ø
C
下标
0
1
2
3
4
5
6
7
３ Ａ Ø
Ｂ Ø
Ø
Ø
Ｃ
二叉树存储
顺序存储 链式存储
结点的类型
struct BinTNode { char data； Struct BinTNode *lchild， *rchild； //左右孩子指针 }；
lchild
data
rchild
举例
二叉链表的操作 由底向上建立 遍历
举例 int main() { T1 = Tree('D', NULL, NULL); T2 = Tree('E', NULL, NULL); T3 = Tree('B', T1, T2); T4 = Tree('F', NULL, NULL); T5 = Tree('G', NULL, NULL); T6 = Tree('C', T4, T5); my Tree = Tree('A', T3, T6); }
举例：排序树
10 3 2 4 9 9 13 15 18 21
8
写出其中序序列？
如何生成排序树？
1. 令R1为二叉排序树的根结点。 2. 若R2＜R1,令R2为R1的左子树的根结 点; 否则R2为R1的右子树的根结点。 3. R3, · · ·, Rn结点的插入方法同上。
作业
• 17 • 19 • 21 • 23
二叉链表的操作 建立 遍历
先序 中序 后序
先序遍历
1. 访问根结点 2. 遍历左子树 3. 遍历右子树
中序遍历
1. 遍历左子树 2. 访问根结点 3. 遍历右子树
后序遍历
1. 遍历左子树 2. 遍历右子树 3. 访问根结点
举例：表达式树
先序：-+a*b-cd/ef
中序：a+b*c-d-e/f 后序：abcd-*+ef/-
二叉树 定义 二叉树存储 二叉树应用
二叉树应用
哈夫曼树 排序树
哈夫曼树(Huffman Tree) 带权路径长度WPL最小的二叉树。 又称为最优二叉树,
带权路径长度 ( Weighted Path Length, WPL )
树的各叶结点所带的权值与该结点到根 的路径长度的乘积之和。
先序
void PreOrder(struct BinTNode *T) { if (T == NULL) { return; } printf("%c ", T->data); PreOrder(T->lchild); PreOrder(T->rchild); }
中序
void InOrder(struct BinTNode *T) { if (T == NULL) { return; } InOrder(T->lchild); printf("%c ", T->data); InOrder(T->rchild); }
新建节点，返回节点指针
struct BinTNode *Tree(char newthing, struct BinTNode * L, struct BinTNode * R) { struct BinTNode *T； T=(struct BinTNode *) malloc(sizeof(struct BinTNode))； //生成结点 T->data= newthing; T->lchild = L T->rchilid = R; return T; }