【5-3】树与森林的遍历及应用课件

数据结构中国地质大学信息工程学院2013年秋1第五章树2内容提要5.1树的基本概念5.2二叉树5.3二叉树的存储表示5.4二叉树的遍历及其应用5.6树与森林5.7树与森林的遍历及其应用5.8堆及其应用5.9Huffman树及其应用35.6树与森林

1.树的存储表示树作为一种数据结构，既可以采用顺序存储结构，也可以采用链式存储结构。无论采用哪种存储结构，都要求它们既可以存储各结点本身的数据信息，又能够准确地反映树中各结点之间的逻辑关系。41.树的存储表示双亲表示法：父指针表示孩子表示法：子女链表表示双亲-孩子表示法：双亲表示法和孩子表示法孩子-兄弟表示法：左孩子-右兄弟链表5（1）双亲表示法用一组连续的存储空间（一维数组）存储树中的各结点，同时在每个结点中附设一个指示器，指示其双亲结点在数组中的序号。DataParentParent:指示双亲结点6ABCDEFGdataparentABCDEFG-10001130123456双亲表示示例优点：查找父节点的时间复杂度O(1)缺点：查找孩子节点的时间复杂度O(n)适用情况：经常需要查找父节点的应用！7DataParentFirstSonSiblingParent:指示双亲结点FirstSon：指示第一个孩子结点Sibling：指示第一个兄弟结点双亲表示法的改进8双亲表示法示例ABEDGFCHIJLKNM序号dataparent0A-11B02C03D04E15F16G27H38I39J310K511L512M813N8Fsonnext1-142637-1-1510-1-1-1-18129-1-1-111-1-1-113-1-19（2）孩子表示法树中的每个结点有零个或多个孩子结点，可以考虑用一个多重链表表示树，链表中的每个结点包括一个数据域和多个指针域。

数据域：存储树中结点的自身信息；

每个指针域指向该结点的一个孩子结点，通过每个指针反映树中各结点之间的关系。10孩子表示法示例无序树情形链表中各结点顺序任意有序树必须自左向右链接各个子女结点ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG012345611在一棵树中，由于各结点的度数不一样，因此，结点的指针域个数的设置有两种方法：（1）每个结点指针域的个数等于该结点的度数；（2）每个结点指针域的个数等于树的度数：当各结点的度数相差不大时，可以采用这种存储方法。多重链表的指针域12多重链表示例datapoint1point2point3缺点：每个节点需要等数量的指针域！ABCDEFGABCDEFG空链域2n+1个13孩子表示法的特点

优点：查找孩子节点的时间复杂度O(d)其中，d为树的度缺点：查找父节点的时间复杂度O(n)适用情况：经常需要查找孩子节点的应用！123∧45∧6∧∧∧∧∧ABCDEFG012345614（3）双亲-孩子表示法适用情况：查询父节点和孩子节点均很方便将双亲表示法和孩子表示法进行有机地结合。（1）将各结点的孩子结点分别组成单链表；（2）用一维数组顺序存储树中的各结点：数组元素包括结点本身的信息、它的双亲结点在数组中的序号、以及该结点的孩子结点链表的头结点。15序号dataparentlink0A-11B02C03D04E1^5F16G2^7H3^8I39J3^10K5^11L5^12M8^13N8^123^45^6^789^1011^1213^树的双亲-孩子表示法ABEDGFCHIJLKNM16（4）孩子-兄弟表示法又称二叉树表示法或二叉链表表示法。左孩子-右兄弟链表表示法链表中的每个结点有一个信息域和两个指针域。firstChilddatanextSibling

firstChild域：指向第一个孩子结点；

nextSibling域：指向下一个兄弟结点。17

datafirstChildnextSiblingABCDEFGABCDGFE孩子-兄弟表示法示例若想找某结点的所有子女，可先找firstChild，再反复用nextSibling沿链扫描。18孩子-兄弟表示法的特点

