第15讲树4.ppt

* * 授课者：章 英 E-mail：walking7876@ Essential of Lecture Fifteen ： 一、树的存储结构 二、森林和二叉树的转换 三、哈夫曼树及编码 四、哈夫曼树的应用 难点 实战：软件设计师 2004上半年试题 1、选择题 设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是__(10)__。 A．x是y的左兄弟 B．x是y的右兄弟 C．x是y的祖先 D．x是y的后裔 实战： 2、选择题 若在一个森林中有n个结点，k条边(nk)，则该森林中必有 棵树。 A k B n C n-k D n+k 假设森林中有T1,T2,…,Ts，且每个Ti有ni个结点，ki条边，由树的等价条件知：ki=ni-1，则k=k1+k2+…+ks=(n1-1)+(n2-1)+…+(ns-1)=n-s。故s=n-k。 一、树的存储结构 树的存储结构 (1) 双亲表示法 采用一组连续空间存储树的结点，通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。 I A C B H G F E D 9 A 0 B 1 C 1 D 2 E 2 F 3 G 5 H 5 I 5 0 1 2 3 4 5 6 7 8 9 data parent 一、树的存储结构 双亲表示法 #define MAX 100 struct PTNode{ char data; int parent; }; struct PTree{ struct PTNode nodes[MAX]; int r,n; }; A -1 B 0 C 0 D 1 E 1 F 2 G 4 H 4 I 4 0 1 2 3 4 5 6 7 8 9 data parent I A C B H G F E D 一、树的存储结构 树的存储结构 (2) 孩子表示法 通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。孩子链表：对树的每个结点用线性链表存储它的孩子结点。 ∧ I ∧ H ∧ G ∧ F E ∧ D C B A 0 1 2 3 4 5 6 7 8 9 6 8 ∧ 7 1 2 ∧ 4 ∧ 5 ∧ 3 data firstchild 树的孩子链表图示 找一个结点的孩子十分方便，但要找一个结点的双亲则要遍历整个结构 I A C B H G F E D 一、树的存储结构 struct CTNode { //孩子结点 int child; struct CTNode * next; }*ChildPtr; struct { char data; ChildPtr firstchild; //孩子链表头指针 } CTBox; struct { CTBox nodes[MAX]; int n, r; }CTree; 一、树的存储结构 树的孩子链表存储表示 ∧ ∧ ∧ ∧ ∧ 4 I 4 H 4 G 2 F 1 E 1 D 0 C 0 B -1 A 0 1 2 3 4 5 6 7 8 9 6 8∧ 7 1 2 ∧ 4 ∧ 5 ∧ 3 data parent firstchild 带双亲孩子链表 双亲孩子表示法： 结合双亲表示法和孩子表示法 I A C B H G F E D 一、树的存储结构 （3）孩子兄弟表示法 用二叉链表作为树的存储结构。链表的两个指针域分别指向该结点的第一个孩子结点和下一个兄弟结点。 struct CSNode { char data; struct CSNode *firstchild, * nextsibling; }CSNode , *CSTree; 一、树的存储结构 树的孩子兄弟表示法图示 B的第一个孩子结点 B的右兄弟结点 一、树的存储结构 G H ∧ I D ∧ A ∧ ∧ ∧ ∧ B ∧ F ∧ ∧ E ∧ C 二叉树与树都可用二叉链表存储，以二叉链表