返回本章首页
下一页
上一页
第 8章树的存储结构及应用
? 8.1 树与树林
? 8.2 树和树林的存储表示
? 8.3 二叉树
? 8.4 二叉树的存储表示
? 8.5 哈夫曼算法及其应用 上一章
下一章
返回目录
返回本章首页
下一页
上一页
8.1 树与树林
? 8.1.1 树的定义
? 8.1.2 基本术语
? 8.1.3 树林
? 8.1.4 树的基本运算
? 8.1.5 树的周游
? 8.1.6 树林的周游
返回本章首页
下一页
上一页
8.1.1 树 (Tree) 的定义
树的例子：家族树
? A 有子女 B,C； B 和 C 分别有子女 D,E,F 和 G,H;
? E有子女 I,J。
? T = (N,R),其中
? N={A,B,C,D,E,F,G,H,I,J}
? R={< A,B>,< A,C>,< B,D>,< B,E>,< B,F>,
? < C,G>,< C,H>,< E,I>,< E,J> }
? 关系有层次性，总是高层与低层相关，同层之间无关，
也没有低层到高层的关系。与不同元素相关的元素也
互不相交。
返回本章首页
下一页
上一页
树的表示方法：
返回本章首页
下一页
上一页
返回本章首页
下一页
上一页
树的递归定义：
树是 n (n≥ 0) 个结点的有限集 T。当 T非空时，满足：
1,有且仅有一个特别标出的称为根的结点 r；
2,除根结点外，其余结点可分为 m（ m >= 0）个互不
相交非空的有限集 T1,T2,…,Tm,其中每一个集
合本身又是一棵非空树，称为根 r 的子树 (subtree)。
? 空树：结点数为 0 的树。
? 树可以没有子树（ m = 0）
返回本章首页
下一页
上一页
8.1.2 基本术语
(a) 树 t (b) 树 t '
有序树 和 无序树,树中的子树的顺序是否重要
返回本章首页
下一页
上一页
父结点，子结点，边
兄弟结点
祖先，子孙
路径，路径长度
结点的层数（根的层为 0）
深度或高度（结点的最大层数）
结点的度数、树的度数
树叶、分支结点
结点的次序（最左,… ）
返回本章首页
下一页
上一页
8.1.3 树林
树林, m（ m≥ 0）棵互不相交的树的集合
一棵非空树是二元组 Tree = (root,F),其中 root是
树根
结点,F 是 m（ m≥ 0）棵子树构成的树林。
F=(T1,
T2,…,Tm) 。 Ti 称作根 root 的第 i 棵子树。
注意树与树林的关系：
? 树由根和子树 树林 组成
? 树林由一集树组成
返回本章首页
下一页
上一页
8.1.4 树的基本运算
抽象运算（操作）
?创建空树
Tree createTree(Node p,Tree t1,Tree t2,…,Tree ti )
i = 1,2,3,…
?判断某棵树是否为空
int isNull ( Tree t )
?求树中的根结点，若为空树，则返回特殊值
Node root ( Tree t )
?求指定结点的父结点，当结点是树根时返回特殊值
Node parent ( Node p )
返回本章首页
下一页
上一页
? 求树中某个指定结点的最左子结点，当指定结点为
树叶时返回特殊值
Tree leftChild ( Tree t )
? 求树中某个指定结点的右兄弟结点，当指定结点没
有右兄弟时返回特殊值
Tree rightSibling ( Tree t,Tree child )
? 树的 周游,按某种系统方式访问树中的所有结点，
每个结点恰好访问一次。
返回本章首页
下一页
上一页
8.1.5 树的周游
1,周游,按某种规律系
统地访问树中所有结
点，每个结点恰好访
问一次的过程。
2,周游方法：按深度周
游和按宽度周游。
(I) 按深度（以图为例）
a,先根序
1）访问根结点；
2）从左到右按先根次序周游根结点的每棵子树
1,2,3,5,8,9,6,10,4,7
返回本章首页
下一页
上一页
b,中根序
1）按中根次序周游根结点
的最左子树；
2）访问根结点；
3）从左到右按中根次序周
游根结点的其它各子树。
2,1,8,5,9,3,10,6,7,4
c,后根序
1）从左到右按后根次序周游
根结点的每棵子树 ;
2）访问根结点。
2,8,9,5,10,6,3,7,4,1
返回本章首页
下一页
上一页
（ II） 按宽度（层次）周游
先访问层数为 0的结点，然后
从左到右逐个访问层数为 1的
结点，依此类推，直到访问
完树中全部结点。
1,2,3,4,5,6,7,8,9,10
返回本章首页
下一页
上一页
先根序周游的非递归算法
void preOrder( Tree t ) {
Tree c = leftChild ( t );
visit ( root( t ) );
while ( !Null ( c ) ) {
preOrder ( c );
c = rightSibling ( t,c );
}
}
返回本章首页
下一页
上一页
先根序周游的非递归算法
void npreOrder ( Tree t ) {
PSeqStack s = createEmptyStack ( );
Tree c = t;
do {
while ( !Null ( c ) ) {
visit ( c ); push ( s,c );
c = leftChild ( t,c );
}
while ( Null ( c ) && !isEmptyStack (s)) {
c = rightSibling ( t,top (s) );
pop (s);
}
} while( !Null ( c ) );
}
返回本章首页
下一页
上一页
void inOrder( Tree t ) { /*中根序周游 */
Tree c = leftChild ( t );
if ( !Null ( c ) ) inOrder( c );
visit( root( t ) );
if ( !Null ( c ) )
while ( !Null(c = rightSibling (t,c )) )
inOrder ( t,c );
}
void postOrder( Tree t ) { /*后根序周游 */
Tree c = leftChild (t,p);
while ( !Null ( c ) ) {
postOrder ( c );
c = rightSibling (t,c);
}
visit( root( t ) );
｝
返回本章首页
下一页
上一页
void levelOrder( Tree t) {
PSeqQueue q = createEmptyQueue( );
Tree c = t;
if ( Null(c) ) return;
enQueue_seq(q,c);
while (!isEmptyQueue (q)) {
c = frontQueue (q);
deQueue (q);
visit( root( c ) );
c = leftChild (t,c);
while ( !Null(c) ) {
enQueue (q,c);
c = rightSibling ( t,c );
}
}
}
返回本章首页
下一页
上一页
8.1.6 树林的周游
是其中的树的周游的总和
1,先根（ A,B,C,K,D,E,H,F,J,G )
2,后根 ( B,K,C,A,H,E,J,F,G,D )
返回本章首页
下一页
上一页
8.2 树和树林的存储表示
8.2.1 树的存储表示
8.2.2 树林的存储表示
返回本章首页
下一页
上一页
8.2.1 树的存储表示
父指针表示法
子表表示法
长子 -兄弟表示法
返回本章首页
下一页
上一页
父指针表示法
用一组连续空间存储树中结点，每个结点设一个指示器，指示其双
亲结点（父结点）的位置。
typedef struct ParTreeNode { /* 树结点结构 */
DataType info; /* 结点中的数据 */
int parent; /* 结点的父结点位置 */
} ParTreeNode;
typedef struct ParTree {
int n; /* 树中结点个数 */
ParTreeNode nodelist[MAXNUM]; /* 树中结点 */
} ParTree,*PParTree;
返回本章首页
下一页
上一页
优点,a) 容易找到父结点及所有祖先；
b) 能找到结点的子女和兄弟（穷尽）；
缺点,a) 没表示出结点之间的左右次序；
b) 找结点的子女和兄弟比较费事。
改进方法：
按某种周游次
序在数组中存
放结点。常见
的方法是按先
根序存放树中
结点，如图：
返回本章首页
下一页
上一页
返回本章首页
下一页
上一页
子表表示法
结点表中每个元素包含一个子表，存放该结点的所有子结点。结
点表顺序存放，子表用链接表示。
struct EdgeNode { /* 子表中节点的结构 */
int nodeposition;
struct EdgeNode *link;
};
typedef struct ChiTreeNode { /* 结点表中节点结构 */
DataType info;
struct EdgeNode *children;
} ChiTreeNode;
}
返回本章首页
下一页
上一页
子表表示的树结构定义如下：
typedef struct ChiTree { /* 树结构 */
struct ChiTreeNode nodelist[MAXNUM];
int root; /* 根结点的位置 */
int n; /* 结点的个数 */
} ChiTree,* PChiTree;
返回本章首页
下一页
上一页
长子 -兄弟表示法
除信息域外，增加指向其最左子女和右兄弟的指针。
typedef struct CSNode *PCSNode; /* 结点指针 */
typedef struct CSNode { /* 结点结构 */
DataType info; /* 结点中的元素 */
PCSNode lchild; /* 结点的最左子女的指针 */
PCSNode rsibling; /* 结点的右兄弟的指针 */
} CSNode; /* 结点类型 */
typedef struct CSNode *CSTree; /* 树类型定义 */
返回本章首页
下一页
上一页图 8.7 树的长子兄弟表法
找长子或者右兄弟都比较简单
找父结点很困难（可以增加父
指针）
返回本章首页
下一页
上一页
8.2.2 树林的存储表示
是树表示法的变形：
,父指针表示法
,子表表示法
,长子 -兄弟表示法
返回本章首页
下一页
上一页
树林的父结点表示方法
返回本章首页
下一页
上一页
树林的子表表示法
返回本章首页
下一页
上一页
树林的长子兄弟表示法
返回本章首页
下一页
上一页
8.3 二叉树
8.3.1 二叉树的基本概念
8.3.2 二叉树的性质
8.3.3 二叉树的基本运算
8.3.4 二叉树的周游
8.3.5 树、树林与二叉树的转换
返回本章首页
下一页
上一页
8.3.1 二叉树的基本概念
二叉树：
结点的有限集，或为空集，或由一个根及两棵不相交
的二叉树组成。
两棵子树分别称作根的, 左子树, 和, 右子树, 。
,二叉树中结点至多有两棵子树，子树有 左右 之分。
,与树不同。
返回本章首页
下一页
上一页
二叉树的基本形态：
返回本章首页
下一页
上一页
二叉树不是树的特殊情形，它们是不同的两个概念。
树和二叉树之间主要差别是：二叉树结点的子树分为
左子树和右子树，即使在结点只有一棵子树的情况下
也要明确指出该子树是左子树还是右子树。
下面是两棵不同的二叉树，但作为树是相同的。
在二叉树中可定义与树中类似的各种概念。
返回本章首页
下一页
上一页
满二叉树：每个非叶结
点都有两棵非空子树
完全二叉树：每层结点
都满，只有最下一层右
边可缺
返回本章首页
下一页
上一页
8.3.2 二叉树的一些性质
性质 1,在非空二叉树第 i 层上至多有 2i 个结点 (i≥ 0)。
性质 2,深度为 k 的二叉树至多有 2k+1-1 个结点 (k ≥ 0)。
性质 3,对任何非空二叉树 T，如果叶结点个数为 n0，度为 2 的
结点个数为 n2，则 n0 = n2 + 1。
性质 4,n 个结点的完全二叉树的深度 k 为 log2n,
性质 5,（完全二叉树）如果 n 个结点的完全二叉树按层次序
从 1 开始编号，对任一结点 i（ 1 ≤ i≤ n) 都有：
1,序号 1的结点是根； i > 1时其双亲结点是 ∟ i/2 」 。
2,如果 2i ≤ n，其左子女结点序号为 2i。否则无左子女。
3,如果 2i+1 ≤ n，其右子女结点序号为 2i+1; 否则没有右子女。
返回本章首页
下一页
上一页
A B C D E F G A B C D E F G H
1 2 3 4 5 6 7 1 2 3 4 5 6 7 8
如果完全二叉树中的结点从 0 开始编号，也有类似性质：
1,序号 0 的结点为根；
2,非根结点 i 的父结点编号是 ∟ (i – 1)/2 」 ；
3,结点的两个子结点（若存在）的编号分别为 2i+1和 2i+2。
完全二叉树的信息可以方便地存入一系列连续位置中。
返回本章首页
下一页
上一页
8.3.3 二叉树的基本运算
? 创建一棵空二叉树；
? 判断二叉树是否为空；
? 求二叉树的根结点，若为空，则返回一特殊值；
? 求二叉树中某个指定结点的父结点，当指定结点为根时，
返回一特殊值；
? 求二叉树中某个指定结点的左子女结点，当指定结点没有
左子女时，返回一特殊值；
? 求二叉树中某个指定结点的右子女结点，当指定结点没有
右子女时，返回一特殊值；
? 二叉树的周游。
返回本章首页
下一页
上一页
8.3.4 二叉树的周游
二叉树的周游 (Traversing，遍历 )：按某种顺序访问二
叉树中所有结点，每个结点访问一次且仅一次。
三种基本方式：
先根次序 (DLR)
对称序 (LDR)
后根次序 (LRD)
返回本章首页
下一页
上一页
先根次序
A B D C E G F H I
后根次序
D B G E H I F C A
对称序（中根次序）
D B A E G C H F I
返回本章首页
下一页
上一页
二叉树的周游算法
/* 二叉树的先根序（先序）周游 */
void preOrder( BNode p) {
if (p==NULL) return;
visit(p); preOrder(leftChild(p)); preOrder(rightChild(p));
}
/* 二叉树的中根序（中序）周游 */
void inOrder(BNode p) {
if (p == NULL) return;
inOrder(leftChild (p)); visit(p); inOrder(rightChild (p));
}
/* 二叉树的后根序（后序）周游 */
void postOrder(BNode p) {
if (p == NULL) return;
postOrder(leftChild (p)); postOrder(rightChild (p)); visit(p);
}
返回本章首页
下一页
上一页
8.3.5 树、树林与二叉树的转换
树、树林转换为二叉树。步骤：
1,在所有相邻的兄弟结点之间连一条线；
2,对每个非终端结点，只保留它到其最左子女的连
线，删去它与其它子女的连线；
3,以根结点为轴心，旋转整棵树。
返回本章首页
下一页
上一页
二叉树转换为树、树林。步骤：
1,若某结点是其父母的左子女，则把该结点的右子女，
右子女的右子女,… 都与该结点的父母连线；
2,去掉原二叉树中所有父母到右子女的连线。
返回本章首页
下一页
上一页
8.4 二叉树的存储表示
8.4.1 顺序表示
8.4.2 链接表示
8.4.3 二叉树的生成
返回本章首页
下一页
上一页
8.4.1 顺序表示
用一组连续存储单元按
层次序存储完全二叉树
的结点。
可以方便地从子结点找
父结点，从父结点找子
结点。
一般二叉树，可将其结点对应到完全二叉树后存储入一维数组。
用顺序方式存储非完全二叉树时，可能出现大量空位，可能浪费
大量存储空间。
返回本章首页
下一页
上一页
8.4.2 链接表示
typedef struct BNode BNode,*PBNode; /* 类型 */
struct BNode {/*二叉树结点 */
DataType info; /* 数据域 */
PBNode llink; /* 指向左子女 */
PBNode rlink; /* 指向右子女 */
};
typedef struct BNode *BinTree;
typedef BinTree *PBinTree;
返回本章首页
下一页
上一页
返回本章首页
下一页
上一页
8.4.3二叉树的生成
创建二叉树与表示方式有关。
采用顺序表示时，只需把二叉
树扩充为完全二叉树（用某种
特殊符号表示没有结点），采
用层次方式列出完全二叉树，
读入并装入数组。
创建链接表示的二叉树，设计线性输入方式（一种设计）：
? 按先序周游顺序给出结点序列
A B D C E G F H I
? 加入空二叉树信息（以方便二叉树构造），例如用 @
A B D @ @ @ C E @ G @ @ F H @ @ I @ @
返回本章首页
下一页
上一页
/* 递归地创建二叉树 */
PBinTreeNode create_BTree() {
PBinTreeNode pbnode;
char ch;
scanf(" %c",&ch);
if (ch == '@') return NULL;
pbnode = (PBinTreeNode )malloc(sizeof(BinTreeNode));
if ( pbnode == NULL ) {
printf("Out of space!\n");
return NULL;
pbnode->info = ch;
pbnode->llink = create_BTree(); /* 构造左子树 */
pbnode->rlink = create_BTree(); /* 构造右子树 */
return pbnode;
}
返回本章首页
下一页
上一页
8.5 哈夫曼算法及其应用
8.5.1 哈夫曼树
8.5.2 哈夫曼 (Huffman)算法
8.5.3 哈夫曼编码
哈夫曼树可以看作二叉树的一种应用
哈夫曼编码在信息领域有重要价值，讨论一组信息的最短
编码
问题。
返回本章首页
下一页
上一页
8.5.1 哈夫曼树
设有一集实数 {w1,w2,w3,…,wm},要构造一棵扩充二叉树，其
中包含 m个分别以 wi（ i = 1,2,…, m）为权的外部结点。要求带权
外部路径长度 WPL最小。这样的扩充二叉树称为哈夫曼树或最优二
叉树。
例如,{ 2,3,4,11}
返回本章首页
下一页
上一页
8.5.2 哈夫曼算法
1,用给定的 m 个权值 {w1,w2,…,wm} 构造 m 棵二叉树
的集合 F = {T1,T2,…,Tm},其中每棵二叉树 Ti中只
有一个带权为 wi的根结点，根结点权值为 wi ；
2,在 F中选取两棵权值最小的树作为左右子树，构造
一棵新的二叉树，新二叉树的根结点的权值为其左
右子树根结点权值之和；
3,从 F删除所选的两棵树，把新构造的二叉树加入 F；
4,重复（ 2）和（ 3），直到 F中只含一棵树为止。
返回本章首页
下一页
上一页
哈夫曼 (huffman)算法的实现
存储结构：
typedef struct HtNode { /* 哈夫曼树结点的结构 */
int ww;
int parent,llink,rlink;
} HtNode;
typedef struct HtTree { /* 哈夫曼树定义 */
HtNode ht[MAXNODE];
int root; /* 哈夫曼树根在数组中的下标 */
} HtTree,*PHtTree;
返回本章首页
下一页
上一页
/* 构造具有 m 个叶结点的哈夫曼树 */
PHtTree huffman(int m,int *w) {
PHtTree pht = initHFT(m,w); int i,j,x1,x2,m1,m2;
if (pht == NULL) return NULL;
for ( i = 0; i < m - 1; i++) {/* 每次循环构造一个内部结点 */
m1 = m2 = MAXINT; x1 = x2 = -1; /* 变量赋初值 */
for (j = 0; j < m+i; j++) {/* 找两个最小权的无父结点的结点 */
HtNode *p = &(pht->ht[j]); /* 考察一个结点 */
if (p->parent == -1) {
if (p->ww < m1) { m2 = m1; x2 = x1; m1 = p->ww; x1 = j; }
else if (p->ww < m2) { m2 = p->ww; x2 = j; }
} }
pht->ht[x1].parent = pht->ht[x2].parent = m+i; /* 构造一个内部
结点 */
pht->ht[m+i].ww = m1 + m2;
pht->ht[m+i].llink = x1; pht->ht[m+i].rlink = x2;
pht->root = m+i;
} return pht; }
返回本章首页
下一页
上一页
/* 初始化 Huffman 树数据结构 */
PHtTree initHFT (int m,int *w) {
int i;
PHtTree pht = (PHtTree)malloc(sizeof(struct HtTree));
if (pht == NULL) {
printf("Out of space!! \n");
return NULL;
}
for (i = 0; i < 2*m-1; i++) {/* 置初态 */
HtNode *p = &(pht->ht[i]);
p->llink = p->rlink = p->parent = -1;
p->ww = (i < m)? w[i], -1;
}
return pht;
}
返回本章首页
下一页
上一页
8.5.3 哈夫曼编码
设有如下基本数据：
D={d1,d2,…,dn }
W={w1,w2,…,wn }
D为需要编码的字符集,W为 D中各字符出现的频率
要求：（ 1）编码总长最短；
（ 2）若 di≠ dj,di编码不是 dj编码的前缀。
返回本章首页
下一页
上一页
通过构造哈夫曼树，实现哈夫曼编码：
以 d1,d2,…,dn 为外部结点,w1,w2,….,wn 作为外部结点
的权，构造哈夫曼树。
在哈夫曼树中，所有从一个结点引向其左子女的边标 0；
引向其右子女的边上标 1。
从根结点到叶子结点的路径上的数字拼接起来就是这
个叶子结点字符的编码。
可以证明：对于 D和 W，这样得到的哈夫曼编码是最优
（最短）编码。
返回本章首页
下一页
上一页
w = {2,3,5,7,11,13,17,19,23,29,31,37,}
下一页
上一页
第 8章树的存储结构及应用
? 8.1 树与树林
? 8.2 树和树林的存储表示
? 8.3 二叉树
? 8.4 二叉树的存储表示
? 8.5 哈夫曼算法及其应用 上一章
下一章
返回目录
返回本章首页
下一页
上一页
8.1 树与树林
? 8.1.1 树的定义
? 8.1.2 基本术语
? 8.1.3 树林
? 8.1.4 树的基本运算
? 8.1.5 树的周游
? 8.1.6 树林的周游
返回本章首页
下一页
上一页
8.1.1 树 (Tree) 的定义
树的例子：家族树
? A 有子女 B,C； B 和 C 分别有子女 D,E,F 和 G,H;
? E有子女 I,J。
? T = (N,R),其中
? N={A,B,C,D,E,F,G,H,I,J}
? R={< A,B>,< A,C>,< B,D>,< B,E>,< B,F>,
? < C,G>,< C,H>,< E,I>,< E,J> }
? 关系有层次性，总是高层与低层相关，同层之间无关，
也没有低层到高层的关系。与不同元素相关的元素也
互不相交。
返回本章首页
下一页
上一页
树的表示方法：
返回本章首页
下一页
上一页
返回本章首页
下一页
上一页
树的递归定义：
树是 n (n≥ 0) 个结点的有限集 T。当 T非空时，满足：
1,有且仅有一个特别标出的称为根的结点 r；
2,除根结点外，其余结点可分为 m（ m >= 0）个互不
相交非空的有限集 T1,T2,…,Tm,其中每一个集
合本身又是一棵非空树，称为根 r 的子树 (subtree)。
? 空树：结点数为 0 的树。
? 树可以没有子树（ m = 0）
返回本章首页
下一页
上一页
8.1.2 基本术语
(a) 树 t (b) 树 t '
有序树 和 无序树,树中的子树的顺序是否重要
返回本章首页
下一页
上一页
父结点，子结点，边
兄弟结点
祖先，子孙
路径，路径长度
结点的层数（根的层为 0）
深度或高度（结点的最大层数）
结点的度数、树的度数
树叶、分支结点
结点的次序（最左,… ）
返回本章首页
下一页
上一页
8.1.3 树林
树林, m（ m≥ 0）棵互不相交的树的集合
一棵非空树是二元组 Tree = (root,F),其中 root是
树根
结点,F 是 m（ m≥ 0）棵子树构成的树林。
F=(T1,
T2,…,Tm) 。 Ti 称作根 root 的第 i 棵子树。
注意树与树林的关系：
? 树由根和子树 树林 组成
? 树林由一集树组成
返回本章首页
下一页
上一页
8.1.4 树的基本运算
抽象运算（操作）
?创建空树
Tree createTree(Node p,Tree t1,Tree t2,…,Tree ti )
i = 1,2,3,…
?判断某棵树是否为空
int isNull ( Tree t )
?求树中的根结点，若为空树，则返回特殊值
Node root ( Tree t )
?求指定结点的父结点，当结点是树根时返回特殊值
Node parent ( Node p )
返回本章首页
下一页
上一页
? 求树中某个指定结点的最左子结点，当指定结点为
树叶时返回特殊值
Tree leftChild ( Tree t )
? 求树中某个指定结点的右兄弟结点，当指定结点没
有右兄弟时返回特殊值
Tree rightSibling ( Tree t,Tree child )
? 树的 周游,按某种系统方式访问树中的所有结点，
每个结点恰好访问一次。
返回本章首页
下一页
上一页
8.1.5 树的周游
1,周游,按某种规律系
统地访问树中所有结
点，每个结点恰好访
问一次的过程。
2,周游方法：按深度周
游和按宽度周游。
(I) 按深度（以图为例）
a,先根序
1）访问根结点；
2）从左到右按先根次序周游根结点的每棵子树
1,2,3,5,8,9,6,10,4,7
返回本章首页
下一页
上一页
b,中根序
1）按中根次序周游根结点
的最左子树；
2）访问根结点；
3）从左到右按中根次序周
游根结点的其它各子树。
2,1,8,5,9,3,10,6,7,4
c,后根序
1）从左到右按后根次序周游
根结点的每棵子树 ;
2）访问根结点。
2,8,9,5,10,6,3,7,4,1
返回本章首页
下一页
上一页
（ II） 按宽度（层次）周游
先访问层数为 0的结点，然后
从左到右逐个访问层数为 1的
结点，依此类推，直到访问
完树中全部结点。
1,2,3,4,5,6,7,8,9,10
返回本章首页
下一页
上一页
先根序周游的非递归算法
void preOrder( Tree t ) {
Tree c = leftChild ( t );
visit ( root( t ) );
while ( !Null ( c ) ) {
preOrder ( c );
c = rightSibling ( t,c );
}
}
返回本章首页
下一页
上一页
先根序周游的非递归算法
void npreOrder ( Tree t ) {
PSeqStack s = createEmptyStack ( );
Tree c = t;
do {
while ( !Null ( c ) ) {
visit ( c ); push ( s,c );
c = leftChild ( t,c );
}
while ( Null ( c ) && !isEmptyStack (s)) {
c = rightSibling ( t,top (s) );
pop (s);
}
} while( !Null ( c ) );
}
返回本章首页
下一页
上一页
void inOrder( Tree t ) { /*中根序周游 */
Tree c = leftChild ( t );
if ( !Null ( c ) ) inOrder( c );
visit( root( t ) );
if ( !Null ( c ) )
while ( !Null(c = rightSibling (t,c )) )
inOrder ( t,c );
}
void postOrder( Tree t ) { /*后根序周游 */
Tree c = leftChild (t,p);
while ( !Null ( c ) ) {
postOrder ( c );
c = rightSibling (t,c);
}
visit( root( t ) );
｝
返回本章首页
下一页
上一页
void levelOrder( Tree t) {
PSeqQueue q = createEmptyQueue( );
Tree c = t;
if ( Null(c) ) return;
enQueue_seq(q,c);
while (!isEmptyQueue (q)) {
c = frontQueue (q);
deQueue (q);
visit( root( c ) );
c = leftChild (t,c);
while ( !Null(c) ) {
enQueue (q,c);
c = rightSibling ( t,c );
}
}
}
返回本章首页
下一页
上一页
8.1.6 树林的周游
是其中的树的周游的总和
1,先根（ A,B,C,K,D,E,H,F,J,G )
2,后根 ( B,K,C,A,H,E,J,F,G,D )
返回本章首页
下一页
上一页
8.2 树和树林的存储表示
8.2.1 树的存储表示
8.2.2 树林的存储表示
返回本章首页
下一页
上一页
8.2.1 树的存储表示
父指针表示法
子表表示法
长子 -兄弟表示法
返回本章首页
下一页
上一页
父指针表示法
用一组连续空间存储树中结点，每个结点设一个指示器，指示其双
亲结点（父结点）的位置。
typedef struct ParTreeNode { /* 树结点结构 */
DataType info; /* 结点中的数据 */
int parent; /* 结点的父结点位置 */
} ParTreeNode;
typedef struct ParTree {
int n; /* 树中结点个数 */
ParTreeNode nodelist[MAXNUM]; /* 树中结点 */
} ParTree,*PParTree;
返回本章首页
下一页
上一页
优点,a) 容易找到父结点及所有祖先；
b) 能找到结点的子女和兄弟（穷尽）；
缺点,a) 没表示出结点之间的左右次序；
b) 找结点的子女和兄弟比较费事。
改进方法：
按某种周游次
序在数组中存
放结点。常见
的方法是按先
根序存放树中
结点，如图：
返回本章首页
下一页
上一页
返回本章首页
下一页
上一页
子表表示法
结点表中每个元素包含一个子表，存放该结点的所有子结点。结
点表顺序存放，子表用链接表示。
struct EdgeNode { /* 子表中节点的结构 */
int nodeposition;
struct EdgeNode *link;
};
typedef struct ChiTreeNode { /* 结点表中节点结构 */
DataType info;
struct EdgeNode *children;
} ChiTreeNode;
}
返回本章首页
下一页
上一页
子表表示的树结构定义如下：
typedef struct ChiTree { /* 树结构 */
struct ChiTreeNode nodelist[MAXNUM];
int root; /* 根结点的位置 */
int n; /* 结点的个数 */
} ChiTree,* PChiTree;
返回本章首页
下一页
上一页
长子 -兄弟表示法
除信息域外，增加指向其最左子女和右兄弟的指针。
typedef struct CSNode *PCSNode; /* 结点指针 */
typedef struct CSNode { /* 结点结构 */
DataType info; /* 结点中的元素 */
PCSNode lchild; /* 结点的最左子女的指针 */
PCSNode rsibling; /* 结点的右兄弟的指针 */
} CSNode; /* 结点类型 */
typedef struct CSNode *CSTree; /* 树类型定义 */
返回本章首页
下一页
上一页图 8.7 树的长子兄弟表法
找长子或者右兄弟都比较简单
找父结点很困难（可以增加父
指针）
返回本章首页
下一页
上一页
8.2.2 树林的存储表示
是树表示法的变形：
,父指针表示法
,子表表示法
,长子 -兄弟表示法
返回本章首页
下一页
上一页
树林的父结点表示方法
返回本章首页
下一页
上一页
树林的子表表示法
返回本章首页
下一页
上一页
树林的长子兄弟表示法
返回本章首页
下一页
上一页
8.3 二叉树
8.3.1 二叉树的基本概念
8.3.2 二叉树的性质
8.3.3 二叉树的基本运算
8.3.4 二叉树的周游
8.3.5 树、树林与二叉树的转换
返回本章首页
下一页
上一页
8.3.1 二叉树的基本概念
二叉树：
结点的有限集，或为空集，或由一个根及两棵不相交
的二叉树组成。
两棵子树分别称作根的, 左子树, 和, 右子树, 。
,二叉树中结点至多有两棵子树，子树有 左右 之分。
,与树不同。
返回本章首页
下一页
上一页
二叉树的基本形态：
返回本章首页
下一页
上一页
二叉树不是树的特殊情形，它们是不同的两个概念。
树和二叉树之间主要差别是：二叉树结点的子树分为
左子树和右子树，即使在结点只有一棵子树的情况下
也要明确指出该子树是左子树还是右子树。
下面是两棵不同的二叉树，但作为树是相同的。
在二叉树中可定义与树中类似的各种概念。
返回本章首页
下一页
上一页
满二叉树：每个非叶结
点都有两棵非空子树
完全二叉树：每层结点
都满，只有最下一层右
边可缺
返回本章首页
下一页
上一页
8.3.2 二叉树的一些性质
性质 1,在非空二叉树第 i 层上至多有 2i 个结点 (i≥ 0)。
性质 2,深度为 k 的二叉树至多有 2k+1-1 个结点 (k ≥ 0)。
性质 3,对任何非空二叉树 T，如果叶结点个数为 n0，度为 2 的
结点个数为 n2，则 n0 = n2 + 1。
性质 4,n 个结点的完全二叉树的深度 k 为 log2n,
性质 5,（完全二叉树）如果 n 个结点的完全二叉树按层次序
从 1 开始编号，对任一结点 i（ 1 ≤ i≤ n) 都有：
1,序号 1的结点是根； i > 1时其双亲结点是 ∟ i/2 」 。
2,如果 2i ≤ n，其左子女结点序号为 2i。否则无左子女。
3,如果 2i+1 ≤ n，其右子女结点序号为 2i+1; 否则没有右子女。
返回本章首页
下一页
上一页
A B C D E F G A B C D E F G H
1 2 3 4 5 6 7 1 2 3 4 5 6 7 8
如果完全二叉树中的结点从 0 开始编号，也有类似性质：
1,序号 0 的结点为根；
2,非根结点 i 的父结点编号是 ∟ (i – 1)/2 」 ；
3,结点的两个子结点（若存在）的编号分别为 2i+1和 2i+2。
完全二叉树的信息可以方便地存入一系列连续位置中。
返回本章首页
下一页
上一页
8.3.3 二叉树的基本运算
? 创建一棵空二叉树；
? 判断二叉树是否为空；
? 求二叉树的根结点，若为空，则返回一特殊值；
? 求二叉树中某个指定结点的父结点，当指定结点为根时，
返回一特殊值；
? 求二叉树中某个指定结点的左子女结点，当指定结点没有
左子女时，返回一特殊值；
? 求二叉树中某个指定结点的右子女结点，当指定结点没有
右子女时，返回一特殊值；
? 二叉树的周游。
返回本章首页
下一页
上一页
8.3.4 二叉树的周游
二叉树的周游 (Traversing，遍历 )：按某种顺序访问二
叉树中所有结点，每个结点访问一次且仅一次。
三种基本方式：
先根次序 (DLR)
对称序 (LDR)
后根次序 (LRD)
返回本章首页
下一页
上一页
先根次序
A B D C E G F H I
后根次序
D B G E H I F C A
对称序（中根次序）
D B A E G C H F I
返回本章首页
下一页
上一页
二叉树的周游算法
/* 二叉树的先根序（先序）周游 */
void preOrder( BNode p) {
if (p==NULL) return;
visit(p); preOrder(leftChild(p)); preOrder(rightChild(p));
}
/* 二叉树的中根序（中序）周游 */
void inOrder(BNode p) {
if (p == NULL) return;
inOrder(leftChild (p)); visit(p); inOrder(rightChild (p));
}
/* 二叉树的后根序（后序）周游 */
void postOrder(BNode p) {
if (p == NULL) return;
postOrder(leftChild (p)); postOrder(rightChild (p)); visit(p);
}
返回本章首页
下一页
上一页
8.3.5 树、树林与二叉树的转换
树、树林转换为二叉树。步骤：
1,在所有相邻的兄弟结点之间连一条线；
2,对每个非终端结点，只保留它到其最左子女的连
线，删去它与其它子女的连线；
3,以根结点为轴心，旋转整棵树。
返回本章首页
下一页
上一页
二叉树转换为树、树林。步骤：
1,若某结点是其父母的左子女，则把该结点的右子女，
右子女的右子女,… 都与该结点的父母连线；
2,去掉原二叉树中所有父母到右子女的连线。
返回本章首页
下一页
上一页
8.4 二叉树的存储表示
8.4.1 顺序表示
8.4.2 链接表示
8.4.3 二叉树的生成
返回本章首页
下一页
上一页
8.4.1 顺序表示
用一组连续存储单元按
层次序存储完全二叉树
的结点。
可以方便地从子结点找
父结点，从父结点找子
结点。
一般二叉树，可将其结点对应到完全二叉树后存储入一维数组。
用顺序方式存储非完全二叉树时，可能出现大量空位，可能浪费
大量存储空间。
返回本章首页
下一页
上一页
8.4.2 链接表示
typedef struct BNode BNode,*PBNode; /* 类型 */
struct BNode {/*二叉树结点 */
DataType info; /* 数据域 */
PBNode llink; /* 指向左子女 */
PBNode rlink; /* 指向右子女 */
};
typedef struct BNode *BinTree;
typedef BinTree *PBinTree;
返回本章首页
下一页
上一页
返回本章首页
下一页
上一页
8.4.3二叉树的生成
创建二叉树与表示方式有关。
采用顺序表示时，只需把二叉
树扩充为完全二叉树（用某种
特殊符号表示没有结点），采
用层次方式列出完全二叉树，
读入并装入数组。
创建链接表示的二叉树，设计线性输入方式（一种设计）：
? 按先序周游顺序给出结点序列
A B D C E G F H I
? 加入空二叉树信息（以方便二叉树构造），例如用 @
A B D @ @ @ C E @ G @ @ F H @ @ I @ @
返回本章首页
下一页
上一页
/* 递归地创建二叉树 */
PBinTreeNode create_BTree() {
PBinTreeNode pbnode;
char ch;
scanf(" %c",&ch);
if (ch == '@') return NULL;
pbnode = (PBinTreeNode )malloc(sizeof(BinTreeNode));
if ( pbnode == NULL ) {
printf("Out of space!\n");
return NULL;
pbnode->info = ch;
pbnode->llink = create_BTree(); /* 构造左子树 */
pbnode->rlink = create_BTree(); /* 构造右子树 */
return pbnode;
}
返回本章首页
下一页
上一页
8.5 哈夫曼算法及其应用
8.5.1 哈夫曼树
8.5.2 哈夫曼 (Huffman)算法
8.5.3 哈夫曼编码
哈夫曼树可以看作二叉树的一种应用
哈夫曼编码在信息领域有重要价值，讨论一组信息的最短
编码
问题。
返回本章首页
下一页
上一页
8.5.1 哈夫曼树
设有一集实数 {w1,w2,w3,…,wm},要构造一棵扩充二叉树，其
中包含 m个分别以 wi（ i = 1,2,…, m）为权的外部结点。要求带权
外部路径长度 WPL最小。这样的扩充二叉树称为哈夫曼树或最优二
叉树。
例如,{ 2,3,4,11}
返回本章首页
下一页
上一页
8.5.2 哈夫曼算法
1,用给定的 m 个权值 {w1,w2,…,wm} 构造 m 棵二叉树
的集合 F = {T1,T2,…,Tm},其中每棵二叉树 Ti中只
有一个带权为 wi的根结点，根结点权值为 wi ；
2,在 F中选取两棵权值最小的树作为左右子树，构造
一棵新的二叉树，新二叉树的根结点的权值为其左
右子树根结点权值之和；
3,从 F删除所选的两棵树，把新构造的二叉树加入 F；
4,重复（ 2）和（ 3），直到 F中只含一棵树为止。
返回本章首页
下一页
上一页
哈夫曼 (huffman)算法的实现
存储结构：
typedef struct HtNode { /* 哈夫曼树结点的结构 */
int ww;
int parent,llink,rlink;
} HtNode;
typedef struct HtTree { /* 哈夫曼树定义 */
HtNode ht[MAXNODE];
int root; /* 哈夫曼树根在数组中的下标 */
} HtTree,*PHtTree;
返回本章首页
下一页
上一页
/* 构造具有 m 个叶结点的哈夫曼树 */
PHtTree huffman(int m,int *w) {
PHtTree pht = initHFT(m,w); int i,j,x1,x2,m1,m2;
if (pht == NULL) return NULL;
for ( i = 0; i < m - 1; i++) {/* 每次循环构造一个内部结点 */
m1 = m2 = MAXINT; x1 = x2 = -1; /* 变量赋初值 */
for (j = 0; j < m+i; j++) {/* 找两个最小权的无父结点的结点 */
HtNode *p = &(pht->ht[j]); /* 考察一个结点 */
if (p->parent == -1) {
if (p->ww < m1) { m2 = m1; x2 = x1; m1 = p->ww; x1 = j; }
else if (p->ww < m2) { m2 = p->ww; x2 = j; }
} }
pht->ht[x1].parent = pht->ht[x2].parent = m+i; /* 构造一个内部
结点 */
pht->ht[m+i].ww = m1 + m2;
pht->ht[m+i].llink = x1; pht->ht[m+i].rlink = x2;
pht->root = m+i;
} return pht; }
返回本章首页
下一页
上一页
/* 初始化 Huffman 树数据结构 */
PHtTree initHFT (int m,int *w) {
int i;
PHtTree pht = (PHtTree)malloc(sizeof(struct HtTree));
if (pht == NULL) {
printf("Out of space!! \n");
return NULL;
}
for (i = 0; i < 2*m-1; i++) {/* 置初态 */
HtNode *p = &(pht->ht[i]);
p->llink = p->rlink = p->parent = -1;
p->ww = (i < m)? w[i], -1;
}
return pht;
}
返回本章首页
下一页
上一页
8.5.3 哈夫曼编码
设有如下基本数据：
D={d1,d2,…,dn }
W={w1,w2,…,wn }
D为需要编码的字符集,W为 D中各字符出现的频率
要求：（ 1）编码总长最短；
（ 2）若 di≠ dj,di编码不是 dj编码的前缀。
返回本章首页
下一页
上一页
通过构造哈夫曼树，实现哈夫曼编码：
以 d1,d2,…,dn 为外部结点,w1,w2,….,wn 作为外部结点
的权，构造哈夫曼树。
在哈夫曼树中，所有从一个结点引向其左子女的边标 0；
引向其右子女的边上标 1。
从根结点到叶子结点的路径上的数字拼接起来就是这
个叶子结点字符的编码。
可以证明：对于 D和 W，这样得到的哈夫曼编码是最优
（最短）编码。
返回本章首页
下一页
上一页
w = {2,3,5,7,11,13,17,19,23,29,31,37,}