优点：查找孩子节点的时间复杂度O(d)其中，d为树的度,n为树中结点个数缺点：查找父节点的时间复杂度O(n)适用情况：经常需要查找孩子节点的应用！ABCDGFE19树节点定义template<classT>structTreeNode{ //树的结点类

Tdata; //结点数据

TreeNode<T>*firstChild,*nextSibling;

//子女及兄弟指针

TreeNode(Tvalue=0,TreeNode<T>*fc=NULL,

TreeNode<T>*ns=NULL)

:data(value),firstChild(fc),nextSibling(ns){}//构造函数};20template<classT>classTree{ //树类private:

TreeNode<T>*root,*current; //根指针及当前指针

intFind(TreeNode<T>*p,Tvalue);

//在以p为根的树中搜索valuevoidRemovesubTree(TreeNode<T>*p);

//删除以p为根的子树

boolFindParent(TreeNode<T>*t,TreeNode<T>*p);//在以t为根的子树中,寻找p的父节点，并置为当前节点public:树类的定义便于插入和查询21

Tree(){root=current=NULL;} //构造函数

boolRoot(); //置根结点为当前结点

boolIsEmpty(){returnroot==NULL;}boolFirstChild();

//将当前结点的第一个子女置为当前结点

boolNextSibling();

//将当前结点的下一个兄弟置为当前结点

boolParent();

//将当前结点的双亲置为当前结点

boolFind(Tvalue);

//搜索含value的结点,使之成为当前结点

…… //树的其他公共操作};树类的定义（续1）22树类的部分实现template<classT>boolTree<T>::Root()

{//让树的根结点成为树的当前结点

if(root==NULL){

current=NULL;returnfalse;}else{

current=root;returntrue;}}23template<classT>boolTree<T>::FindParent(TreeNode<T>*t,TreeNode<T>*p)

{//在根为*t的树中找*p的双亲,并置为当前结点

TreeNode<T>*q=t->firstChild;//*q是*t长子

boolsucc;while(q!=NULL&&q!=p){ //扫描兄弟链

if((succ=FindParent(q,p))==true)

returnsucc; //递归搜索以*q为根的子树

q=q->nextSibling;}if(q!=NULL&&q==p){current=t;returntrue;}else{current=NULL;returnfalse;}//未找到}树类的部分实现（续1）24template<classT>boolTree<T>::Parent()

{//置当前结点的双亲结点为当前结点

TreeNode<T>*p=current;if(current==NULL||current==root)

{current=NULL;returnfalse;}

//空树或根无双亲

returnFindParent(root,p); //从根开始找*p的双亲结点}树类的部分实现（续2）25template<classT>boolTree<T>::FirstChild()

{//在树中找当前结点的长子,并置为当前结点

if(current&¤t->firstChild){current=current->firstChild;returntrue;}current=NULL;returnfalse;}树类的部分实现（续3）26template<classT>boolTree<T>::NextSibling()

{//在树中找当前结点的兄弟,并置为当前结点

if(current&¤t->nextSibling)

{

current=current->nextSibling;returntrue;}

current=NULL;returnfalse;}树类的部分实现（续4）27template<classT>boolTree<T>::Find(TreeNode<T>*p,TValue){//在根为p的树中查找值为value的结点，并使之成为当前结点

boolresult=false;

if(p->data==value){result=true;current=p;}//搜索成功

else{TreeNode<T>*q=p->firstChild;

while(q!=NULL&&!(result==Find(q,value)))q=q->nextSibling;}

returnresult;}树类的部分实现（续5）28template<classT>boolTree<T>::Find(TValue){

if(IsEmpty())returnfalse;

returnFind(root,Value);}树类的部分实现（续6）292.树与二叉树的转换二叉树和树都可以用二叉链表作为存储结构，以二叉链表作为媒介可导出树与二叉树的一个对应关系——给定一棵树，可以找到唯一的一棵二叉树与之对应。从物理结构上来看，它们的二叉链表示相同的，只是解释不同而已。ABCDEFGABCEDGF30如何把树转换成二叉链表形式?ABCDEFGBCDGFEA1)凡是兄弟就用线连接起来2)对每个非叶子结点，除其最左孩子外，删去该结点与其他孩子结点的连线3)以根结点为轴心，顺时针旋转450ABCDEFG31A^D^^G^F^^ECB^K^L^^HI^M^J^^N^ABEDGFCHIJLKNM示例32ABEDCGFKLHIJMNA^D^G^^F^E^CBK^L^^H^IM^J^^N^^333.森林与二叉树的转换将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。森林与二叉树表示的转换可以借助树的二叉树表示来实现。34T1T2T3AFHT1T2T3ABCDGIJEKFBCDEGHIKJABCEDHIKJFG3

