Data Structure LXJ
第 7 章树 和 二叉树西南科技大学 计算机学院信息教研室
Data Structure LXJ
内容提纲
7.1 仿真指针
7.2 树
7.3 二叉树
7.4 链式存储结构的二叉树设计
7.5 二叉树遍历游标类
7.6 线索二叉树
7.7 堆
7.8 哈夫曼树
Data Structure LXJ
第一部分仿真指针
Data Structure LXJ
7.1仿真指针
A）常规链表：链式存储实现，使用指针
a1 a2 a3 a4 ^head a0
2a3
4a2
－ 1a4
3a1
1a00
2
3
1
4
data next
B）
静态链表：顺序存储实现 (数组 ),使用仿真指针
Data Structure LXJ
第二部分树
Data Structure LXJ
7.2.1 树的定义树 tree的递归定义：
树 (tree)是 n个数据元素的有限集 (记为 T)，对任意一棵树 T有：
1,存在唯一一个称为 根 (root) 的数据元素；
2,当 n＞ 1时，其它数据元素可分为 m(m＞ 0) 个互不相交的有限集 T1,T2,…,Tm，其中每个集合 Ti(i=1,2,…,m)本身又是一棵树，并称树 Ti是根的 子树 (subtree).
A
B C
D E F G
A(空树 )
（ a） （ b） （ c）
Data Structure LXJ
树的结点（ Node）
根结点、叶结点、分支结点、孩子结点、双亲结点、兄弟结点、
祖先结点、子孙结点
Data Structure LXJ
结点的度、树的度
A
B C D
E F G H I J
K L M
······················根 3度
········叶 0度
2个 3度点 A,D
2个 2度点 B,E
2个 1度点 C,H
7个叶 F,G,I,J,K,L,M
树的度,树中所有结点的度的最大值。
上图：树的度为 3
Data Structure LXJ
结点的层次、树的深度树的深度为 4
A
B C D
E F G H I J
K L M
·············································第一层
······························第二层
···············第三层
····································第四层
Data Structure LXJ
序树、森林
无序树：树中任意一个结点的各个子树之间的次序构成无关紧要，交换树中任意一个结点的各个子树的次序均和原树相同的树构成无序树。
有序树：树中任意一个结点的任意子树都是有次序的树。
森林,m颗树的集合称为森林。
A
B C
D E F G
A
森林
A
B C
Data Structure LXJ
7.2.2 树的表示方法
1,树的直观表示法
A
B C
D E F G
Data Structure LXJ
树的形式化表示法主要用于树理论描述。
T = (D,R)
T为树,D表示树的结点,R为结点之间的关系的集合
为空树时,D =?
非空时,D = {Root}? F （ Root：根结点,F森林）
F = T1? T2? T3 …? Tm （ Ti：子树）
R = {<Root,Rooti>,I = 1,2,3…m} （ Root：根结点、
Rooti,i子树的根结点,<Root,Rooti> 表示了父子关系）
树的形式化表示法
A
B C
D E F G
Data Structure LXJ
树的凹入表示法
A）常规表示
A
B C
D E F G
A
B
C
D
E
D
E
B）凹入表示
Data Structure LXJ
树的集合表示
A
B C
D E F G
A）常规表示
D E F G
B C
A
B）集合表示
C）广义表表示
（ A（ B（ D,E）,C（ F,G） ） ）
Data Structure LXJ
7.2.3 树的基本操作
树是非线性结构，结点之间的关系较线性结构复杂。
数据成员：根节点指针，当前节点指针第一类操作：
1,寻找根结点使之成为当前结点；
2,寻找当前结点的双亲结点使之成为当前结点；
3,寻找当前结点的孩子结点使之成为当前结点；
4,寻找当前结点的下一个兄弟结点使之成为当前结点。
Data Structure LXJ
树的基本操作第二类操作：
1,在树的当前结点上插入一个新结点，使新插入的结点成为当前结点的第 i个孩子结点；
2,删除树的当前结点的第 i个孩子结点；
3,在树的当前结点上插入一个新子树，使新子树成为当前结点的第 I棵子树；
4,删除树的当前结点的第 I棵子树。
Data Structure LXJ
树的基本操作第三类操作：
1,按某种方式遍历一棵树显示树中每个结点的数据域值；
2,按某种方式遍历一棵树寻找数据元素域为某一值的结点。
树的遍历操作指按某种方式访问树中每一个结点，
且每一个结点只被访问一次
遍历方式分为：
1,先根遍历
2,后根遍历
Data Structure LXJ
树的遍历
先根遍历：
1,访问根结点
2,按照从左到右次序先根遍历根结点的每一棵子树
A
B C D
E F G H I J
K L M
遍历次序,A B E K L F C G D H M I J
A
B C D
遍历次序,A B C D
Data Structure LXJ
树的遍历
后根遍历：
1,按照从左到右次序后根遍历根结点的每一棵子树
2,访问根结点
A
B C D
E F G H I J
K L M
遍历次序,K L E F B G C M H I JD A
A
B C D
遍历次序,B C D A
层次遍历
Data Structure LXJ
7.2.4 树的存储结构
计算机中树的存储既要求存储数据，又要求存储关系，但关系复杂
常见几种存储结构
1,双亲表示法
2,孩子表示法
3,双亲孩子表示法
4,孩子兄弟表示法
Data Structure LXJ
双亲表示法
双亲表示法每个结点有两个域：
1,data：数据元素域
2,parent：指示其双亲结点的指针域
A
B C
D E F G
IH
a）一棵树
4I
4H
2G
1F
1E
1D
0C
0B
-1A
下标 data parent
8
7
6
5
4
3
2
1
0
b）双亲表示法仿真指针存储结构
Data Structure LXJ
孩子表示法
孩子表示法每个子树个数（即结点的度）不同，每个结点的孩子结点指针域不同，为了方便，定义结点孩子指针域个数为树的度：
1,data：数据元素域
2,children[]：指示其孩子结点的指针域
A
B C
D E F G
IH
a）一棵树 b）树的常规指针的孩子表示法
A
CB
FDG?E
GI
root
Data Structure LXJ
双亲孩子表示法
双亲孩子表示把双亲表示法和孩子表示法结合起来的兼具两种存储结构的优点。
A
B C
D E F G
IH
a）一棵树 b）双亲孩子表示法的一种结构
4I8
4H7
2G6
1F5
1E4
1D3
0C2
0B1
-1A0
下标 data parent children
1 2?
3 4
6?
5?
7 8?
Data Structure LXJ
孩子兄弟表示法
孩子兄弟表示为每个结点设计三个域：
1,data：数据元素域
2,firstChild：该结点的第一个孩子指针
3,nextSibling：该结点的下一个兄弟指针
a）一棵树 b）孩子兄弟表示法
A
B C
D E F G
IH
A?
B C?
D E? F G?
H? I?
root
Data Structure LXJ
7.2.5 树类的抽象
树抽象用得最多的一种表示法：孩子兄弟表示法，
抽象过程分为两步
1,结点的抽象
2,树的抽象
Data Structure LXJ
树类－ 结点定义
firstChild data nextSibling
#include <stdlib.h>
template <class T> class Tree;
template<class T> class TreeNode
{
friend class Tree<T>; //树类为友元
private:
TreeNode<T>* firstChild; //第一个孩子结点指针域
TreeNode<T>* nextSibling; //下一个兄弟结点指针域
public:
T data; //数据域
…
Data Structure LXJ
…
//构造函数
TreeNode(T value,TreeNode<T> *fc =NULL,
TreeNode<T> *ns = NULL)
:data(value),firstChild(fc),nextSibling(ns){}
//访问指针域的成员函数
TreeNode<T>* &FirstChild(void)
{
return firstchild;
}
TreeNode<T>* &NextSlibling(void)
{
return nextSibling;
}
};
树类－ 结点定义
Data Structure LXJ
template <class T> class Tree
{
private:
//数据成员
TreeNode<T>* root; //根结点指针
TreeNode<T>* current; //当前结点指针
//私有成员函数
void PreOrderTree(TreeNode<T>*& t);
void PostOrderTree(TreeNode<T>*& t);
int Current(TreeNode<T>*& t);
//在树 root中回溯查找结点 s的双亲结点
TreeNode<T>* SerchParent(TreeNode<T>*& root,
TreeNode<T>*& s);
…
树类定义
Data Structure LXJ
…
public:
Tree() //构造函数
{ root = current = NULL;
};
~Tree() //析构函数
{
DeleteSubTree(root);
};
int Root(); //使根结点为当前结点
int Parent(); //使当前结点的双亲结点为当前结点
int FirstChild(); //使当前结点的第一个孩子结点为当前结点
int Nextsibling();//使当前结点的兄弟结点为当前结点
…
第一类操作的成员函数构造函数和析构函数树类定义
Data Structure LXJ
public:
…
//第二类操作的成员函数
void InsertChild(T value);
//把 value值插入到当前结点的最后一个结点
void DeleteSubTree(TreeNode<T>*& t);
//删除以 t为根结点的子树
int DeleteChild(int i); //删除当前结点的第 i个孩子结点
//第三类操作的成员函数
void DisplayTree();//按先根遍历次序显示树的数据域值
};
树类定义
Data Structure LXJ
树类实现－ 构造函数和析构函数
A
B C D
E F
A?
B
E? C
D F?
root
Tree() //构造函数
{
root = current = NULL;
};
~Tree() //析构函数
{
DeleteSubTree(root);
};
Data Structure LXJ
template <class T>
void Tree<T>::DeleteSubTree(TreeNode<T>*& t)
{
if(t == NULL) return;
TreeNode<T>* q = t->firstChild,*p;
while(q != NULL)
{
p = q->nextSibling;
DeleteSubTree(q);
q = p;
}
delete t;
}
A?
B
E? C
D F?
root
树类实现－ 删除以 t为根结点的子树
Data Structure LXJ
template <class T>
int Tree<T>::Current(TreeNode<T>*& t) //当前节点为是 t所指节点
{
if(t == NULL) return 0;
current = t;
return 1;
}
A?
B
E? C
D F?
root
树类实现－ 第一类操作
Data Structure LXJ
template <class T>
int Tree<T>::Root()
{
if(root == NULL)
{
current = NULL;
return 0;
}
return Current(root);
}
A?
B
E? C
D F?
root
树类实现－ 第一类操作
Data Structure LXJ
template <class T>
int Tree<T>::FirstChild()
{
if(current != NULL && current->firstChild !=
NULL)
return Current(current->firstChild);
else
return 0;
}
A?
B
E? C
D F?
root
树类实现－ 第一类操作
Data Structure LXJ
template <class T>
int Tree<T>::Nextsibling()
{
if(current != NULL && current->nextSibling != NULL)
return Current(current->nextSibling);
else
return 0;
}
A?
B
E? C
D F?
root
树类实现－ 第一类操作
Data Structure LXJ
template <class T>
int Tree<T>::Parent()
// 使当前结点的双亲结点为当前结点
{
if(current == NULL)
{
current = root;
return 0;
}
TreeNode<T>* p = SerchParent(root,current);
if(p == NULL) return 0;
else return Current(p);
}
A?
B
E? C
D F?
root
树类实现－ 第一类操作
Data Structure LXJ
template <class T>
TreeNode<T>* Tree<T>::SerchParent(TreeNode<T>*
&root,TreeNode<T>*& s)// 在树 root中回溯查找结点 s的双亲结点
//查找到时时 current指向 s结点的双亲结点
{
if(root == NULL) return NULL;
if(root -> FirstChild() == s|| root->NextSibling() == s)
return root;
TreeNode<T>* p;
if((p = SearchParent(root->FirstChild(),s)) != NULL) return p;
if((p = SearchParent(root->NextSibling(),s)) != NULL) return p;
return NULL; //失败时返回空使算法回溯
}
树类实现－ 第一类操作
Data Structure LXJ
树类实现－ 第二类操作
template <class T>
void Tree<T>::InsertChild(T value)
// 把 value值插入到当前结点的最后一个结点
{
//建立数据域值为 value的结点由 newNode指针指示
TreeNode<T>* newNode = new TreeNode<T>(value);
if(root == NULL) //当为空时
{
root = current = newNode;
return;
}
if(current->firstChild == NULL)
current->firstChild = newNode;
。。。
A?
B
E? C
D F?
root
Data Structure LXJ
。。。
else
{
TreeNode<T> *p = current->firstChild;
while(p->nextSibling != NULL) p = p->nextSibling;
p->nextSibling = newNode;
}
Current(newNode);
}
A?
B
E? C
D F?
root
树类实现－ 第二类操作
Data Structure LXJ
template <class T>
int Tree<T>::DeleteChild(int i) // 删除当前结点的第 i个孩子
{
TreeNode<T> *r = NULL;
//当删除当前结点的第一棵子树时
if(i = 1)
{
r = current->firstChild;
if(r == NULL) return 0; //要删除的子树为空，返回
current ->firstChild = r->nextSibling; //脱链要删除的子树
}
。。。
树类实现－ 第二类操作
Data Structure LXJ
template <class T>
int Tree<T>::DeleteChild(int i) // 删除当前结点的第 i个孩子
{
。。。//当删除当前结点的其他子树时
else
{
int k = 1;
TreeNode<T> *p = current->firstChild;
while(p != NULL && k <= i-1) //寻找指向要删除子树的指针
{
p = p->nextSibling;
k++;
}
。。。
}
。。。
}
A?
B
E? C
D F?
root
树类实现－ 第二类操作
Data Structure LXJ
template <class T>
int Tree<T>::DeleteChild(int i) // 删除当前结点的第 i个孩子
{
。。。
//当删除当前结点的其他子树时
else
{ 。。。
if(p != NULL) //所寻找的指向要删除子树的指针找到
{
r = p->nextSibling;
if(r != NULL) //脱链要删除的子树
p->nextSibling = r->nextSibling;
else return 0; //要删除子树为空返回
}
else return 0; //所寻找的指向要删除子树的指针找到
}
DeleteSubTree(r); //删除找到要删除的子树
return 1; //删除成功
}
树类实现－ 第二类操作
Data Structure LXJ
树类实现－ 第三类操作
template <class T>
void Tree<T>::PreOrderTree(TreeNode<T> *& t)
{
if(t == NULL) return;
cout << t->data << " "; //显示根结点数据
if(t->firstChild != NULL) //先根遍历子树
PreOrderTree(t ->firstChild);
if(t->nextSibling != NULL)
PreOrderTree(t ->nextSibling);
}
A?
B
E? C
D F?
root
Data Structure LXJ
树类实现－ 第三类操作
template <class T>
void Tree<T>::PostOrderTree(TreeNode<T> *& t)
{
if(t == NULL) return;
if(t->firstChild != NULL) //后根遍历子树
PostOrderTree(t ->firstChild);
cout << t->data << " "; //显示根结点数据
if(t->nextSibling != NULL)
PostOrderTree(t ->nextSibling);
}
A?
B
E? C
D F?
root
Data Structure LXJ
树类实现－ 第三类操作
template <class T>
void Tree<T>::PostOrderTree(TreeNode<T> *& t)
{
if(t == NULL) return;
if(t->firstChild != NULL) //后根遍历子树
PostOrderTree(t ->firstChild);
cout << t->data << " "; //显示根结点数据
if(t->nextSibling != NULL)
PostOrderTree(t ->nextSibling);
}
Data Structure LXJ
#include <iostream.h>
#include "Tree.h"
void main()
{
Tree<char> t;
t.InsertChild('A');
for(int i = 0;i < 3;i++)
{
t.Root();
t.InsertChild('B' + i);
}
。。。
}
Data Structure LXJ
#include <iostream.h>
#include "Tree.h"
void main()
{
。。。
for(i = 0;i < 2;i++)
{
t.Root();
t.FirstChild();
t.InsertChild('E' + i);
}
cout << "按先根遍历显示的结点次序为," << endl;
t.DisplayTree();
cout << endl << "析构函数按后根遍历释放结点的次序为," << endl;
}
Data Structure LXJ
二叉树
BinaryTree
第二部分
Data Structure LXJ
7.3.1 二叉树的定义
每个结点至多有两棵子树,1度或 2度
每个结点分左子树（ 左孩子 ）、右子树（ 右孩子 ）
二叉树的 5种形态
A
B C
D E F G
H I J
A
B C
D E F G
H I J
a）二叉树 b） 度数为 2的有序树
Data Structure LXJ
特殊二叉树
满二叉树：所有分支结点都存在左子树和右子树，且叶子结点在同一层，称满二叉树。 深度为 k,结点数 2k-1,每层结点数都最大
完全二叉树,满二叉树去掉最下层最右边若干结点
满二叉树也是完全二叉树
A
B C
D E F G
H I J K L M N O
A
B C
D E F G
H I J K
a）满二叉树 b）完全二叉树
Data Structure LXJ
7.3.2 二叉树的性质
性质 1 若规定根结点的层次是 0，则一颗非空二叉树第 i层上的结点数目最多为 2i(i≥0)。
A
B C
D E F G
H I J K L M N O
第 0层第 1层第 2层第 3层
Data Structure LXJ
二叉树的性质
性质 2 若规定空树的深度为 -1,深度为 k的二叉树至多有 2k+1-1个结点 (k≥-1)。
A
B C
D E F G
H I J K L M N O
第 0层第 1层第 2层第 3层
Data Structure LXJ
二叉树的性质
性质 3 在任意 -棵二叉树中，若终端结点的个数为 n0，度为 2
的结点数为 n2，则 no=n2+1。
证明,因为二叉树中所有结点的度数均不大于 2，所以结点总数 (记为 n)应等于 0度结点数,1度结点 (记为 n1)和 2度结点数之和：
n=no+n1+n2 (式子 1)
另一方面,1度结点有一个孩子,2度结点有两个孩子，故二叉树中孩子结点总数是：
nl+2n2
树中只有根结点不是任何结点的孩子，故二叉树孩子结点总数又可表示为,n-1
n-1=n1+2n2 (式子 2)
由式子 1和式子 2得到：
no=n2+1
A
B C
D E F
Data Structure LXJ
二叉树的性质
性质 4 具有 n个结点的完全二叉树的深度为不超过
k = log2(n+1) - 1的最大整数第 1个结点深度为?log21+1? - 1 = 0
第 2-3个结点深度为?log22+1? - 1 = 1
第 4-7个结点深度为?log24+1? - 1 = 2
第 8-15个结点深度为?log28+1? - 1 = 3
1
2 3
4 5 6 7
8 9 10 11 12 13
Data Structure LXJ
二叉树的性质
性质 5,若将一棵具有 n个结点的完全二叉树按层次次序从 0开始编号，则对任意编号为 n的结点有：
1,若 i〉 1，则编号为 i的结点的父结点的编号为 (i-1)/2
2,若 2i+1<n，则编号为 i的结点的左孩子结点编号为 2i+1，
否则 i无左孩子。
3,若 2i+2<=n，则结点 i的右孩子结点编号为 2i+2，否则 i无右孩子。 1
2 3
4 5 6 7
8 9 10 11 12 13
1,结点 i的左孩子结点是 2i
2,右孩子结点是 2i+1
3,结点 i的父结点是?i/2?
Data Structure LXJ
7.3.3 二叉树的操作
二叉树操作和树操作基本相同，
二叉树 =根结点 +左子树 +右子树
第一类操作 （找某种满足某种特定关系的节点）
1,寻找根结点使之成为当前结点
2,寻找当前结点的双亲结点使之成为当前结点
3,寻找当前结点的左孩子使之成为当前结点
4,寻找当前结点的右孩子使之成为当前结点
Data Structure LXJ
二叉树的操作
第二类操作,（插入和删除）
1,在二叉树的当前结点上插入一个新结点，使新插入结点成为当前结点的左孩子结点
2,在二叉树的当前结点上插入一个新结点，使新插入结点成为当前结点的右孩子结点
3,在二叉树的当前结点上插入一个子树，使新插入子树成为当前结点的左子树
4,在二叉树的当前结点上插入一个子树，使新插入子树成为当前结点的右子树
5,删除二叉树的当前结点的左孩子结点
6,删除二叉树的当前结点的右孩子结点
7,删除二叉树的当前结点的左子树
8,删除二叉树的当前结点的右子树
Data Structure LXJ
二叉树的操作
第三类操作，遍历二叉树,（遍历）
1,中序遍历（ LDR）二叉树
中序遍历根结点的左子树（ L）
访问根结点（ D）
中序遍历根结点的右子树（ R）
2,前序遍历（ DLR）二叉树
访问根结点（ D）
前序遍历根结点的左子树（ L）
前序遍历根结点的右子树（ R）
3,后序遍历（ LRD）二叉树
后序遍历根结点的左子树（ L）
后序遍历根结点的右子树（ R）
访问根结点（ D）
Data Structure LXJ
二叉树的遍历
LDR,D H B E A F I C G
DLR,A B D H E C F I G
LRD,H D E B I F G C A
层序遍历
A B C D E F G H I
A
B C
D E F G
H I
二叉树的前序遍历后中序遍历可以确定一颗二叉树
当规定了遍历方法后，二叉树也像单链表一样
一颗二叉树的遍历序列不能确定一颗二叉树
Data Structure LXJ
7.3.3 二叉树的存储结构
1,二叉树的顺序存储结构
A
B C
D E F
a）完全二叉树的存储 b）一般二叉树的存储
FEDCBA
543210
FED?CBA
6543210
A
B C
D E F
Data Structure LXJ
二叉树的存储结构
2,二叉树链式存储结构
leftChild data rightChild
A
B C
D E F A
B C
D E F?
root
a）二叉树结点结构 b）二叉树链式存储结构
1,优点,寻找孩子简单
2,缺点,寻找双亲麻烦
3,解决方法,用三叉链式存储代替二叉链式存储
Data Structure LXJ
二叉树的存储结构
3,二叉树仿真指针存储结构
A
B C
D E F
a）二叉树仿真指针存储结构下标 data leftChild rightChild
－ 1
1
－ 1
5
3
2
－ 1F
－ 1E
－ 1D
4C
－ 1B
1A
5
4
3
2
1
0
Data Structure LXJ
7.3.5 树和二叉树的转换
1,树转换为二叉树
a,树中所有相同双亲结点的兄弟之间加一条连线；
b,树中每个结点，保留它与第一个孩子之间的连线，删除与其他孩子之间的连线；
c,整理所有保留和添加的线，使结点孩子连线位于左孩子指针位置，使结点兄弟位于右孩子指针位置。
d,完毕,c图表示法 也即是 树的孩子兄弟表示法
A
B D
E F G
C
A
B D
E F G
C
A
B D
E F G
C
A
B
D
E
F
G
C
a） b） c）树
Data Structure LXJ
树和二叉树的转换
2,二叉树还原为树
a,若该结点是双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子 … 都与该结点的双亲结点连接起来；
b,删除原二叉树中所有双亲结点与右孩子结点的连线；
c,整理所有保留和添加的线，使每个结点的孩子结点连线顺序位于下方孩子结点位置。
A
B
D
E
F
G
C
A
B
D
E
F
G
C
A
B
D
E
F
G
C
A
B D
E F G
C
a） b） c） 树
Data Structure LXJ
7.4 链式存储结构的二叉树设计两种方法：
1。设计一个结点类，然后在结点类的基础上设计出需要实现的二叉树操作的函数。（通过外部函数）
优点：实现比较简单因为二叉树是一种递归定义，所以对结点的操作也能对二叉树操作。
缺点 （ 1）当二叉树结构比较复杂时，结点类不能够给出二叉树结点之间关系的成员函数；
（ 2）需要定义的结点类对像也会很多；
（ 3）用外部函数实现也不够规范。
Data Structure LXJ
7.4 链式存储结构的二叉树设计
2。在设计的节点类的基础上在设计一个二叉树类，二叉树类的成员函数包括了基本操作
Data Structure LXJ
7.4 链式存储结构的二叉树设计
#include <iostream.h>
#include <stdlib.h>
template <class T> class BiTreeNode
{
private:
BiTreeNode<T>* leftChild; //左子树指针
BiTreeNode<T>* rightChild; //右子树指针
public:
T data;
//构造函数和析构函数
BiTreeNode():leftChild(NULL),rightChild(NULL){}
BiTreeNode(T item,BiTreeNode<T>* left= NULL,
BiTreeNode<T>* right = NULL):
data(item),leftChild(left),rightChild(right){}
~BiTreeNode(){}
//结点操作的成员函数
BiTreeNode<T>*& Left(void){return leftChild;}
BiTreeNode<T>*& Right(void){return rightChild;}
};
Data Structure LXJ
7.4 链式存储结构的二叉树设计
//定义一个由结点构造二叉树的外部函数
template<class T>
BiTreeNode<T>* getTreeNode(Titem,
BiTreeNode<T> *left = NULL,
BiTreeNode<T>* right = NULL)
{
BiTreeNode<T>* p;
p = new BiTreeNode<T>(item,left,right);
if(p == NULL)
{
cerr << "内存分配失败！ \n";
exit(1);
}
return p;
}
A
B C
D E F
Data Structure LXJ
7.4 二叉树的遍历
template<class T>
void PreOrder(BiTreeNode<T>*& t,void visit(T item))
//使用 visit(item)函数前序遍历二叉树
{
if(root != NULL)
{
visit(t->data);
PreOrder(t->Left(),visit);
PreOrder(t->Right(),visit);
}
}
visit是函数参数。
A
B C
D E F
Data Structure LXJ
template<class T>
void InOrder(BiTreeNode<T>*& t,void visit(T item))
//使用 visit(item)函数中序遍历二叉树
{
if(t != NULL)
{
InOrder(t->Left(),visit);
visit(t->data);
InOrder(t->Right(),visit);
}
}
A
B C
D E F
7.4 二叉树的遍历
Data Structure LXJ
template<class T>
void PostOrder(BiTreeNode<T>*& t,void visit(T
item))
//使用 visit(item)函数后序遍历二叉树
{
if(t != NULL)
{
PostOrder(t->Left(),visit);
PostOrder(t->Right(),visit);
visit(t->data);
}
}
A
B C
D E F
7.4 二叉树的遍历
Data Structure LXJ
#include "LineQueue.h" //包含模板链式队列类
template<class T>
void LevelScan(BiTreeNode<T>*& t,void visit(T item))
//使用 visit(item)函数层序遍历二叉树
{
LinQueue<BiTreeNode<T>*> q; //定义模板链式队列类对象
BiTreeNode<T>* p;
q.QInsert(t); //根结点入队
while(!q.QueueEmpty())
{
p = q.QDelete(); //出队列
visit(p->data); //访问根结点
if(p->Left() != NULL) //根结点的左子树入队列
q.Qinsert(p->Left()); //根结点的右子树入队列
if(p->Right() != NULL)
q.Qinsert(p->Right());
}
}
A
B C
D E F
7.4 二叉树的遍历
Data Structure LXJ
计算二叉树的深度，叶子结点个数，查找元素，
分层显示二叉树结点数据域值两类：
1。不考虑遍历顺序
2。考虑遍历顺序
7.4 二叉树的遍历的应用
A
B C
D E F
Data Structure LXJ
template<class T>
int Depth(BiTreeNode<T>*& root)
//返回计算出的二叉树的深度
{
int depthleft,depthright,depthval;
if(root == NULL) depthval = 0;
else
{
depthleft = Depth(root->Left());
depthright = Depth(root->Right());
//二叉树的深度为左子树和右子树深度的最大值加根结点的深度值 1
depthval = 1 + (depthleft > depthright? depthleft,
depthright);
}
return depthval;
}
7.4 二叉树的遍历的应用
A
B C
D E F
Data Structure LXJ
template<class T>
int CountLeaf(BiTreeNode<T>*& root,int& count)
//计算二叉树 root的叶子结点个数并存与 count中
{
if(root != NULL)
{
CountLeaf(t ->Left(),count);
CountLeaf(t->Right(),count);
if(t->Left() == NULL && t->Right() == NULL)
count++;
}
}
7.4 二叉树的遍历的应用
A
B C
D E F
Data Structure LXJ
template<class T>
BiTreeNode<T>* Find(BiTreeNode<T>*& root,T item)
//在二叉树 root中回溯查找数据元素 item找到时返回该结点指针，
否则返回空
{
if(root == NULL) return NULL;
if(root->data == item || root->data == item)
return root;
BiTreeNode<T>* p;
if((p = Find(root->Left(),item)) != NULL) return p;
if((p = Find(root->Right(),item)) != NULL) return p;
return NULL;
}
7.4 二叉树的遍历的应用
A
B C
D E F
Data Structure LXJ
template<class T>
void PrintTree(BiTreeNode<T>*& root,int level)
//二叉树 root第 level层结点数据域值的横向显示
{
if(root != NULL)
{
//二叉树 root->Right()第 level+1层结点数据域值的横向显示
PrintTree(root->Right(),level + 1);
if(level != 0)
{
//走过 6 * (level - 1)个空格
for(int i = 0;i < 6 * (level - 1);i++) cout << " ";
cout << "----"; //显示横线 ----
}
cout << root-> data << endl; //显示结点的数据域值
//二叉树 root->Left()第 level+1层结点数据域值的横向显示
PrintTree(root->Left(),level + 1);
}
}
7.4 二叉树的遍历的应用
Data Structure LXJ
7.4 链式存储结构的二叉树设计两种方法：
1。设计一个结点类，然后在结点类的基础上设计出需要实现的二叉树操作的函数。（通过外部函数）
优点：实现比较简单因为二叉树是一种递归定义，所以对结点的操作也能对二叉树操作。
缺点 （ 1）当二叉树结构比较复杂时，结点类不能够给出二叉树结点之间关系的成员函数；
（ 2）需要定义的结点类对像也会很多；
（ 3）用外部函数实现也不够规范。
Data Structure LXJ
7.4 链式存储结构的二叉树设计
2。二叉树类在设计的节点类的基础上在设计一个二叉树类，二叉树类的成员函数包括了基本操作
Data Structure LXJ
7.4 链式存储结构的二叉树设计
#include <iostream.h>
#include <stdlib.h>
template <class T> class BiTreeNode
{
private:
BiTreeNode<T>* leftChild; //左子树指针
BiTreeNode<T>* rightChild; //右子树指针
public:
T data;
//构造函数和析构函数
BiTreeNode():leftChild(NULL),rightChild(NULL){}
BiTreeNode(T item,BiTreeNode<T>* left= NULL,
BiTreeNode<T>* right = NULL):
data(item),leftChild(left),rightChild(right){}
~BiTreeNode(){}
//结点操作的成员函数
BiTreeNode<T>*& Left(void){return leftChild;}
BiTreeNode<T>*& Right(void){return rightChild;}
};
Data Structure LXJ
//page 7.4.5二叉树类
#include <iostream.h>
#include <stdlib.h>
#include "BiTreeNode.h"
template<class T> class BiTree
{
private:
BiTreeNode<T> *root;
//实现相应共有成员函数的算法
void PreOrder(BiTreeNode<T> *&t,void (*visit)(T item));
void InOrder(BiTreeNode<T> *&t,void (*visit)(T item));
void PostOrder(BiTreeNode<T> *&t,void (*visit)(T item));
public:
…
7.4.5 二叉树类
A
B C
D E F
Data Structure LXJ
7.4 链式存储结构的二叉树设计
public:
//构造函数和析构函数
BiTree():root(NULL){};
~BiTree(){};
//构造二叉树
void MakeTree(const T &item,BiTree<T> &left,BiTree<T>
&right);
//遍历访问树
void PreOrder(void (*visit)(T item)); //前序遍历访问树
void InPreOrder(void (*visit)(T item)); //中序遍历访问树
void PostOrder(void (*visit)(T item)); //后序遍历访问树
}; A
B C
D E F
Data Structure LXJ
构造树和删除树的根结点
1,构造树和删除树的根结点
template<class T>
void BiTree<T>::MakeTree(const T &item,BiTree<T>
&left,BiTree<T> &right)
//构造数据域为 item左子树为 left 右子树为 right的二叉树
{
root = new BiTreeNode<T>(item,left.root,right.root);
}
left.root = right.root = NULL;
Data Structure LXJ
7.4 链式存储结构的二叉树设计
template<class T>
void BiTree<T>::PreOrder( void (*visit)(T item) )
//用 visit(item)函数前序遍历访问当前对象的二叉树的公有函数
{
PreOrder(root,visit);
}
template<class T>
void BiTree<T>::PreOrder(BiTreeNode<T> *&t,void (*visit)(T
item))
//用 visit(item)函数前序遍历访问二叉树 t的私有函数
{
if(root != NULL)
{
visit(t -> data);
PreOrder(t ->Left(),visit);
PreOrder(t->Right(),visit);
}
}
不用给出二叉树对象的根结点的指针但为了实现二叉树的递归遍历，
根结点这个指针参数是必需的
Data Structure LXJ
7.4 链式存储结构的二叉树设计
#include "BiTree.h"
template<class T>
void Visit<T>(T item)
{
cout << item << " ";
}
void main(void)
{
BiTree<char> a,b,c,d,e,f,g,null;
g.MakeTree('G',null,null);
d.MakeTree('D',null,g);
b.MakeTree('B',d,null);
e.MakeTree('E',null,null);
f.MakeTree('F',null,null);
c.MakeTree('C',e,f);
a.MakeTree('A',b,c);
cout << "前序遍历序列为,";
a.PreOrder(Visit);
}
A
B C
D E F
G
Data Structure LXJ
第六部分线索二叉树
Data Structure LXJ
线索二叉树
1,二叉树的二叉链表存储：反复递归操作
2,二叉树游标化：类似单链表的简单操作
3,线索二叉树：线索化后的二叉树结点更容易找到其的前驱和后继，
线索二叉树的优点：遍历查找方便快捷，从任何结点可以向前向后搜索
线索二叉树的用途：需要反复遍历和查找的二叉树
本节内容：
1,线索二叉树的存储结构
2,线索二叉树类
3,中序线索二叉树类
Data Structure LXJ
7.6.1 线索二叉树的存储结构
按某种规则遍历二叉树时把二叉树的结点排成一个线性结构,本质 上就是对一个非线性结构进行线性化操作
保存这种按某种规则遍历二叉树时得到的每个结点的后继结点信息和前驱结点信息，就构成线索二叉树结点的存储结构
1,对二叉树以某种遍历方式使其变为线索二叉树的过程称作按该种方式对二叉树进行的 线索化。
Data Structure LXJ
线索二叉树结点结构
带线索的二叉树，即每个结点都带有指向其前驱和后继的指针的二叉树
结点域说明，加入了标志域
1,leftThread = 0 leftChild 指向左孩子结点
2,= 1 指向前驱
3,rightThread = 0 rightChild 指向右孩子结点
4,= 1 指向后继
结点存储结构中指向前驱结点的指针和指向后继结点的指针称为 线索
leftChild leftThread data rightThread rightChild
Data Structure LXJ
中序线索二叉树
1,增加头结点使算法设计方便
2,头结点 左孩子 指向根结点,右线索 指向遍历算法的最后一个结点
A
B C
D E F?
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
a）二叉树 b）中序线索二叉树
Data Structure LXJ
前序线索二叉树
A
B C
D E F?
a）二叉树 b）前序线索二叉树
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
Data Structure LXJ
后序线索二叉树
A
B C
D E F?
a）二叉树
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
b）后序线索二叉树
Data Structure LXJ
7.6.2 线索二叉树类
线索二叉树类定义所有或实现各种不同的线索二叉树类共同的操作，为各种不同的线索二叉树提供相同的操作；
如成员函数,First(),Next(),EndOfNext()构成线索二叉树的正向遍历的循环结构；
又如成员函数,Last(),Prior(),EndOfPrior()
构成线索二叉树的反向遍历的循环结构；
当然不同遍历方法实现的线索二叉树的具体函数算法是不同的，将在具体的派生类中实现。
Data Structure LXJ
类层次图线索二叉树后序线索二叉树前序线索二叉树 中序线索二叉树
Data Structure LXJ
线索二叉树类定义
template <class T> class ThreadIterator
{
protected:
BiTrThNode<T> *root;
BiTrThNode<T> *root;
int nextComplete;
int priorComplete;
public:
//构造函数
ThreadIterator（ BiTrThNode<T> *&tree） ;
//数据检索和修改成员函数
T& Data(void);
…
Data Structure LXJ
线索二叉树类定义
…
//算法需要的成员函数
virtual void First(void) = 0; //纯虚函数
virtual void Next(void) = 0; //纯虚函数
virtual void Last(void) = 0; //纯虚函数
virtual void Prior(void) = 0; //纯虚函数
virtual void EndOfNext(void)const
{
return nextComplete;
}
virtual void EndOfPrior(void)const
{
return priorComplete;
}
};
Data Structure LXJ
线索二叉树的构造函数
template<class T>
ThreadIterator<T>::ThreadIterator(BiTrThNode<T>*& tree)
//构造函数
{
root = tree;
current = root;
if(tree == NULL)
{
nextComplete = 1;
priorComplete = 1;
}
else
{
nextComplete = 0;
priorComplte = 0;
}
}
Data Structure LXJ
返回二叉树结点值
template <class T>
T& ThreadIterator<T>::Data(void)
//返回线索二叉树的数据域值
{
if(root == NULL)
{
cout << "二叉树空！ " << endl;
exit(1);
}
return current->data;
}
Data Structure LXJ
7.6.3 中序线索二叉树类
类中将定义的两类函数：
1,中序线索二叉树类将具体实现基类中的和遍历相关的 4个虚函数，以方便对该二叉树的查找等操作。
2,实现中序线索化函数 CreateInThread()和
InThread()
1,中序线索化函数具体实现是在二叉树的 中序遍历 过程中给每个结点添加线索信息；
2,线索二叉树在没有被线索化之前可以按一般二叉树看待。
Data Structure LXJ
中序线索二叉树类定义
template <class T>
class InThreadIterator:public ThreadIterator<T> //继承
{
private:
void InThread(BiTrThNode<T> *& tree,
BiTrThNode<T> *&pre);
public:
//构造函数
InThreadIterator(BiTrThNode<T>*&
tree):ThreadIterator<T>(tree){};
void CreadInThread();
virtual void First(void);
virtual void Next(void);
virtual void Last(void);
virtual void Prior(void);
};
Data Structure LXJ
中序线索化函数－ CreatInThread()
template <class T>
void InThreadIterator<T>::CreatInThread()
//中序线索化二叉树
{
BiTrThNode<T> *t = root;
root = new BiTrThNode<T>;
root->leftThread = 0;
root ->rightThread = 1;
if(t == NULL)
{
root->leftChild = root;
root->rightChild = root;
}
…
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
Data Structure LXJ
CreatInThread()
…
else //当树非空
{
current = root->leftChild = t; //置头结点的左指针
root->leftThread = 0; //置头结点的左标志
BiTrThNode<T>* pre = root;
InThread(current,pre); //中序线索化二叉树
pre->rightChild = root; //置最后一个结点的右线索
pre->rightThread = 1; //置最后一个结点的右标志
root->rightChild = pre; //置头结点的右线索
root->rightThread = 1; //置头结点的右标志
}
}
Data Structure LXJ
中序线索化函数－ InThread()
templage <class T>
void InThreadIterator<T>::InThread(BiTrThNode<T>*&
current,BiTrThNode<T>*& pre)
//中序线索化二叉树,current为当前指针，
//pre为当前结点的中序前驱结点指针
{
if(current != NULL)
{
InThread(current->leftChild,pre);//中序线索化左子树
if(current -> leftChild == NULL) //当前结点左子树为空
{
current->leftChild = pre; //建立左线索指针
current->leftThread = 1; //建立左线索标记
}
…
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
Data Structure LXJ
InThread()
…
if(pre->rightChild = current)
{
pre->rightChild = current;
pre->rightThread = 1;
}
pre = current;
InThread(current->rightChild,pre);
}
}
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
Data Structure LXJ
Next()
template <class T>
void InThreadIterator<T>::Next(void)
//使当前结点指针指向当前结点的下一个结点，到尾部时正序结束标记置为 1
{
if(nextComplete == 1)
{
err << "已到二叉树 !" << endl;
exit(1);
}
//使当前结点指针指向当前结点的下一个结点
BiTrThNode<T> *p = current->rightChild;
if(current->rightThread == 0)
while(p->leftThread == 0) p = p－ >leftChild;
current = p;
if(current == root) nextComplete = 1;
}
Data Structure LXJ
遍历 线索二叉树 (补充 )
遍历线索二叉树,
有了线索二叉树，就容易遍历二叉树了．
只要
（１）先找要遍历的第一个结点；
（２）然后依次找结点的后继；
（３）重复（２）直到其后继为头结点．
所有问题归为如何在线索二叉树中找结点的后继？
Data Structure LXJ
1）遍历中序线索二叉树
（ 1）中序线索二叉树中，找结点的后继算法算法思想,对任意结点 p，若 rtag=1，则
rchild指向该结点的后继；若 rtag=0，则
rchild指向该结点的右孩子，此时，应从右孩子开始，沿左指针前进，直到找到没有左孩子的结点 s（ ltag=1）,则 s就是 p的后继，即后继是中序遍历右子树时，访问的第一个结点；
Data Structure LXJ
中序线索二叉树中，找结点的后继 算法
BiThrTree in_next(p,thrt)
BiThrTree p,thrt;
{ /*在以 thrt为头指针的中序线索二叉树上,*/
/*查找指针 p所指结点的后继 */
s=p->rchild；
if (p->rtag==0)
while (s->ltag=0)
s= s->lchild；
return s;
}//in_next
p
1
s
p
0
1
0
s
Data Structure LXJ
（ 2）遍历中序线索二叉树算法
void thrt_inorder(BiThrTree thrt)
{//遍历以 thrt为头指针的中序线索二叉树
p=thrt->lchild；
while (p->lchild<>thrt) p= p->lchild;
//定位要遍历的第一个结点,
while (p<>thrt) { visit(p->data)；
p=in_next(p,thrt);}
}//thrt_inorder
p-> ltag==0
Data Structure LXJ
2）遍历后序线索二叉树
（ 1）后序线索二叉树中，找结点的后继算法算法思想,对任意结点 p，
若 p为二叉树的根，则无后继 ;
若 p是双亲的右孩子、或是独生左孩子，则后继为双亲；
若 p是有兄弟的左孩子，则后继为双亲的右子树上按后序遍历时，访问的第一个结点 (叶结点 )；
s
p
s
p
s
p
s
Data Structure LXJ
后序线索二叉树中，找结点的后继 算法
BiThrTree post_next(p,thrt)
BiThrTree p,thrt;
{//在以 thrt为头指针的后序线索二叉树上,
//查找指针 p所指结点的后继
s=parent（ thrt,p）； //在 thrt上查找 p的双亲
if (s==thrt) return thrt；
if (s->rchild==p)||(s->rtag==1)return s；
while (s->rtag==0)
{ s= s->rchild；
while (s->ltag==0) s= s->lchild； }
return s;
}//post_next
Data Structure LXJ
（ 2）遍历后序线索二叉树算法
void thrt_postorder(BiThrTree thrt)
{//遍历以 thrt为头指针的后序线索二叉树
if (thrt!=thrt->lchild)
{ p=thrt->lchild； search=1；
while (search)
{ while (p->ltag==0) p= p->lchild；
if (p->rtag==0) p= p->rchild;
else search=0； }
while (p!=thrt) { visit(p↑.data) ；
p=post_next(p,thrt)}}
}//thrt_postorder
Data Structure LXJ
3）遍历先序线索二叉树
（ 1）先序线索二叉树中，找结点的后继算法算法思想,对任意结点 p:
若 p有左孩子，则后继为左孩子 ;
若 p无左孩子,有右孩子，则后继为右孩子；
若 p无左孩子,也无右孩子，则后继为右线索；
Data Structure LXJ
先序线索二叉树中，找结点的后继 算法
BiThrTree pre_next(p,thrt)
BiThrTree p,thrt;
{//在以 thrt为头指针的先序线索二叉树上,
//查找指针 p所指结点的后继
if (p->ltag==0) return(p->lchild)；
else return p->rchild;
}//pre_next
Data Structure LXJ
（ 2）遍历先序线索二叉树算法
void thrt_preorder(BiThrTree thrt)；
{ //遍历以 thrt为头指针的先序线索二叉树
p=thrt->lchild；
while (p!=thrt)
{ visit(p->data)；
p=pre_next(p,thrt)}
}//thrt_preorder
Data Structure LXJ
第七部分堆
Data Structure LXJ
7.7.1 堆的定义
堆 （ heap）是具有如下特点的 完全二叉树,
1,若根结点存在左（右）孩子，则根结点值 小于等于 （大于等于）左（右）孩子结点值；
2,以左右孩子为根的子树又各是一个堆。
12
24 16
59 66 72 38
80
Data Structure LXJ
堆分类
12
24 16
59 66 72 38
80
88
76 32
50 10 16 9
a）小顶堆 b）大顶堆
Data Structure LXJ
堆的存储
堆是一个完全二叉树,故可用数组来存放堆元素
根据数组下标和完全二叉树的性质就可数组中找出双亲－孩子 关系和 大小 比较
12
24 16
59 66 72 38
80
38726659162412
6543210
80
7
a）堆 b）堆的存储
Data Structure LXJ
7.7.2 最小堆类－ Class MinHeap
template <class T> class MinHeap
{
private:
T* heapArray; //存放数据元素的数组
int markArray; //标记
int MaxHeapSize； //最大元素个数
int heapsize; //当前元素个数
void FilterUp(int i); //插入元素后重新堆化
void FilterDown(int i); //删除元素后重新堆化
…
Data Structure LXJ
Class MinHeap
…
public:
MinHeap(int maxSize); //构造函数
//拷贝构造函数，用于把 n个元素的数组堆化
MiniHeap(T arr[],int n);
~MiniHeap(void)
{if (markArray == 0) delete heapArray;}
void Insert(const T& item);
T Delte(void);
T GetHeapTop() const {return heapArray[0]}
int HeapSize(void)const {return heapSize;}
int HeapEmpty(void)const {return heapSize == 0;}
int HeapFull(void)const
{return heapSize == MaxHeapSize;}
};
Data Structure LXJ
1、插入数据元素操作第一步,插入数据结点 15
1,currentPos = 8
2,计算,parentPos = (8 – 1)/ 2 =3
3,比较,heapArray[3] > heapArray[8],不满足 小顶堆定义，应该交换位置
38726659162412
6543210
80
7
15
8
12
24 16
59 66 72 38
80 15
heapArray
Data Structure LXJ
插入数据元素第二步,交换数据结点 59<－ >15
1,heapArray[1] <-> heapArray[3]
2,currentPos = 3
3,计算,parentPos = (3 – 1)/ 2 =1
4,比较,heapArray[1] > heapArray[3],不满足 小顶堆定义，应该交换位置
38726615162412
6543210
80
7
59
8
12
24 16
15 66 72 38
80 59
heapArray
Data Structure LXJ
插入数据元素第三步,交换数据结点 24<－ >15
1,heapArray[3] <-> heapArray[8]
2,currentPos = 1
3,计算,parentPos = (1 – 1)/ 2 =0
4,比较,heapArray[1] < heapArray[3],满足 小顶堆定义，结束
38726624161512
6543210
80
7
59
8
12
15 16
24 66 72 38
80 59
heapArray
Data Structure LXJ
12
24 16
59 66 72 38
80 15
12
15 16
24 66 72 38
80 59
38726659162412
6543210
80
7
15
8
heapArray
38726615162412
6543210
80
7
59
8
38726624161512
6543210
80
7
59
8
38726659162412
6543210
80
7 8
插入操作
a）插入前后 b）数据元素移动过程
Data Structure LXJ
2、删除数据元素操作第一步,删除数据结点 12
38726659162412
6543210
80
7
12
24 16
59 66 72 38
80
heapArray
第二步,移动该结点为根结点的子堆中最后一个元素填删除位置
38726659162480
6543210 7
80
24 16
59 66 72 38
80
heapArray
Data Structure LXJ
删除数据元素第三步：
1,计算左右孩子位置
2,并和左右孩子结点比较大小
38726659162480
6543210 7
80
24 16
59 66 72 38
heapArray
第四步：
1,和最小的孩子交换位置
2,并和左右孩子结点比较大小
16
24 80
59 66 72 38
38726659802416
6543210 7
heapArray
Data Structure LXJ
删除数据元素第五步：
1,和最小的孩子交换位置
2,80结点无孩子，不用再移动，算法结束
16
24 38
59 66 72 80
80726659382416
6543210 7
heapArray
16
24 38
59 66 72 80
80726659382416
6543210 7
heapArray
最后结果：符合小顶堆定义
Data Structure LXJ
3、数组堆化操作
堆化：把一个有 n个数据元素的数组构造成一个堆。
方法 1：生成一个空堆，利用前面插入算法插入数组中每个元素，每插入一个元素使新数组仍然为堆
方法 2：利用原有数组，移动数据元素达到目的
Data Structure LXJ
数组堆化－ 方法 1
24 24
10
10
24
33251677901024 89 67 array
10
24 90
10
24 90
77
10
24 90
77 16
10
16 90
77 24
10
16 90
77 24 25
10
16 25
77 24 90
10
16 25
77 24 90 33
插入 24 插入 10 插入 90 插入 77
插入 16 插入 25 插入 33
Data Structure LXJ
数组堆化－ 方法 1
33251677901024 89 67 array
10
16 25
77 24 90 33
89
10
16 25
77 24 90 33
89 67
10
16 25
67 24 90 33
89 77
插入 89 插入 67
33902467251610 89 77堆中数组：
Data Structure LXJ
数组堆化操作－方法 2
1、调整最后一个叶子结点的双亲结点构成的子树为一个堆
（最后一个叶子结点的双亲结点为 currentPos）
2、调整该结点前一个结点所形成的一个子树为一个堆
(currentPos=
currentPos-1)
3、直到根结点（下标为 0）
24
10 90
77 16 25 33
89 67
Data Structure LXJ
数组堆化－ 方法 2
24
10 90
77 16 25 33
89 67
24
10 90
67 16 25 33
89 77
24
10 90
67 16 25 33
89 77
24
10 25
67 16 90 33
89 77
第一步第二步
Data Structure LXJ
24
10 25
67 16 90 33
89 77
数组堆化－ 方法 2
第三步
24
10 25
67 16 90 33
89 77
第四步
10
16 25
67 24 90 33
89 77
Data Structure LXJ
哈夫曼树（ Huffman）树是一类带权路径长度最短的树一,Huffman树（最优二叉树）
1,概念
两结点间的路径：从一结点到另一结点所经过的结点序列
路径长度：路径上的分支树
树的路径长度：从根到每一结点的路径长度之和
2
76
3
4
1
5
例
⑴ -⑵ -⑸ 为结点 1到 5之间的路径，其路径长度为 2，
树的路径长度 =l12 +l13+l14 +l15+ l16 +l17
=1+1+2+2+2+2=10
7.8 哈夫曼树
Data Structure LXJ
考虑带权时：设树中有 m个叶结点，每个叶结点带一个权值 wｉ 且根到叶结点 i的路径长度为 Li (ｉ =1,2，．,m），则树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。
Ｍ
即：ＷＰＬ＝ ∑ Ｗ ｋ Ｌ ｋ
Ｋ＝１
7.8 哈夫曼树
Data Structure LXJ
例：
使 WPL最小的二叉树成为最优二叉树 (Huffman 树 )
完全二叉树
dca b
7 5 2 4
c
d
ba
2
4
7 5
WPLa=2*7+2*5+2*2+2*4 WPLb=7*3+5*3+2*1+4*2
=36 =46
7.8 哈夫曼树
Data Structure LXJ
Huffman 树
WPLc=7*1+5*2+2*3+4*3
=35
b
dc
a
7
5
2 4
（ 1）完全二叉树并不一定是 Huffman树；
（ 2） HT是权值越大的越靠近根结点；
（ 3） HT不唯一，但
WPL一定相等。
7.8 哈夫曼树
Data Structure LXJ
2．构造 Huffman树算法
(1) 以权值分别为 W1,W2．．．Ｗ ｎ 的ｎ各结点，构成 n棵二叉树 T1,T2,．．,Tn并组成森林 F={T1,T2,．．,Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点；
(2) 在 F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值 =左右孩子权值之和，
叶结点的权值 = Wi）
(3) 从 F中删除这两棵二叉树，同时将新二叉树加入到 F中 ;
(4) 重复 (2),(3)直到 F中只含一棵二叉树为止，这棵二叉树就是 Huffman 树。
7.8 哈夫曼树
Data Structure LXJ
a b c d
7 5 2 4例,F={ }
a bF={ }
c d
7 5 6
2 4
F={ }a
b
c d
11
6
4
2
5
F={ }a
b
c d
11
6
425
7
18
7
7.8 哈夫曼树
Data Structure LXJ
HT不唯一性,可能出现在,
（ 1）构造新树时，左、右孩子未作规定。
（ 2）当有多个权值相同的树，可作为候选树时，选择谁未作规定。
二、哈夫曼编码（ Huffman 树的应用）
1、问题的提出通讯中常需要将文字转换成二进制字符串电文进行传送。文字 电文，称为 编码 。
反之，收到电文后要将电文转换成原来的文字，
电文 文字，称为 译码 。
7.8 哈夫曼树
Data Structure LXJ
例如：需将文字,ABACCDA”转换成电文。文字中 有四种字符，用 2位二进制便可分辨。
A B C D
00 01 10 11
编码方案 1：
则上述文字的电文为,00010010101100 共 14位。
译码时，只需每 2位一译即可。
特点：等长等频率编码，译码容易，但电文不一定最短,
7.8 哈夫曼树
Data Structure LXJ
A B C D
0 00 1 01
编码方案 2：
采用不等长编码，让出现次数多的字符用短码。
则上述文字的电文为,000011010 共 9位。
但无法译码，它即可译为 BBCCACA，也可译为
AAAACCDA等。
必须使任何一个字符得编码都不是另一个字符编码得前缀
7.8 哈夫曼树
Data Structure LXJ
A B C D
0 110 10 111
编码方案 3：
采用不等长编码，让出现次数多的字符用短码，
且任一编码不能是另一编码的前缀,即前缀编码。
则上述文字的电文为,0110010101110 共 13位。
7.8 哈夫曼树
Data Structure LXJ
设有 n种字符，每种字符出现的次数为 Wi,
其编码长度为 Li (i=1,2,．．,n)，
则整个电文总长度为 ∑ Wi Li,
要得到最短的电文，即使得 ∑ Wi Li最小。
也就是以字符出现的次数为权值，构造一棵 Huffman树，
并规定左分支编码位 0，右分支编码为 1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。
用构造 Huffman树编出来的码，称为 Huffman编码。
哈夫曼编码构造方法
7.8 哈夫曼树
Data Structure LXJ
对上例有,
1
A
3 C
B D
1
1
2 0
0
0
1 1
7.8 哈夫曼树
Data Structure LXJ
7.8 哈夫曼树
#include <iostream.h>
#include <stdlib.h>
const int MaxValue = 10000; //初始设定的权值最大值
const int MaxBit = 10; //初始设定的最大编码位数
const int MaxN = 10; //初始设定的最大结点个数
struct HaffNode
//哈夫曼树结点结构
{
int weight; //权值
int flag; //标记
int parent; //双亲结点下标
int leftChild; //左孩子下标
int rightChild; //右孩子下标
};
Data Structure LXJ
7.8 哈夫曼树
struct Code
//存放哈夫曼编码的数组元素结构
{
int bit[MaxN]; //数组
int start; //编码的起始下标
int weight; //字符的权值
};
Data Structure LXJ
7.8 哈夫曼树
void Haffman(int weight[],int n,HaffNode haffTree[])
//建立叶结点个数为 n权值数组为 weight的哈夫曼树 haffTree
{
int j,m1,m2,x1,x2;
//哈夫曼树 haffTree[]初始化。 n个叶结点共有 2n-1个结点
for (int i = 0;i < 2;i++ )
{
if(i < n)
haffTree[i].weight = weight[i];
else
haffTree[i].weight = 0;
haffTree[i].parent = 0;
haffTree[i].flag = 0;
haffTree[i].leftChild = -1;
haffTree[i].rightChild = -1;
}
Data Structure LXJ
7.8 哈夫曼树
//构造哈夫曼树 haffTree[]的 n-1个非叶结点
for (i = 0;i < n - 1 ;i++ )
{
m1 = m2 = MaxValue;
x1 = x2 = 0;
for (j = 0;j < n + 1 ;j++ )
{
if (haffTree[j].weight < m1 && haffTree[j].flag == 0)
{
m2 = m1;
x2 = x1;
m1 = haffTree[j].weight;
x1 = j;
}
else if(haffTree[j].weight < m2 && haffTree[j].flag == 0)
{
m2 = haffTree[j].weight;
x2 = j;
}
}
Data Structure LXJ
7.8 哈夫曼树
//将找出的两棵权值最小的子树合并为一棵子树
haffTree[x1].parent = n + i;
haffTree[x2].parent = n + i;
haffTree[x1].flag = 1;
haffTree[x2].flag = 1;
haffTree[n + i].weight = haffTree[x1].weight +
haffTree[x2].weight;
haffTree[n + i].leftChild = x1;
haffTree[n + i].rightChild = x2;
}
}
Data Structure LXJ
7.8 哈夫曼树
void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[])
//由 n个结点的哈夫曼树 haffTree[]构造哈夫曼编码 haffCode[]
{
Code* cd = new Code;
int child,parent;
//求 n个叶结点的哈夫曼编码
for (int i = 0;i < n;i++ )
{
cd->start = n - 1; //不等长编码的最后一位为 n-1
cd->weight = haffTree[i].weight; //取得编码对应权值得字符
child = i;
parent = haffTree[child].parent;
。。。
Data Structure LXJ
7.8 哈夫曼树
//由叶结点向上直到根结点
while (parent != 0)
{
if(haffTree[parent].leftChild == child)
cd->bit[cd->start] = 0;
else
cd->bit[cd->start] = 1;
cd -> start --;
child = parent;
parent = haffTree[child].parent;
}
//保存每个叶结点得编码和不等长编码得起始位
for (int j = cd->start + 1;j < n;j++ )
haffCode[i].bit[j] = cd -> bit[j];
haffCode[i].start = cd->start;
haffCode[i].weight = cd->weight; //记住编码对应权值的字符
}
}
Data Structure LXJ
7.8 哈夫曼树
void main(void)
{
int i,j,n = 4;
int weight[] = {1,3,5,7};
HaffNode * myHaffTree = new HaffNode[2*n+1];
Code* myHaffCode = new Code[n];
if (n > MaxN)
{
cout << "定义的 n越界，修改 MaxN！ " << endl;
exit(1);
}
Data Structure LXJ
7.8 哈夫曼树
Haffman(weight,n,myHaffTree);
HaffmanCode(myHaffTree,n,myHaffCode);
//输出每个叶结点的哈夫曼编码
for (i = 0;i < n;i++)
{
cout << "Weight = " << myHaffCode[i].weight << "Code
= ";
for (j = myHaffCode[i].start + 1;j < n;j++)
cout << myHaffCode[i].bit[j];
cout << endl;
}
}
/*程序运行结果如下：
Weiht = 1 Code = 100
Weiht = 3 Code = 101
Weiht = 5 Code = 11
Weiht = 7 Code = 0
*/
第 7 章树 和 二叉树西南科技大学 计算机学院信息教研室
Data Structure LXJ
内容提纲
7.1 仿真指针
7.2 树
7.3 二叉树
7.4 链式存储结构的二叉树设计
7.5 二叉树遍历游标类
7.6 线索二叉树
7.7 堆
7.8 哈夫曼树
Data Structure LXJ
第一部分仿真指针
Data Structure LXJ
7.1仿真指针
A）常规链表：链式存储实现，使用指针
a1 a2 a3 a4 ^head a0
2a3
4a2
－ 1a4
3a1
1a00
2
3
1
4
data next
B）
静态链表：顺序存储实现 (数组 ),使用仿真指针
Data Structure LXJ
第二部分树
Data Structure LXJ
7.2.1 树的定义树 tree的递归定义：
树 (tree)是 n个数据元素的有限集 (记为 T)，对任意一棵树 T有：
1,存在唯一一个称为 根 (root) 的数据元素；
2,当 n＞ 1时，其它数据元素可分为 m(m＞ 0) 个互不相交的有限集 T1,T2,…,Tm，其中每个集合 Ti(i=1,2,…,m)本身又是一棵树，并称树 Ti是根的 子树 (subtree).
A
B C
D E F G
A(空树 )
（ a） （ b） （ c）
Data Structure LXJ
树的结点（ Node）
根结点、叶结点、分支结点、孩子结点、双亲结点、兄弟结点、
祖先结点、子孙结点
Data Structure LXJ
结点的度、树的度
A
B C D
E F G H I J
K L M
······················根 3度
········叶 0度
2个 3度点 A,D
2个 2度点 B,E
2个 1度点 C,H
7个叶 F,G,I,J,K,L,M
树的度,树中所有结点的度的最大值。
上图：树的度为 3
Data Structure LXJ
结点的层次、树的深度树的深度为 4
A
B C D
E F G H I J
K L M
·············································第一层
······························第二层
···············第三层
····································第四层
Data Structure LXJ
序树、森林
无序树：树中任意一个结点的各个子树之间的次序构成无关紧要，交换树中任意一个结点的各个子树的次序均和原树相同的树构成无序树。
有序树：树中任意一个结点的任意子树都是有次序的树。
森林,m颗树的集合称为森林。
A
B C
D E F G
A
森林
A
B C
Data Structure LXJ
7.2.2 树的表示方法
1,树的直观表示法
A
B C
D E F G
Data Structure LXJ
树的形式化表示法主要用于树理论描述。
T = (D,R)
T为树,D表示树的结点,R为结点之间的关系的集合
为空树时,D =?
非空时,D = {Root}? F （ Root：根结点,F森林）
F = T1? T2? T3 …? Tm （ Ti：子树）
R = {<Root,Rooti>,I = 1,2,3…m} （ Root：根结点、
Rooti,i子树的根结点,<Root,Rooti> 表示了父子关系）
树的形式化表示法
A
B C
D E F G
Data Structure LXJ
树的凹入表示法
A）常规表示
A
B C
D E F G
A
B
C
D
E
D
E
B）凹入表示
Data Structure LXJ
树的集合表示
A
B C
D E F G
A）常规表示
D E F G
B C
A
B）集合表示
C）广义表表示
（ A（ B（ D,E）,C（ F,G） ） ）
Data Structure LXJ
7.2.3 树的基本操作
树是非线性结构，结点之间的关系较线性结构复杂。
数据成员：根节点指针，当前节点指针第一类操作：
1,寻找根结点使之成为当前结点；
2,寻找当前结点的双亲结点使之成为当前结点；
3,寻找当前结点的孩子结点使之成为当前结点；
4,寻找当前结点的下一个兄弟结点使之成为当前结点。
Data Structure LXJ
树的基本操作第二类操作：
1,在树的当前结点上插入一个新结点，使新插入的结点成为当前结点的第 i个孩子结点；
2,删除树的当前结点的第 i个孩子结点；
3,在树的当前结点上插入一个新子树，使新子树成为当前结点的第 I棵子树；
4,删除树的当前结点的第 I棵子树。
Data Structure LXJ
树的基本操作第三类操作：
1,按某种方式遍历一棵树显示树中每个结点的数据域值；
2,按某种方式遍历一棵树寻找数据元素域为某一值的结点。
树的遍历操作指按某种方式访问树中每一个结点，
且每一个结点只被访问一次
遍历方式分为：
1,先根遍历
2,后根遍历
Data Structure LXJ
树的遍历
先根遍历：
1,访问根结点
2,按照从左到右次序先根遍历根结点的每一棵子树
A
B C D
E F G H I J
K L M
遍历次序,A B E K L F C G D H M I J
A
B C D
遍历次序,A B C D
Data Structure LXJ
树的遍历
后根遍历：
1,按照从左到右次序后根遍历根结点的每一棵子树
2,访问根结点
A
B C D
E F G H I J
K L M
遍历次序,K L E F B G C M H I JD A
A
B C D
遍历次序,B C D A
层次遍历
Data Structure LXJ
7.2.4 树的存储结构
计算机中树的存储既要求存储数据，又要求存储关系，但关系复杂
常见几种存储结构
1,双亲表示法
2,孩子表示法
3,双亲孩子表示法
4,孩子兄弟表示法
Data Structure LXJ
双亲表示法
双亲表示法每个结点有两个域：
1,data：数据元素域
2,parent：指示其双亲结点的指针域
A
B C
D E F G
IH
a）一棵树
4I
4H
2G
1F
1E
1D
0C
0B
-1A
下标 data parent
8
7
6
5
4
3
2
1
0
b）双亲表示法仿真指针存储结构
Data Structure LXJ
孩子表示法
孩子表示法每个子树个数（即结点的度）不同，每个结点的孩子结点指针域不同，为了方便，定义结点孩子指针域个数为树的度：
1,data：数据元素域
2,children[]：指示其孩子结点的指针域
A
B C
D E F G
IH
a）一棵树 b）树的常规指针的孩子表示法
A
CB
FDG?E
GI
root
Data Structure LXJ
双亲孩子表示法
双亲孩子表示把双亲表示法和孩子表示法结合起来的兼具两种存储结构的优点。
A
B C
D E F G
IH
a）一棵树 b）双亲孩子表示法的一种结构
4I8
4H7
2G6
1F5
1E4
1D3
0C2
0B1
-1A0
下标 data parent children
1 2?
3 4
6?
5?
7 8?
Data Structure LXJ
孩子兄弟表示法
孩子兄弟表示为每个结点设计三个域：
1,data：数据元素域
2,firstChild：该结点的第一个孩子指针
3,nextSibling：该结点的下一个兄弟指针
a）一棵树 b）孩子兄弟表示法
A
B C
D E F G
IH
A?
B C?
D E? F G?
H? I?
root
Data Structure LXJ
7.2.5 树类的抽象
树抽象用得最多的一种表示法：孩子兄弟表示法，
抽象过程分为两步
1,结点的抽象
2,树的抽象
Data Structure LXJ
树类－ 结点定义
firstChild data nextSibling
#include <stdlib.h>
template <class T> class Tree;
template<class T> class TreeNode
{
friend class Tree<T>; //树类为友元
private:
TreeNode<T>* firstChild; //第一个孩子结点指针域
TreeNode<T>* nextSibling; //下一个兄弟结点指针域
public:
T data; //数据域
…
Data Structure LXJ
…
//构造函数
TreeNode(T value,TreeNode<T> *fc =NULL,
TreeNode<T> *ns = NULL)
:data(value),firstChild(fc),nextSibling(ns){}
//访问指针域的成员函数
TreeNode<T>* &FirstChild(void)
{
return firstchild;
}
TreeNode<T>* &NextSlibling(void)
{
return nextSibling;
}
};
树类－ 结点定义
Data Structure LXJ
template <class T> class Tree
{
private:
//数据成员
TreeNode<T>* root; //根结点指针
TreeNode<T>* current; //当前结点指针
//私有成员函数
void PreOrderTree(TreeNode<T>*& t);
void PostOrderTree(TreeNode<T>*& t);
int Current(TreeNode<T>*& t);
//在树 root中回溯查找结点 s的双亲结点
TreeNode<T>* SerchParent(TreeNode<T>*& root,
TreeNode<T>*& s);
…
树类定义
Data Structure LXJ
…
public:
Tree() //构造函数
{ root = current = NULL;
};
~Tree() //析构函数
{
DeleteSubTree(root);
};
int Root(); //使根结点为当前结点
int Parent(); //使当前结点的双亲结点为当前结点
int FirstChild(); //使当前结点的第一个孩子结点为当前结点
int Nextsibling();//使当前结点的兄弟结点为当前结点
…
第一类操作的成员函数构造函数和析构函数树类定义
Data Structure LXJ
public:
…
//第二类操作的成员函数
void InsertChild(T value);
//把 value值插入到当前结点的最后一个结点
void DeleteSubTree(TreeNode<T>*& t);
//删除以 t为根结点的子树
int DeleteChild(int i); //删除当前结点的第 i个孩子结点
//第三类操作的成员函数
void DisplayTree();//按先根遍历次序显示树的数据域值
};
树类定义
Data Structure LXJ
树类实现－ 构造函数和析构函数
A
B C D
E F
A?
B
E? C
D F?
root
Tree() //构造函数
{
root = current = NULL;
};
~Tree() //析构函数
{
DeleteSubTree(root);
};
Data Structure LXJ
template <class T>
void Tree<T>::DeleteSubTree(TreeNode<T>*& t)
{
if(t == NULL) return;
TreeNode<T>* q = t->firstChild,*p;
while(q != NULL)
{
p = q->nextSibling;
DeleteSubTree(q);
q = p;
}
delete t;
}
A?
B
E? C
D F?
root
树类实现－ 删除以 t为根结点的子树
Data Structure LXJ
template <class T>
int Tree<T>::Current(TreeNode<T>*& t) //当前节点为是 t所指节点
{
if(t == NULL) return 0;
current = t;
return 1;
}
A?
B
E? C
D F?
root
树类实现－ 第一类操作
Data Structure LXJ
template <class T>
int Tree<T>::Root()
{
if(root == NULL)
{
current = NULL;
return 0;
}
return Current(root);
}
A?
B
E? C
D F?
root
树类实现－ 第一类操作
Data Structure LXJ
template <class T>
int Tree<T>::FirstChild()
{
if(current != NULL && current->firstChild !=
NULL)
return Current(current->firstChild);
else
return 0;
}
A?
B
E? C
D F?
root
树类实现－ 第一类操作
Data Structure LXJ
template <class T>
int Tree<T>::Nextsibling()
{
if(current != NULL && current->nextSibling != NULL)
return Current(current->nextSibling);
else
return 0;
}
A?
B
E? C
D F?
root
树类实现－ 第一类操作
Data Structure LXJ
template <class T>
int Tree<T>::Parent()
// 使当前结点的双亲结点为当前结点
{
if(current == NULL)
{
current = root;
return 0;
}
TreeNode<T>* p = SerchParent(root,current);
if(p == NULL) return 0;
else return Current(p);
}
A?
B
E? C
D F?
root
树类实现－ 第一类操作
Data Structure LXJ
template <class T>
TreeNode<T>* Tree<T>::SerchParent(TreeNode<T>*
&root,TreeNode<T>*& s)// 在树 root中回溯查找结点 s的双亲结点
//查找到时时 current指向 s结点的双亲结点
{
if(root == NULL) return NULL;
if(root -> FirstChild() == s|| root->NextSibling() == s)
return root;
TreeNode<T>* p;
if((p = SearchParent(root->FirstChild(),s)) != NULL) return p;
if((p = SearchParent(root->NextSibling(),s)) != NULL) return p;
return NULL; //失败时返回空使算法回溯
}
树类实现－ 第一类操作
Data Structure LXJ
树类实现－ 第二类操作
template <class T>
void Tree<T>::InsertChild(T value)
// 把 value值插入到当前结点的最后一个结点
{
//建立数据域值为 value的结点由 newNode指针指示
TreeNode<T>* newNode = new TreeNode<T>(value);
if(root == NULL) //当为空时
{
root = current = newNode;
return;
}
if(current->firstChild == NULL)
current->firstChild = newNode;
。。。
A?
B
E? C
D F?
root
Data Structure LXJ
。。。
else
{
TreeNode<T> *p = current->firstChild;
while(p->nextSibling != NULL) p = p->nextSibling;
p->nextSibling = newNode;
}
Current(newNode);
}
A?
B
E? C
D F?
root
树类实现－ 第二类操作
Data Structure LXJ
template <class T>
int Tree<T>::DeleteChild(int i) // 删除当前结点的第 i个孩子
{
TreeNode<T> *r = NULL;
//当删除当前结点的第一棵子树时
if(i = 1)
{
r = current->firstChild;
if(r == NULL) return 0; //要删除的子树为空，返回
current ->firstChild = r->nextSibling; //脱链要删除的子树
}
。。。
树类实现－ 第二类操作
Data Structure LXJ
template <class T>
int Tree<T>::DeleteChild(int i) // 删除当前结点的第 i个孩子
{
。。。//当删除当前结点的其他子树时
else
{
int k = 1;
TreeNode<T> *p = current->firstChild;
while(p != NULL && k <= i-1) //寻找指向要删除子树的指针
{
p = p->nextSibling;
k++;
}
。。。
}
。。。
}
A?
B
E? C
D F?
root
树类实现－ 第二类操作
Data Structure LXJ
template <class T>
int Tree<T>::DeleteChild(int i) // 删除当前结点的第 i个孩子
{
。。。
//当删除当前结点的其他子树时
else
{ 。。。
if(p != NULL) //所寻找的指向要删除子树的指针找到
{
r = p->nextSibling;
if(r != NULL) //脱链要删除的子树
p->nextSibling = r->nextSibling;
else return 0; //要删除子树为空返回
}
else return 0; //所寻找的指向要删除子树的指针找到
}
DeleteSubTree(r); //删除找到要删除的子树
return 1; //删除成功
}
树类实现－ 第二类操作
Data Structure LXJ
树类实现－ 第三类操作
template <class T>
void Tree<T>::PreOrderTree(TreeNode<T> *& t)
{
if(t == NULL) return;
cout << t->data << " "; //显示根结点数据
if(t->firstChild != NULL) //先根遍历子树
PreOrderTree(t ->firstChild);
if(t->nextSibling != NULL)
PreOrderTree(t ->nextSibling);
}
A?
B
E? C
D F?
root
Data Structure LXJ
树类实现－ 第三类操作
template <class T>
void Tree<T>::PostOrderTree(TreeNode<T> *& t)
{
if(t == NULL) return;
if(t->firstChild != NULL) //后根遍历子树
PostOrderTree(t ->firstChild);
cout << t->data << " "; //显示根结点数据
if(t->nextSibling != NULL)
PostOrderTree(t ->nextSibling);
}
A?
B
E? C
D F?
root
Data Structure LXJ
树类实现－ 第三类操作
template <class T>
void Tree<T>::PostOrderTree(TreeNode<T> *& t)
{
if(t == NULL) return;
if(t->firstChild != NULL) //后根遍历子树
PostOrderTree(t ->firstChild);
cout << t->data << " "; //显示根结点数据
if(t->nextSibling != NULL)
PostOrderTree(t ->nextSibling);
}
Data Structure LXJ
#include <iostream.h>
#include "Tree.h"
void main()
{
Tree<char> t;
t.InsertChild('A');
for(int i = 0;i < 3;i++)
{
t.Root();
t.InsertChild('B' + i);
}
。。。
}
Data Structure LXJ
#include <iostream.h>
#include "Tree.h"
void main()
{
。。。
for(i = 0;i < 2;i++)
{
t.Root();
t.FirstChild();
t.InsertChild('E' + i);
}
cout << "按先根遍历显示的结点次序为," << endl;
t.DisplayTree();
cout << endl << "析构函数按后根遍历释放结点的次序为," << endl;
}
Data Structure LXJ
二叉树
BinaryTree
第二部分
Data Structure LXJ
7.3.1 二叉树的定义
每个结点至多有两棵子树,1度或 2度
每个结点分左子树（ 左孩子 ）、右子树（ 右孩子 ）
二叉树的 5种形态
A
B C
D E F G
H I J
A
B C
D E F G
H I J
a）二叉树 b） 度数为 2的有序树
Data Structure LXJ
特殊二叉树
满二叉树：所有分支结点都存在左子树和右子树，且叶子结点在同一层，称满二叉树。 深度为 k,结点数 2k-1,每层结点数都最大
完全二叉树,满二叉树去掉最下层最右边若干结点
满二叉树也是完全二叉树
A
B C
D E F G
H I J K L M N O
A
B C
D E F G
H I J K
a）满二叉树 b）完全二叉树
Data Structure LXJ
7.3.2 二叉树的性质
性质 1 若规定根结点的层次是 0，则一颗非空二叉树第 i层上的结点数目最多为 2i(i≥0)。
A
B C
D E F G
H I J K L M N O
第 0层第 1层第 2层第 3层
Data Structure LXJ
二叉树的性质
性质 2 若规定空树的深度为 -1,深度为 k的二叉树至多有 2k+1-1个结点 (k≥-1)。
A
B C
D E F G
H I J K L M N O
第 0层第 1层第 2层第 3层
Data Structure LXJ
二叉树的性质
性质 3 在任意 -棵二叉树中，若终端结点的个数为 n0，度为 2
的结点数为 n2，则 no=n2+1。
证明,因为二叉树中所有结点的度数均不大于 2，所以结点总数 (记为 n)应等于 0度结点数,1度结点 (记为 n1)和 2度结点数之和：
n=no+n1+n2 (式子 1)
另一方面,1度结点有一个孩子,2度结点有两个孩子，故二叉树中孩子结点总数是：
nl+2n2
树中只有根结点不是任何结点的孩子，故二叉树孩子结点总数又可表示为,n-1
n-1=n1+2n2 (式子 2)
由式子 1和式子 2得到：
no=n2+1
A
B C
D E F
Data Structure LXJ
二叉树的性质
性质 4 具有 n个结点的完全二叉树的深度为不超过
k = log2(n+1) - 1的最大整数第 1个结点深度为?log21+1? - 1 = 0
第 2-3个结点深度为?log22+1? - 1 = 1
第 4-7个结点深度为?log24+1? - 1 = 2
第 8-15个结点深度为?log28+1? - 1 = 3
1
2 3
4 5 6 7
8 9 10 11 12 13
Data Structure LXJ
二叉树的性质
性质 5,若将一棵具有 n个结点的完全二叉树按层次次序从 0开始编号，则对任意编号为 n的结点有：
1,若 i〉 1，则编号为 i的结点的父结点的编号为 (i-1)/2
2,若 2i+1<n，则编号为 i的结点的左孩子结点编号为 2i+1，
否则 i无左孩子。
3,若 2i+2<=n，则结点 i的右孩子结点编号为 2i+2，否则 i无右孩子。 1
2 3
4 5 6 7
8 9 10 11 12 13
1,结点 i的左孩子结点是 2i
2,右孩子结点是 2i+1
3,结点 i的父结点是?i/2?
Data Structure LXJ
7.3.3 二叉树的操作
二叉树操作和树操作基本相同，
二叉树 =根结点 +左子树 +右子树
第一类操作 （找某种满足某种特定关系的节点）
1,寻找根结点使之成为当前结点
2,寻找当前结点的双亲结点使之成为当前结点
3,寻找当前结点的左孩子使之成为当前结点
4,寻找当前结点的右孩子使之成为当前结点
Data Structure LXJ
二叉树的操作
第二类操作,（插入和删除）
1,在二叉树的当前结点上插入一个新结点，使新插入结点成为当前结点的左孩子结点
2,在二叉树的当前结点上插入一个新结点，使新插入结点成为当前结点的右孩子结点
3,在二叉树的当前结点上插入一个子树，使新插入子树成为当前结点的左子树
4,在二叉树的当前结点上插入一个子树，使新插入子树成为当前结点的右子树
5,删除二叉树的当前结点的左孩子结点
6,删除二叉树的当前结点的右孩子结点
7,删除二叉树的当前结点的左子树
8,删除二叉树的当前结点的右子树
Data Structure LXJ
二叉树的操作
第三类操作，遍历二叉树,（遍历）
1,中序遍历（ LDR）二叉树
中序遍历根结点的左子树（ L）
访问根结点（ D）
中序遍历根结点的右子树（ R）
2,前序遍历（ DLR）二叉树
访问根结点（ D）
前序遍历根结点的左子树（ L）
前序遍历根结点的右子树（ R）
3,后序遍历（ LRD）二叉树
后序遍历根结点的左子树（ L）
后序遍历根结点的右子树（ R）
访问根结点（ D）
Data Structure LXJ
二叉树的遍历
LDR,D H B E A F I C G
DLR,A B D H E C F I G
LRD,H D E B I F G C A
层序遍历
A B C D E F G H I
A
B C
D E F G
H I
二叉树的前序遍历后中序遍历可以确定一颗二叉树
当规定了遍历方法后，二叉树也像单链表一样
一颗二叉树的遍历序列不能确定一颗二叉树
Data Structure LXJ
7.3.3 二叉树的存储结构
1,二叉树的顺序存储结构
A
B C
D E F
a）完全二叉树的存储 b）一般二叉树的存储
FEDCBA
543210
FED?CBA
6543210
A
B C
D E F
Data Structure LXJ
二叉树的存储结构
2,二叉树链式存储结构
leftChild data rightChild
A
B C
D E F A
B C
D E F?
root
a）二叉树结点结构 b）二叉树链式存储结构
1,优点,寻找孩子简单
2,缺点,寻找双亲麻烦
3,解决方法,用三叉链式存储代替二叉链式存储
Data Structure LXJ
二叉树的存储结构
3,二叉树仿真指针存储结构
A
B C
D E F
a）二叉树仿真指针存储结构下标 data leftChild rightChild
－ 1
1
－ 1
5
3
2
－ 1F
－ 1E
－ 1D
4C
－ 1B
1A
5
4
3
2
1
0
Data Structure LXJ
7.3.5 树和二叉树的转换
1,树转换为二叉树
a,树中所有相同双亲结点的兄弟之间加一条连线；
b,树中每个结点，保留它与第一个孩子之间的连线，删除与其他孩子之间的连线；
c,整理所有保留和添加的线，使结点孩子连线位于左孩子指针位置，使结点兄弟位于右孩子指针位置。
d,完毕,c图表示法 也即是 树的孩子兄弟表示法
A
B D
E F G
C
A
B D
E F G
C
A
B D
E F G
C
A
B
D
E
F
G
C
a） b） c）树
Data Structure LXJ
树和二叉树的转换
2,二叉树还原为树
a,若该结点是双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子 … 都与该结点的双亲结点连接起来；
b,删除原二叉树中所有双亲结点与右孩子结点的连线；
c,整理所有保留和添加的线，使每个结点的孩子结点连线顺序位于下方孩子结点位置。
A
B
D
E
F
G
C
A
B
D
E
F
G
C
A
B
D
E
F
G
C
A
B D
E F G
C
a） b） c） 树
Data Structure LXJ
7.4 链式存储结构的二叉树设计两种方法：
1。设计一个结点类，然后在结点类的基础上设计出需要实现的二叉树操作的函数。（通过外部函数）
优点：实现比较简单因为二叉树是一种递归定义，所以对结点的操作也能对二叉树操作。
缺点 （ 1）当二叉树结构比较复杂时，结点类不能够给出二叉树结点之间关系的成员函数；
（ 2）需要定义的结点类对像也会很多；
（ 3）用外部函数实现也不够规范。
Data Structure LXJ
7.4 链式存储结构的二叉树设计
2。在设计的节点类的基础上在设计一个二叉树类，二叉树类的成员函数包括了基本操作
Data Structure LXJ
7.4 链式存储结构的二叉树设计
#include <iostream.h>
#include <stdlib.h>
template <class T> class BiTreeNode
{
private:
BiTreeNode<T>* leftChild; //左子树指针
BiTreeNode<T>* rightChild; //右子树指针
public:
T data;
//构造函数和析构函数
BiTreeNode():leftChild(NULL),rightChild(NULL){}
BiTreeNode(T item,BiTreeNode<T>* left= NULL,
BiTreeNode<T>* right = NULL):
data(item),leftChild(left),rightChild(right){}
~BiTreeNode(){}
//结点操作的成员函数
BiTreeNode<T>*& Left(void){return leftChild;}
BiTreeNode<T>*& Right(void){return rightChild;}
};
Data Structure LXJ
7.4 链式存储结构的二叉树设计
//定义一个由结点构造二叉树的外部函数
template<class T>
BiTreeNode<T>* getTreeNode(Titem,
BiTreeNode<T> *left = NULL,
BiTreeNode<T>* right = NULL)
{
BiTreeNode<T>* p;
p = new BiTreeNode<T>(item,left,right);
if(p == NULL)
{
cerr << "内存分配失败！ \n";
exit(1);
}
return p;
}
A
B C
D E F
Data Structure LXJ
7.4 二叉树的遍历
template<class T>
void PreOrder(BiTreeNode<T>*& t,void visit(T item))
//使用 visit(item)函数前序遍历二叉树
{
if(root != NULL)
{
visit(t->data);
PreOrder(t->Left(),visit);
PreOrder(t->Right(),visit);
}
}
visit是函数参数。
A
B C
D E F
Data Structure LXJ
template<class T>
void InOrder(BiTreeNode<T>*& t,void visit(T item))
//使用 visit(item)函数中序遍历二叉树
{
if(t != NULL)
{
InOrder(t->Left(),visit);
visit(t->data);
InOrder(t->Right(),visit);
}
}
A
B C
D E F
7.4 二叉树的遍历
Data Structure LXJ
template<class T>
void PostOrder(BiTreeNode<T>*& t,void visit(T
item))
//使用 visit(item)函数后序遍历二叉树
{
if(t != NULL)
{
PostOrder(t->Left(),visit);
PostOrder(t->Right(),visit);
visit(t->data);
}
}
A
B C
D E F
7.4 二叉树的遍历
Data Structure LXJ
#include "LineQueue.h" //包含模板链式队列类
template<class T>
void LevelScan(BiTreeNode<T>*& t,void visit(T item))
//使用 visit(item)函数层序遍历二叉树
{
LinQueue<BiTreeNode<T>*> q; //定义模板链式队列类对象
BiTreeNode<T>* p;
q.QInsert(t); //根结点入队
while(!q.QueueEmpty())
{
p = q.QDelete(); //出队列
visit(p->data); //访问根结点
if(p->Left() != NULL) //根结点的左子树入队列
q.Qinsert(p->Left()); //根结点的右子树入队列
if(p->Right() != NULL)
q.Qinsert(p->Right());
}
}
A
B C
D E F
7.4 二叉树的遍历
Data Structure LXJ
计算二叉树的深度，叶子结点个数，查找元素，
分层显示二叉树结点数据域值两类：
1。不考虑遍历顺序
2。考虑遍历顺序
7.4 二叉树的遍历的应用
A
B C
D E F
Data Structure LXJ
template<class T>
int Depth(BiTreeNode<T>*& root)
//返回计算出的二叉树的深度
{
int depthleft,depthright,depthval;
if(root == NULL) depthval = 0;
else
{
depthleft = Depth(root->Left());
depthright = Depth(root->Right());
//二叉树的深度为左子树和右子树深度的最大值加根结点的深度值 1
depthval = 1 + (depthleft > depthright? depthleft,
depthright);
}
return depthval;
}
7.4 二叉树的遍历的应用
A
B C
D E F
Data Structure LXJ
template<class T>
int CountLeaf(BiTreeNode<T>*& root,int& count)
//计算二叉树 root的叶子结点个数并存与 count中
{
if(root != NULL)
{
CountLeaf(t ->Left(),count);
CountLeaf(t->Right(),count);
if(t->Left() == NULL && t->Right() == NULL)
count++;
}
}
7.4 二叉树的遍历的应用
A
B C
D E F
Data Structure LXJ
template<class T>
BiTreeNode<T>* Find(BiTreeNode<T>*& root,T item)
//在二叉树 root中回溯查找数据元素 item找到时返回该结点指针，
否则返回空
{
if(root == NULL) return NULL;
if(root->data == item || root->data == item)
return root;
BiTreeNode<T>* p;
if((p = Find(root->Left(),item)) != NULL) return p;
if((p = Find(root->Right(),item)) != NULL) return p;
return NULL;
}
7.4 二叉树的遍历的应用
A
B C
D E F
Data Structure LXJ
template<class T>
void PrintTree(BiTreeNode<T>*& root,int level)
//二叉树 root第 level层结点数据域值的横向显示
{
if(root != NULL)
{
//二叉树 root->Right()第 level+1层结点数据域值的横向显示
PrintTree(root->Right(),level + 1);
if(level != 0)
{
//走过 6 * (level - 1)个空格
for(int i = 0;i < 6 * (level - 1);i++) cout << " ";
cout << "----"; //显示横线 ----
}
cout << root-> data << endl; //显示结点的数据域值
//二叉树 root->Left()第 level+1层结点数据域值的横向显示
PrintTree(root->Left(),level + 1);
}
}
7.4 二叉树的遍历的应用
Data Structure LXJ
7.4 链式存储结构的二叉树设计两种方法：
1。设计一个结点类，然后在结点类的基础上设计出需要实现的二叉树操作的函数。（通过外部函数）
优点：实现比较简单因为二叉树是一种递归定义，所以对结点的操作也能对二叉树操作。
缺点 （ 1）当二叉树结构比较复杂时，结点类不能够给出二叉树结点之间关系的成员函数；
（ 2）需要定义的结点类对像也会很多；
（ 3）用外部函数实现也不够规范。
Data Structure LXJ
7.4 链式存储结构的二叉树设计
2。二叉树类在设计的节点类的基础上在设计一个二叉树类，二叉树类的成员函数包括了基本操作
Data Structure LXJ
7.4 链式存储结构的二叉树设计
#include <iostream.h>
#include <stdlib.h>
template <class T> class BiTreeNode
{
private:
BiTreeNode<T>* leftChild; //左子树指针
BiTreeNode<T>* rightChild; //右子树指针
public:
T data;
//构造函数和析构函数
BiTreeNode():leftChild(NULL),rightChild(NULL){}
BiTreeNode(T item,BiTreeNode<T>* left= NULL,
BiTreeNode<T>* right = NULL):
data(item),leftChild(left),rightChild(right){}
~BiTreeNode(){}
//结点操作的成员函数
BiTreeNode<T>*& Left(void){return leftChild;}
BiTreeNode<T>*& Right(void){return rightChild;}
};
Data Structure LXJ
//page 7.4.5二叉树类
#include <iostream.h>
#include <stdlib.h>
#include "BiTreeNode.h"
template<class T> class BiTree
{
private:
BiTreeNode<T> *root;
//实现相应共有成员函数的算法
void PreOrder(BiTreeNode<T> *&t,void (*visit)(T item));
void InOrder(BiTreeNode<T> *&t,void (*visit)(T item));
void PostOrder(BiTreeNode<T> *&t,void (*visit)(T item));
public:
…
7.4.5 二叉树类
A
B C
D E F
Data Structure LXJ
7.4 链式存储结构的二叉树设计
public:
//构造函数和析构函数
BiTree():root(NULL){};
~BiTree(){};
//构造二叉树
void MakeTree(const T &item,BiTree<T> &left,BiTree<T>
&right);
//遍历访问树
void PreOrder(void (*visit)(T item)); //前序遍历访问树
void InPreOrder(void (*visit)(T item)); //中序遍历访问树
void PostOrder(void (*visit)(T item)); //后序遍历访问树
}; A
B C
D E F
Data Structure LXJ
构造树和删除树的根结点
1,构造树和删除树的根结点
template<class T>
void BiTree<T>::MakeTree(const T &item,BiTree<T>
&left,BiTree<T> &right)
//构造数据域为 item左子树为 left 右子树为 right的二叉树
{
root = new BiTreeNode<T>(item,left.root,right.root);
}
left.root = right.root = NULL;
Data Structure LXJ
7.4 链式存储结构的二叉树设计
template<class T>
void BiTree<T>::PreOrder( void (*visit)(T item) )
//用 visit(item)函数前序遍历访问当前对象的二叉树的公有函数
{
PreOrder(root,visit);
}
template<class T>
void BiTree<T>::PreOrder(BiTreeNode<T> *&t,void (*visit)(T
item))
//用 visit(item)函数前序遍历访问二叉树 t的私有函数
{
if(root != NULL)
{
visit(t -> data);
PreOrder(t ->Left(),visit);
PreOrder(t->Right(),visit);
}
}
不用给出二叉树对象的根结点的指针但为了实现二叉树的递归遍历，
根结点这个指针参数是必需的
Data Structure LXJ
7.4 链式存储结构的二叉树设计
#include "BiTree.h"
template<class T>
void Visit<T>(T item)
{
cout << item << " ";
}
void main(void)
{
BiTree<char> a,b,c,d,e,f,g,null;
g.MakeTree('G',null,null);
d.MakeTree('D',null,g);
b.MakeTree('B',d,null);
e.MakeTree('E',null,null);
f.MakeTree('F',null,null);
c.MakeTree('C',e,f);
a.MakeTree('A',b,c);
cout << "前序遍历序列为,";
a.PreOrder(Visit);
}
A
B C
D E F
G
Data Structure LXJ
第六部分线索二叉树
Data Structure LXJ
线索二叉树
1,二叉树的二叉链表存储：反复递归操作
2,二叉树游标化：类似单链表的简单操作
3,线索二叉树：线索化后的二叉树结点更容易找到其的前驱和后继，
线索二叉树的优点：遍历查找方便快捷，从任何结点可以向前向后搜索
线索二叉树的用途：需要反复遍历和查找的二叉树
本节内容：
1,线索二叉树的存储结构
2,线索二叉树类
3,中序线索二叉树类
Data Structure LXJ
7.6.1 线索二叉树的存储结构
按某种规则遍历二叉树时把二叉树的结点排成一个线性结构,本质 上就是对一个非线性结构进行线性化操作
保存这种按某种规则遍历二叉树时得到的每个结点的后继结点信息和前驱结点信息，就构成线索二叉树结点的存储结构
1,对二叉树以某种遍历方式使其变为线索二叉树的过程称作按该种方式对二叉树进行的 线索化。
Data Structure LXJ
线索二叉树结点结构
带线索的二叉树，即每个结点都带有指向其前驱和后继的指针的二叉树
结点域说明，加入了标志域
1,leftThread = 0 leftChild 指向左孩子结点
2,= 1 指向前驱
3,rightThread = 0 rightChild 指向右孩子结点
4,= 1 指向后继
结点存储结构中指向前驱结点的指针和指向后继结点的指针称为 线索
leftChild leftThread data rightThread rightChild
Data Structure LXJ
中序线索二叉树
1,增加头结点使算法设计方便
2,头结点 左孩子 指向根结点,右线索 指向遍历算法的最后一个结点
A
B C
D E F?
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
a）二叉树 b）中序线索二叉树
Data Structure LXJ
前序线索二叉树
A
B C
D E F?
a）二叉树 b）前序线索二叉树
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
Data Structure LXJ
后序线索二叉树
A
B C
D E F?
a）二叉树
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
b）后序线索二叉树
Data Structure LXJ
7.6.2 线索二叉树类
线索二叉树类定义所有或实现各种不同的线索二叉树类共同的操作，为各种不同的线索二叉树提供相同的操作；
如成员函数,First(),Next(),EndOfNext()构成线索二叉树的正向遍历的循环结构；
又如成员函数,Last(),Prior(),EndOfPrior()
构成线索二叉树的反向遍历的循环结构；
当然不同遍历方法实现的线索二叉树的具体函数算法是不同的，将在具体的派生类中实现。
Data Structure LXJ
类层次图线索二叉树后序线索二叉树前序线索二叉树 中序线索二叉树
Data Structure LXJ
线索二叉树类定义
template <class T> class ThreadIterator
{
protected:
BiTrThNode<T> *root;
BiTrThNode<T> *root;
int nextComplete;
int priorComplete;
public:
//构造函数
ThreadIterator（ BiTrThNode<T> *&tree） ;
//数据检索和修改成员函数
T& Data(void);
…
Data Structure LXJ
线索二叉树类定义
…
//算法需要的成员函数
virtual void First(void) = 0; //纯虚函数
virtual void Next(void) = 0; //纯虚函数
virtual void Last(void) = 0; //纯虚函数
virtual void Prior(void) = 0; //纯虚函数
virtual void EndOfNext(void)const
{
return nextComplete;
}
virtual void EndOfPrior(void)const
{
return priorComplete;
}
};
Data Structure LXJ
线索二叉树的构造函数
template<class T>
ThreadIterator<T>::ThreadIterator(BiTrThNode<T>*& tree)
//构造函数
{
root = tree;
current = root;
if(tree == NULL)
{
nextComplete = 1;
priorComplete = 1;
}
else
{
nextComplete = 0;
priorComplte = 0;
}
}
Data Structure LXJ
返回二叉树结点值
template <class T>
T& ThreadIterator<T>::Data(void)
//返回线索二叉树的数据域值
{
if(root == NULL)
{
cout << "二叉树空！ " << endl;
exit(1);
}
return current->data;
}
Data Structure LXJ
7.6.3 中序线索二叉树类
类中将定义的两类函数：
1,中序线索二叉树类将具体实现基类中的和遍历相关的 4个虚函数，以方便对该二叉树的查找等操作。
2,实现中序线索化函数 CreateInThread()和
InThread()
1,中序线索化函数具体实现是在二叉树的 中序遍历 过程中给每个结点添加线索信息；
2,线索二叉树在没有被线索化之前可以按一般二叉树看待。
Data Structure LXJ
中序线索二叉树类定义
template <class T>
class InThreadIterator:public ThreadIterator<T> //继承
{
private:
void InThread(BiTrThNode<T> *& tree,
BiTrThNode<T> *&pre);
public:
//构造函数
InThreadIterator(BiTrThNode<T>*&
tree):ThreadIterator<T>(tree){};
void CreadInThread();
virtual void First(void);
virtual void Next(void);
virtual void Last(void);
virtual void Prior(void);
};
Data Structure LXJ
中序线索化函数－ CreatInThread()
template <class T>
void InThreadIterator<T>::CreatInThread()
//中序线索化二叉树
{
BiTrThNode<T> *t = root;
root = new BiTrThNode<T>;
root->leftThread = 0;
root ->rightThread = 1;
if(t == NULL)
{
root->leftChild = root;
root->rightChild = root;
}
…
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
Data Structure LXJ
CreatInThread()
…
else //当树非空
{
current = root->leftChild = t; //置头结点的左指针
root->leftThread = 0; //置头结点的左标志
BiTrThNode<T>* pre = root;
InThread(current,pre); //中序线索化二叉树
pre->rightChild = root; //置最后一个结点的右线索
pre->rightThread = 1; //置最后一个结点的右标志
root->rightChild = pre; //置头结点的右线索
root->rightThread = 1; //置头结点的右标志
}
}
Data Structure LXJ
中序线索化函数－ InThread()
templage <class T>
void InThreadIterator<T>::InThread(BiTrThNode<T>*&
current,BiTrThNode<T>*& pre)
//中序线索化二叉树,current为当前指针，
//pre为当前结点的中序前驱结点指针
{
if(current != NULL)
{
InThread(current->leftChild,pre);//中序线索化左子树
if(current -> leftChild == NULL) //当前结点左子树为空
{
current->leftChild = pre; //建立左线索指针
current->leftThread = 1; //建立左线索标记
}
…
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
Data Structure LXJ
InThread()
…
if(pre->rightChild = current)
{
pre->rightChild = current;
pre->rightThread = 1;
}
pre = current;
InThread(current->rightChild,pre);
}
}
root
F1 1
A0 0
B1 0 C0 0
D1 1 E1 1
0 1
Data Structure LXJ
Next()
template <class T>
void InThreadIterator<T>::Next(void)
//使当前结点指针指向当前结点的下一个结点，到尾部时正序结束标记置为 1
{
if(nextComplete == 1)
{
err << "已到二叉树 !" << endl;
exit(1);
}
//使当前结点指针指向当前结点的下一个结点
BiTrThNode<T> *p = current->rightChild;
if(current->rightThread == 0)
while(p->leftThread == 0) p = p－ >leftChild;
current = p;
if(current == root) nextComplete = 1;
}
Data Structure LXJ
遍历 线索二叉树 (补充 )
遍历线索二叉树,
有了线索二叉树，就容易遍历二叉树了．
只要
（１）先找要遍历的第一个结点；
（２）然后依次找结点的后继；
（３）重复（２）直到其后继为头结点．
所有问题归为如何在线索二叉树中找结点的后继？
Data Structure LXJ
1）遍历中序线索二叉树
（ 1）中序线索二叉树中，找结点的后继算法算法思想,对任意结点 p，若 rtag=1，则
rchild指向该结点的后继；若 rtag=0，则
rchild指向该结点的右孩子，此时，应从右孩子开始，沿左指针前进，直到找到没有左孩子的结点 s（ ltag=1）,则 s就是 p的后继，即后继是中序遍历右子树时，访问的第一个结点；
Data Structure LXJ
中序线索二叉树中，找结点的后继 算法
BiThrTree in_next(p,thrt)
BiThrTree p,thrt;
{ /*在以 thrt为头指针的中序线索二叉树上,*/
/*查找指针 p所指结点的后继 */
s=p->rchild；
if (p->rtag==0)
while (s->ltag=0)
s= s->lchild；
return s;
}//in_next
p
1
s
p
0
1
0
s
Data Structure LXJ
（ 2）遍历中序线索二叉树算法
void thrt_inorder(BiThrTree thrt)
{//遍历以 thrt为头指针的中序线索二叉树
p=thrt->lchild；
while (p->lchild<>thrt) p= p->lchild;
//定位要遍历的第一个结点,
while (p<>thrt) { visit(p->data)；
p=in_next(p,thrt);}
}//thrt_inorder
p-> ltag==0
Data Structure LXJ
2）遍历后序线索二叉树
（ 1）后序线索二叉树中，找结点的后继算法算法思想,对任意结点 p，
若 p为二叉树的根，则无后继 ;
若 p是双亲的右孩子、或是独生左孩子，则后继为双亲；
若 p是有兄弟的左孩子，则后继为双亲的右子树上按后序遍历时，访问的第一个结点 (叶结点 )；
s
p
s
p
s
p
s
Data Structure LXJ
后序线索二叉树中，找结点的后继 算法
BiThrTree post_next(p,thrt)
BiThrTree p,thrt;
{//在以 thrt为头指针的后序线索二叉树上,
//查找指针 p所指结点的后继
s=parent（ thrt,p）； //在 thrt上查找 p的双亲
if (s==thrt) return thrt；
if (s->rchild==p)||(s->rtag==1)return s；
while (s->rtag==0)
{ s= s->rchild；
while (s->ltag==0) s= s->lchild； }
return s;
}//post_next
Data Structure LXJ
（ 2）遍历后序线索二叉树算法
void thrt_postorder(BiThrTree thrt)
{//遍历以 thrt为头指针的后序线索二叉树
if (thrt!=thrt->lchild)
{ p=thrt->lchild； search=1；
while (search)
{ while (p->ltag==0) p= p->lchild；
if (p->rtag==0) p= p->rchild;
else search=0； }
while (p!=thrt) { visit(p↑.data) ；
p=post_next(p,thrt)}}
}//thrt_postorder
Data Structure LXJ
3）遍历先序线索二叉树
（ 1）先序线索二叉树中，找结点的后继算法算法思想,对任意结点 p:
若 p有左孩子，则后继为左孩子 ;
若 p无左孩子,有右孩子，则后继为右孩子；
若 p无左孩子,也无右孩子，则后继为右线索；
Data Structure LXJ
先序线索二叉树中，找结点的后继 算法
BiThrTree pre_next(p,thrt)
BiThrTree p,thrt;
{//在以 thrt为头指针的先序线索二叉树上,
//查找指针 p所指结点的后继
if (p->ltag==0) return(p->lchild)；
else return p->rchild;
}//pre_next
Data Structure LXJ
（ 2）遍历先序线索二叉树算法
void thrt_preorder(BiThrTree thrt)；
{ //遍历以 thrt为头指针的先序线索二叉树
p=thrt->lchild；
while (p!=thrt)
{ visit(p->data)；
p=pre_next(p,thrt)}
}//thrt_preorder
Data Structure LXJ
第七部分堆
Data Structure LXJ
7.7.1 堆的定义
堆 （ heap）是具有如下特点的 完全二叉树,
1,若根结点存在左（右）孩子，则根结点值 小于等于 （大于等于）左（右）孩子结点值；
2,以左右孩子为根的子树又各是一个堆。
12
24 16
59 66 72 38
80
Data Structure LXJ
堆分类
12
24 16
59 66 72 38
80
88
76 32
50 10 16 9
a）小顶堆 b）大顶堆
Data Structure LXJ
堆的存储
堆是一个完全二叉树,故可用数组来存放堆元素
根据数组下标和完全二叉树的性质就可数组中找出双亲－孩子 关系和 大小 比较
12
24 16
59 66 72 38
80
38726659162412
6543210
80
7
a）堆 b）堆的存储
Data Structure LXJ
7.7.2 最小堆类－ Class MinHeap
template <class T> class MinHeap
{
private:
T* heapArray; //存放数据元素的数组
int markArray; //标记
int MaxHeapSize； //最大元素个数
int heapsize; //当前元素个数
void FilterUp(int i); //插入元素后重新堆化
void FilterDown(int i); //删除元素后重新堆化
…
Data Structure LXJ
Class MinHeap
…
public:
MinHeap(int maxSize); //构造函数
//拷贝构造函数，用于把 n个元素的数组堆化
MiniHeap(T arr[],int n);
~MiniHeap(void)
{if (markArray == 0) delete heapArray;}
void Insert(const T& item);
T Delte(void);
T GetHeapTop() const {return heapArray[0]}
int HeapSize(void)const {return heapSize;}
int HeapEmpty(void)const {return heapSize == 0;}
int HeapFull(void)const
{return heapSize == MaxHeapSize;}
};
Data Structure LXJ
1、插入数据元素操作第一步,插入数据结点 15
1,currentPos = 8
2,计算,parentPos = (8 – 1)/ 2 =3
3,比较,heapArray[3] > heapArray[8],不满足 小顶堆定义，应该交换位置
38726659162412
6543210
80
7
15
8
12
24 16
59 66 72 38
80 15
heapArray
Data Structure LXJ
插入数据元素第二步,交换数据结点 59<－ >15
1,heapArray[1] <-> heapArray[3]
2,currentPos = 3
3,计算,parentPos = (3 – 1)/ 2 =1
4,比较,heapArray[1] > heapArray[3],不满足 小顶堆定义，应该交换位置
38726615162412
6543210
80
7
59
8
12
24 16
15 66 72 38
80 59
heapArray
Data Structure LXJ
插入数据元素第三步,交换数据结点 24<－ >15
1,heapArray[3] <-> heapArray[8]
2,currentPos = 1
3,计算,parentPos = (1 – 1)/ 2 =0
4,比较,heapArray[1] < heapArray[3],满足 小顶堆定义，结束
38726624161512
6543210
80
7
59
8
12
15 16
24 66 72 38
80 59
heapArray
Data Structure LXJ
12
24 16
59 66 72 38
80 15
12
15 16
24 66 72 38
80 59
38726659162412
6543210
80
7
15
8
heapArray
38726615162412
6543210
80
7
59
8
38726624161512
6543210
80
7
59
8
38726659162412
6543210
80
7 8
插入操作
a）插入前后 b）数据元素移动过程
Data Structure LXJ
2、删除数据元素操作第一步,删除数据结点 12
38726659162412
6543210
80
7
12
24 16
59 66 72 38
80
heapArray
第二步,移动该结点为根结点的子堆中最后一个元素填删除位置
38726659162480
6543210 7
80
24 16
59 66 72 38
80
heapArray
Data Structure LXJ
删除数据元素第三步：
1,计算左右孩子位置
2,并和左右孩子结点比较大小
38726659162480
6543210 7
80
24 16
59 66 72 38
heapArray
第四步：
1,和最小的孩子交换位置
2,并和左右孩子结点比较大小
16
24 80
59 66 72 38
38726659802416
6543210 7
heapArray
Data Structure LXJ
删除数据元素第五步：
1,和最小的孩子交换位置
2,80结点无孩子，不用再移动，算法结束
16
24 38
59 66 72 80
80726659382416
6543210 7
heapArray
16
24 38
59 66 72 80
80726659382416
6543210 7
heapArray
最后结果：符合小顶堆定义
Data Structure LXJ
3、数组堆化操作
堆化：把一个有 n个数据元素的数组构造成一个堆。
方法 1：生成一个空堆，利用前面插入算法插入数组中每个元素，每插入一个元素使新数组仍然为堆
方法 2：利用原有数组，移动数据元素达到目的
Data Structure LXJ
数组堆化－ 方法 1
24 24
10
10
24
33251677901024 89 67 array
10
24 90
10
24 90
77
10
24 90
77 16
10
16 90
77 24
10
16 90
77 24 25
10
16 25
77 24 90
10
16 25
77 24 90 33
插入 24 插入 10 插入 90 插入 77
插入 16 插入 25 插入 33
Data Structure LXJ
数组堆化－ 方法 1
33251677901024 89 67 array
10
16 25
77 24 90 33
89
10
16 25
77 24 90 33
89 67
10
16 25
67 24 90 33
89 77
插入 89 插入 67
33902467251610 89 77堆中数组：
Data Structure LXJ
数组堆化操作－方法 2
1、调整最后一个叶子结点的双亲结点构成的子树为一个堆
（最后一个叶子结点的双亲结点为 currentPos）
2、调整该结点前一个结点所形成的一个子树为一个堆
(currentPos=
currentPos-1)
3、直到根结点（下标为 0）
24
10 90
77 16 25 33
89 67
Data Structure LXJ
数组堆化－ 方法 2
24
10 90
77 16 25 33
89 67
24
10 90
67 16 25 33
89 77
24
10 90
67 16 25 33
89 77
24
10 25
67 16 90 33
89 77
第一步第二步
Data Structure LXJ
24
10 25
67 16 90 33
89 77
数组堆化－ 方法 2
第三步
24
10 25
67 16 90 33
89 77
第四步
10
16 25
67 24 90 33
89 77
Data Structure LXJ
哈夫曼树（ Huffman）树是一类带权路径长度最短的树一,Huffman树（最优二叉树）
1,概念
两结点间的路径：从一结点到另一结点所经过的结点序列
路径长度：路径上的分支树
树的路径长度：从根到每一结点的路径长度之和
2
76
3
4
1
5
例
⑴ -⑵ -⑸ 为结点 1到 5之间的路径，其路径长度为 2，
树的路径长度 =l12 +l13+l14 +l15+ l16 +l17
=1+1+2+2+2+2=10
7.8 哈夫曼树
Data Structure LXJ
考虑带权时：设树中有 m个叶结点，每个叶结点带一个权值 wｉ 且根到叶结点 i的路径长度为 Li (ｉ =1,2，．,m），则树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。
Ｍ
即：ＷＰＬ＝ ∑ Ｗ ｋ Ｌ ｋ
Ｋ＝１
7.8 哈夫曼树
Data Structure LXJ
例：
使 WPL最小的二叉树成为最优二叉树 (Huffman 树 )
完全二叉树
dca b
7 5 2 4
c
d
ba
2
4
7 5
WPLa=2*7+2*5+2*2+2*4 WPLb=7*3+5*3+2*1+4*2
=36 =46
7.8 哈夫曼树
Data Structure LXJ
Huffman 树
WPLc=7*1+5*2+2*3+4*3
=35
b
dc
a
7
5
2 4
（ 1）完全二叉树并不一定是 Huffman树；
（ 2） HT是权值越大的越靠近根结点；
（ 3） HT不唯一，但
WPL一定相等。
7.8 哈夫曼树
Data Structure LXJ
2．构造 Huffman树算法
(1) 以权值分别为 W1,W2．．．Ｗ ｎ 的ｎ各结点，构成 n棵二叉树 T1,T2,．．,Tn并组成森林 F={T1,T2,．．,Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点；
(2) 在 F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值 =左右孩子权值之和，
叶结点的权值 = Wi）
(3) 从 F中删除这两棵二叉树，同时将新二叉树加入到 F中 ;
(4) 重复 (2),(3)直到 F中只含一棵二叉树为止，这棵二叉树就是 Huffman 树。
7.8 哈夫曼树
Data Structure LXJ
a b c d
7 5 2 4例,F={ }
a bF={ }
c d
7 5 6
2 4
F={ }a
b
c d
11
6
4
2
5
F={ }a
b
c d
11
6
425
7
18
7
7.8 哈夫曼树
Data Structure LXJ
HT不唯一性,可能出现在,
（ 1）构造新树时，左、右孩子未作规定。
（ 2）当有多个权值相同的树，可作为候选树时，选择谁未作规定。
二、哈夫曼编码（ Huffman 树的应用）
1、问题的提出通讯中常需要将文字转换成二进制字符串电文进行传送。文字 电文，称为 编码 。
反之，收到电文后要将电文转换成原来的文字，
电文 文字，称为 译码 。
7.8 哈夫曼树
Data Structure LXJ
例如：需将文字,ABACCDA”转换成电文。文字中 有四种字符，用 2位二进制便可分辨。
A B C D
00 01 10 11
编码方案 1：
则上述文字的电文为,00010010101100 共 14位。
译码时，只需每 2位一译即可。
特点：等长等频率编码，译码容易，但电文不一定最短,
7.8 哈夫曼树
Data Structure LXJ
A B C D
0 00 1 01
编码方案 2：
采用不等长编码，让出现次数多的字符用短码。
则上述文字的电文为,000011010 共 9位。
但无法译码，它即可译为 BBCCACA，也可译为
AAAACCDA等。
必须使任何一个字符得编码都不是另一个字符编码得前缀
7.8 哈夫曼树
Data Structure LXJ
A B C D
0 110 10 111
编码方案 3：
采用不等长编码，让出现次数多的字符用短码，
且任一编码不能是另一编码的前缀,即前缀编码。
则上述文字的电文为,0110010101110 共 13位。
7.8 哈夫曼树
Data Structure LXJ
设有 n种字符，每种字符出现的次数为 Wi,
其编码长度为 Li (i=1,2,．．,n)，
则整个电文总长度为 ∑ Wi Li,
要得到最短的电文，即使得 ∑ Wi Li最小。
也就是以字符出现的次数为权值，构造一棵 Huffman树，
并规定左分支编码位 0，右分支编码为 1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。
用构造 Huffman树编出来的码，称为 Huffman编码。
哈夫曼编码构造方法
7.8 哈夫曼树
Data Structure LXJ
对上例有,
1
A
3 C
B D
1
1
2 0
0
0
1 1
7.8 哈夫曼树
Data Structure LXJ
7.8 哈夫曼树
#include <iostream.h>
#include <stdlib.h>
const int MaxValue = 10000; //初始设定的权值最大值
const int MaxBit = 10; //初始设定的最大编码位数
const int MaxN = 10; //初始设定的最大结点个数
struct HaffNode
//哈夫曼树结点结构
{
int weight; //权值
int flag; //标记
int parent; //双亲结点下标
int leftChild; //左孩子下标
int rightChild; //右孩子下标
};
Data Structure LXJ
7.8 哈夫曼树
struct Code
//存放哈夫曼编码的数组元素结构
{
int bit[MaxN]; //数组
int start; //编码的起始下标
int weight; //字符的权值
};
Data Structure LXJ
7.8 哈夫曼树
void Haffman(int weight[],int n,HaffNode haffTree[])
//建立叶结点个数为 n权值数组为 weight的哈夫曼树 haffTree
{
int j,m1,m2,x1,x2;
//哈夫曼树 haffTree[]初始化。 n个叶结点共有 2n-1个结点
for (int i = 0;i < 2;i++ )
{
if(i < n)
haffTree[i].weight = weight[i];
else
haffTree[i].weight = 0;
haffTree[i].parent = 0;
haffTree[i].flag = 0;
haffTree[i].leftChild = -1;
haffTree[i].rightChild = -1;
}
Data Structure LXJ
7.8 哈夫曼树
//构造哈夫曼树 haffTree[]的 n-1个非叶结点
for (i = 0;i < n - 1 ;i++ )
{
m1 = m2 = MaxValue;
x1 = x2 = 0;
for (j = 0;j < n + 1 ;j++ )
{
if (haffTree[j].weight < m1 && haffTree[j].flag == 0)
{
m2 = m1;
x2 = x1;
m1 = haffTree[j].weight;
x1 = j;
}
else if(haffTree[j].weight < m2 && haffTree[j].flag == 0)
{
m2 = haffTree[j].weight;
x2 = j;
}
}
Data Structure LXJ
7.8 哈夫曼树
//将找出的两棵权值最小的子树合并为一棵子树
haffTree[x1].parent = n + i;
haffTree[x2].parent = n + i;
haffTree[x1].flag = 1;
haffTree[x2].flag = 1;
haffTree[n + i].weight = haffTree[x1].weight +
haffTree[x2].weight;
haffTree[n + i].leftChild = x1;
haffTree[n + i].rightChild = x2;
}
}
Data Structure LXJ
7.8 哈夫曼树
void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[])
//由 n个结点的哈夫曼树 haffTree[]构造哈夫曼编码 haffCode[]
{
Code* cd = new Code;
int child,parent;
//求 n个叶结点的哈夫曼编码
for (int i = 0;i < n;i++ )
{
cd->start = n - 1; //不等长编码的最后一位为 n-1
cd->weight = haffTree[i].weight; //取得编码对应权值得字符
child = i;
parent = haffTree[child].parent;
。。。
Data Structure LXJ
7.8 哈夫曼树
//由叶结点向上直到根结点
while (parent != 0)
{
if(haffTree[parent].leftChild == child)
cd->bit[cd->start] = 0;
else
cd->bit[cd->start] = 1;
cd -> start --;
child = parent;
parent = haffTree[child].parent;
}
//保存每个叶结点得编码和不等长编码得起始位
for (int j = cd->start + 1;j < n;j++ )
haffCode[i].bit[j] = cd -> bit[j];
haffCode[i].start = cd->start;
haffCode[i].weight = cd->weight; //记住编码对应权值的字符
}
}
Data Structure LXJ
7.8 哈夫曼树
void main(void)
{
int i,j,n = 4;
int weight[] = {1,3,5,7};
HaffNode * myHaffTree = new HaffNode[2*n+1];
Code* myHaffCode = new Code[n];
if (n > MaxN)
{
cout << "定义的 n越界，修改 MaxN！ " << endl;
exit(1);
}
Data Structure LXJ
7.8 哈夫曼树
Haffman(weight,n,myHaffTree);
HaffmanCode(myHaffTree,n,myHaffCode);
//输出每个叶结点的哈夫曼编码
for (i = 0;i < n;i++)
{
cout << "Weight = " << myHaffCode[i].weight << "Code
= ";
for (j = myHaffCode[i].start + 1;j < n;j++)
cout << myHaffCode[i].bit[j];
cout << endl;
}
}
/*程序运行结果如下：
Weiht = 1 Code = 100
Weiht = 3 Code = 101
Weiht = 5 Code = 11
Weiht = 7 Code = 0
*/