棵树的森林各棵树的二叉树表示森林的二叉树表示35森林转化成二叉树的规则若F

为空，即n=0，则对应的二叉树B

为空树。若F不空，则二叉树B的根是F第一棵树T1

的根；其左子树为B(T11,T12,…,T1m)，其中，T11,T12,…,T1m

是T1的根的子树；其右子树为B(T2,T3,…,Tn)，其中，T2,T3,…,Tn

是除T1

外其它树构成的森林。36二叉树转换为森林的规则如果B

为空，则对应的森林F

也为空。如果B

非空，则F中第一棵树T1

的根为B

的根；T1的根的子树森林{T11,T12,…,T1m}是由B

的根的左子树

LB

转换而来；F中除了T1

之外其余的树组成的森林{T2,T3,…,Tn

}是由B

的根的右子树RB

转换而成的森林。374.树的遍历及应用深度优先遍历先根次序遍历后根次序遍历树中不宜定义中根遍历广度优先遍历38（1）深度优先遍历树的先根次序遍历当树非空时访问根结点依次先根遍历根的各棵子树树先根遍历ABEFCDG对应二叉树前序遍历ABEFCDG树的先根遍历结果与其对应二叉树示的前序遍历结果相同树的先根遍历可以借助对应二叉树的前序遍历算法实现ABCEDGF39树的先根次序遍历的递归算法template<classT>voidTree<T>::PreOrder

(void(*visit)(BinTreeNode<T>*t)){//以当前指针current为根,先根次序遍历

if(!IsEmpty()){ //树非空

visit(current); //访问根结点

TreeNode<T>*p

=current;//暂存当前指针

current=current->firstChild;//第一棵子树

while(current!=NULL){

PreOrder(visit); //递归先根遍历子树

current=current->nextSibling;}current=p; //恢复当前指针

}}40ABCEDGF树的后根次序遍历当树非空时依次后根遍历根的各棵子树访问根结点树后根遍历EFBCGDA对应二叉树中序遍历EFBCGDA树的后根遍历结果与其对应二叉树表示的中序遍历结果相同树的后根遍历可以借助对应二叉树的中序遍历算法实现41template<classT>voidTree<T>::PostOrder(void(*visit)(BinTreeNode<T>*t)){//以当前指针current为根,按后根次序遍历树

if(!IsEmpty()){//树非空

TreeNode<T>*p=current;//保存当前指针

current=current->firstChild;//第一棵子树

while(current!=NULL){//逐棵子树

PostOrder(visit);

current=current->nextSibling;

}current=p;//恢复当前指针

visit(current);//访问根结点

}}树的后根次序遍历的递归算法42（2）广度优先遍历按广度优先次序遍历树的结果

ABCDEFG遍历算法用到一个队列。ABCEDGF43广度优先（层次次序）遍历算法template<classT>voidTree<T>::LevelOrder(void(*visit)(BinTreeNode<T>*t)){//按广度优先次序分层遍历树,树的根结点是当前指针current

Queue<TreeNode<T>*>Q;

TreeNode<T>*p;if(current!=NULL){//树不空

p=current;//保存当前指针

Q.EnQueue(current);//根结点进队列

44while(!Q.IsEmpty())

{Q.DeQueue(current);//退出队列

visit(current);//访问之

current=current->firstChild;while(current!=N