数据结构中的树

1树与二叉树2树和森林的概念两种树：自由树与有根树。

自由树： 一棵自由树Tf

可定义为一个二元组Tf

=(V,E)

其中V={v1,...,vn}

是由n(n＞0)个元素组成的有限非空集合，称为顶点集合。E={(vi,vj)|vi,vj

V,1≤i,j≤n}

是n-1个序对的集合，称为边集合，E

中的元素(vi,vj）称为边或分支。3自由树有根树： 一棵有根树T，简称为树，它是n(n≥0)

个结点的有限集合。当n=0时，T称为空树；否则，T

是非空树，记作

4r是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为m(m

0)个互不相交的有限集合T1,T2,…,Tm，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。5树的基本术语子女：若结点的子树非空，结点子树的根即为该结点的子女。双亲：若结点有子女，该结点是子女双亲。1层2层4层3层depth=4DACBIJHGFEMLK6兄弟：同一结点的子女互称为兄弟。度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。分支结点：度不为0的结点即为分支结点，亦称为非终端结点。叶结点：度为0的结点即为叶结点，亦称为终端结点。祖先：某结点到根结点的路径上的各个结点都是该结点的祖先。子孙：某结点的所有下属结点，都是该结点的子孙。7结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以下类推。深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。1层2层4层3层depth=4DACBIJHGFEMLK8高度：规定叶结点的高度为1，其双亲结点的高度等于它的高度加一。有序树：树中结点的各棵子树T0,T1,…是有次序的，即为有序树。无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。森林：森林是m（m≥0）棵树的集合。

9树的抽象数据类型template<classT>classTree{//对象:树是由n(≥0)个结点组成的有限集合。在//类界面中的position是树中结点的地址。在顺序//存储方式下是下标型,在链表存储方式下是指针//型。T是树结点中存放数据的类型,要求所有结//点的数据类型都是一致的。public:Tree();

~Tree();

10BuildRoot(constT&value);

//建立树的根结点

positionFirstChild(positionp);

//返回

p第一个子女地址,无子女返回0 positionNextSibling(positionp);

//返回p下一兄弟地址,若无下一兄弟返回0 positionParent(positionp);

//返回

p双亲结点地址,若

p为根返回0TGetData(positionp);

//返回结点

p中存放的值

boolInsertChild(positionp,T&value);

//在结点

p下插入值为

value的新子女,若插

//入失败,函数返回false,否则返回true11

boolDeleteChild(positionp,inti);

//删除结点p

的第

i

个子女及其全部子孙结

//点,若删除失败,则返回false,否则返回true

voidDeleteSubTree(positiont);

//删除以t

为根结点的子树

boolIsEmpty();

//判树空否,若空则返回true,否则返回false

voidTraversal(positionp);

//遍历以

p

为根的子树};

12二叉树的五种不同形态LLRR二叉树(BinaryTree)二叉树的定义

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。13二叉树的性质性质1

若二叉树结点的层次从1开始,则在二叉树的第i层最多有

2i-1

个结点。(i≥1)

[证明用数学归纳法]性质2

深度为k

的二叉树最少有k

个结点，最多有2k-1个结点。(k≥1)

因为每一层最少要有1个结点，因此，最少结点数为k。最多结点个数借助性质1：用求等比级数前k项和的公式20+21+22+…+2k-1=2k-114性质3

对任何一棵二叉树，如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0＝n2＋1

若设度为1的结点有n1个，总结点数为n， 总边数为e，则根据二叉树的定义，

n=n0+n1+n2

e

=2n2+n1=n-1

因此，有2n2+n1=n0+n1+n2-1

n2=n0-1n0=n2+115定义1

满二叉树(FullBinaryTree)

定义2

完全二叉树(CompleteBinaryTree)─若设二叉树的深度为k，则共有k层。除第k层外，其它各层(1～k-1)的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。16性质4

具有n(n≥0)个结点的完全二叉树的深度为log2(n+1)

设完全二叉树的深度为k，则有

2k-1-1<n

≤2k-1

变形2k-1<n+1≤2k

取对数

k-1<log2(n+1)≤k

有

log2(n+1)=k上面k-1层结点数包括第k层的最大结点数23-124-117性质5

如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,…,n，则有以下关系：

若i=1,则i无双亲若i>1,则i的双亲为i／2若2*i<=n,则i的左子女为

2*i， 若2*i+1<=n,则i的右子女为2*i+1若i为奇数,且i!=1,

则其左兄弟为i-1,若若

i为偶数,且i!=n,

则其右兄弟为i+11234856791018二叉树的抽象数据类型template<classT>classBinaryTree{//对象:结点的有限集合,二叉树是有序树public:

BinaryTree(); //构造函数

BinaryTree(BinTreeNode<T>*lch,

BinTreeNode<T>*rch,Titem);

//构造函数,以item为根,lch和rch为左、右子

//树构造一棵二叉树

intDepth(); //求树深度

intSize(); //求树中结点个数19

boolIsEmpty(); //判二叉树空否？

BinTreeNode<T>*Parent(BinTreeNode<T>*t);

//求结点t的双亲

BinTreeNode<T>*LeftChild

(BinTreeNode<T>*t);

//求结点t的左子女

BinTreeNode<T>*RightChild(BinTreeNode<T>*t);

//求结点t的右子女

boolInsert

(Titem); //在树中插入新元素

boolRemove(Titem); //在树中删除元素

boolFind(T&item); //判断item是否在树中

boolgetData(T&item); //取得结点数据20

BinTreeNode<T>*getRoot(); //取根

voidpreOrder(void(*visit)(BinTreeNode<T>*t)); //前序遍历,visit是访问函数

voidinOrder(void(*visit)(BinTreeNode<T>*t));

//中序遍历,visit是访问函数

voidpostOrder(void(*visit)(BinTreeNode<T>*t));

//后序遍历,(*visit)是访问函数

voidlevelOrder(void(*visit)(BinTreeNode<T>*t));

//层次序遍历,visit是访问函数};21完全二叉树一般二叉树的顺序表示的顺序表示二叉树的顺序表示1123456789

10

1412346789

12

14248910567312376489125101113221371531极端情形:只有右单支的二叉树137153123二叉树结点定义：每个结点有3个数据成员，data域存储结点数据，leftChild和rightChild分别存放指向左子女和右子女的指针。leftChilddatarightChilddataleftChildrightChild二叉链表二叉树的链表表示24leftChilddataparentrightChildparentdataleftChildrightChild三叉链表二叉树的链表表示每个结点增加一个指向双亲的指针parent，使得查找双亲也很方便。25二叉树链表表示的示例AAABBBCCCDDDFFFEEErootrootroot26二叉树遍历二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作

V

遍历根的左子树记作

L

遍历根的右子树记作

R则可能的遍历次序有

前序VLR

镜像VRL

中序

LVR

镜像RVL

后序LRV

镜像RLV27中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果

a+b*c

-

d

-

e/f中序遍历(InorderTraversal)--/+*abcdef28二叉树递归的中序遍历算法template<classT>voidBinaryTree<T>::InOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)){if(subTree!=NULL){

InOrder(subTree->leftChild,visit);

//遍历左子树

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

InOrder(subTree->rightChild,visit);

//遍历右子树

}};29前序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L)；前序遍历右子树(R)。遍历结果

-+a*b

-

cd/ef前序遍历(PreorderTraversal)--/+*abcdef30二叉树递归的前序遍历算法template<classT>voidBinaryTree<T>::PreOrder(BinTreeNode<T>*subTree,void(*visit)

(BinTreeNode<T>*t)){if(subTree!=NULL){

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

PreOrder(subTree->leftChild,visit);

//遍历左子树

PreOrder(subTree->rightChild,visit);

//遍历右子树

}};31后序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果

abcd

-*+ef/-后序遍历(PostorderTraversal)--/+*abcdef32二叉树递归的后序遍历算法template<classT>voidBinaryTree<T>::PostOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t){if(subTree!=NULL){

PostOrder(subTree->leftChild,visit);

//遍历左子树

PostOrder(subTree->rightChild,visit); //遍历右子树

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

}};33template<classT>intBinaryTree<T>::Size(BinTreeNode<T>*

subTree)const{//私有函数：利用二叉树后序遍历算法计算二叉//树的结点个数

if(subTree==NULL)return0; //空树

elsereturn1+Size(subTree->leftChild)

+

Size(subTree->rightChild);};应用二叉树遍历的事例34template<classT>intBinaryTree<T>::Height(BinTreeNode<T>*subTree)const{//私有函数：利用二叉树后序遍历算法计算二叉//树的高度或深度

if(subTree==NULL)return0; //空树高度为0 else{ inti=Height(subTree->leftChild);intj=Height(subTree->rightChild); return(i<j)?j+1:i+1; };35利用二叉树前序遍历建立二叉树以递归方式建立二叉树。输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归,此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整数序列空结点。36层次序遍历二叉树就是从根结点开始，按层次逐层遍历，如图：遍历顺序abcdef--+/*层次序遍历二叉树的算法37这种遍历需要使用一个先进先出的队列，在处理上一层时，将其下一层的结点直接进到队列（的队尾）。在上一层结点遍历完后，下一层结点正好处于队列的队头，可以继续访问它们。算法是非递归的。38abcdeQa访问a,进队Qa出队访问b,进队访问c,进队bcQb出队访问d,进队cdQc出队访问e,进队deQd出队eQe出队39层次序遍历的（非递归）算法template<classT>voidBinaryTree<T>::levelOrder(void(*visit)(BinTreeNode<T>*t)){if(root==NULL)return;

Queue<BinTreeNode<T>*>Q;

BinTreeNode<T>*p=root;

visit(p);Q.EnQueue(p);

while(!Q.IsEmpty()){Q.DeQueue(p);if(p->leftChild!=NULL){

40visit(p->leftChild);

Q.EnQueue(p->leftChild);}if(p->rightChild!=NULL){visit(p->rightChild);

Q.EnQueue(p->rightChild);}}};41由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例,前序序列{ABHFDECKG}

和中序序列{HBDFAEKCG

},构造二叉树过程如下：HBDFEKCGAEKCGABHDF42前序序列{ABHFDECKG}KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG43如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。固定前序排列，选择所有可能的中序排列，可能构造多少种不同的二叉树？61234578961237584944例如,有3个数据{1,2,3

}，可得5种不同的二叉树。它们的前序排列均为

123，中序序列可能是321，231，213，132，123。前序序列为123，中序序列为

312

的二叉树不存在。12312312312312345线索化二叉树

(ThreadedBinaryTree)又称为穿线树。通过二叉树的遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前驱、后继。46线索(Thread)增加前驱Pred指针和后继Succ指针的二叉树predleftChilddatarightChildsuccabcdepredpredpredsuccsuccsuccD∧∧AE∧∧B∧∧C∧∧rootpredpredpredpredsuccsuccsuccsucc47这种设计的缺点是每个结点增加两个指针，当结点数很大时存储消耗较大。改造树结点，将pred指针和succ指针压缩到leftChild和rightChild的空闲指针中，并增设两个标志ltag和rtag，指明指针是指示子女还是前驱／后继。后者称为线索。ltag(或rtag)=0，表示相应指针指示左子女（或右子女结点）；当ltag(或rtag)=1,表示相应指针为前驱（或后继）线索。leftChildltagdatartagrightChild

48leftChildltagdatartagrightChild

abcdepredpredpredsuccsuccsuccDAEB∧C∧rootpredpredsuccsucc0000111111线索化二叉树及其链表表示49线索化二叉树的类定义template<classT>structThreadNode{ //线索二叉树的结点类

intltag,rtag; //线索标志

ThreadNode<T>*leftChild,*rightChild;

//线索或子女指针

Tdata; //结点数据

ThreadNode(constTitem)//构造函数

:data(item),leftChild(NULL),rightChild(NULL),ltag(0),rtag(0){} };50template<classT>classThreadTree{ //线索化二叉树类protected:

ThreadNode<T>*root; //树的根指针

voidcreateInThread(ThreadNode<T>*current,

ThreadNode<T>*&pre);

//中序遍历建立线索二叉树

ThreadNode<T>*parent(ThreadNode<T>*t);

//寻找结点t的双亲结点public:

ThreadTree():root(NULL){} //构造函数51voidcreateInThread();//建立中序线索二叉树

ThreadNode<T>*First(ThreadNode<T>*current);

//寻找中序下第一个结点

ThreadNode<T>*Last(ThreadNode<T>*current);

//寻找中序下最后一个结点

ThreadNode<T>*Next(ThreadNode<T>*current);

//寻找结点在中序下的后继结点

ThreadNode<T>*Prior(ThreadNode<T>*current);

//寻找结点在中序下的前驱结点

……… };52通过中序遍历建立中序线索化二叉树0A00B00C00D00E0rootpre==NULLcurrent530A0

1B00C00D00E0rootpre==NULLcurrent540A0

1B00C0

1D00E0rootprecurrent550A0

1B00C0

1D1

0E0rootprecurrent560A0

1B00C0

1D1

1E0rootprecurrent570A0

1B00C0

1D1

1E1

rootprecurrent580A0

1B00C1

1D1

1E1

rootpre后处理59树的存储表示A(B(E,F),C,D(G))

结点的utype域没有画出ABCDEFGABEFCDG1、广义表表示60ABCDEFGdataparentABCDEFG-100011301234562、双亲表示树中结点的存放顺序一般不做特殊要求，但为了操作实现的方便，有时也会规定结点的存放顺序。例如，可以规定按树的前序次序存放树中的各个结点，或规定按树的层次次序安排所有结点。

613、子女链表表示无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG0123456624、子女指针表示一个合理的想法是在结点中存放指向每一个子女结点的指针。但由于各个结点的子女数不同，每个结点设置数目不等的指针，将很难管理。为此，设置等长的结点，每个结点包含的指针个数相等，等于树的度（degree）。这保证结点有足够的指针指向它的所有子女结点。但可能产生很多空闲指针，造成存储浪费。63等数量的链域ABCDEFG

datachild1child2child3childdABCDEFG空链域2n+1个645、子女-兄弟表示也称为树的二叉树表示。结点构造为：firstChild指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。nextSibling指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。若想找某结点的所有子女，可先找firstChild,再反复用nextSibling沿链扫描。

datafirstChildnextSibling65树的子女-

兄弟表示

datafirstChildnextSiblingABCDEFGABCDGFE66堆(Heap)template<classT,classE>classMinPQ{//最小优先级队列类的定义public:

VirtualboolInsert(E&d)=0;

VirtualboolRemove(E&d)=0;};

优先级队列每次出队列的是优先权最高的元素。用堆实现其存储表示，能够高效运作。67最小堆完全二叉树顺序表示

Ki≤K2i+1&&Ki≤K2i+2最大堆完全二叉树顺序表示Ki≥K2i+1&&Ki≥K2i+2090987877878454565653131532323531717堆的定义68堆的元素下标计算由于堆存储在下标从0开始计数的一维数组中，因此在堆中给定下标为i

的结点时如果

i=0，结点i

是根结点，无双亲；否则结点i

的父结点为结点(i-1)/2)；如果2i+1＞n-1，则结点i

无左子女；否则结点i

的左子女为结点2i+1；如果2i+2＞n-1，则结点i无右子女；否则结点i的右子女为结点

2i+2。69自下向上逐步调整为最小堆currentPos=i=3currentPos=i=25353171778780923456587i0923456587i将一组用数组存放的任意数据调整成堆70currentPos=i=15353171778780923456587i0923456587i71currentPos=i=05353171778780923456587i0923456587i09725353171778780923456587i0923456587i1773树的应用例子---决策树74树的应用例子---文件系统搜索树7576二叉搜索树(BinarySearchTree)定义

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：每个结点都有一个作为搜索依据的关键码(Key)，所有结点的关键码互不相同。左子树（如果非空）上所有结点的关键码都小于根结点的关键码。右子树（如果非空）上所有结点的关键码都大于根结点的关键码。左子树和右子树也是二叉搜索树。77351545504025102030二叉搜索树例结点左子树上所有关键码小于结点关键码；右子树上所有关键码大于结点关键码；注意：若从根结点到某个叶结点有一条路径，路径左边的结点的关键码不一定小于路径上的结点的关键码。78如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树。二叉搜索树的类定义#include<iostream.h>#include<stdlib.h>template<classE,classK>structBSTNode{ //二叉树结点类

Edata; //数据域

BSTNode<E,K>*left,*right;//左子女和右子女79BSTNode(){left=NULL;right=NULL;

}

//构造函数

BSTNode(constEd,BSTNode<E,K>*L=NULL,

BSTNode<E,K>*R=NULL){data=d;left=L;right=R;}

//构造函数～BSTNode(){} //析构函数

voidsetData(Ed){data=d;} //修改

EGetData(){returndata;} //提取

booloperator<(constE&x)

//重载：判小于

{returndata.key<x.key;}80booloperator>(constE&x)

//重载：判大于

{returndata.key>x.key;}booloperator==(constE&x)

//重载：判等于

{returndata.key==x.key;}};template<classE,classK>classBST{ //二叉搜索树类定义public:BST(){root=NULL;

} //构造函数

BST(Kvalue); //构造函数

～BST(){}; //析构函数

81boolSearch(constKx)const //搜索

{returnSearch(x,root)!=NULL;}

BST<E,K>&operator=(constBST<E,K>&R); //重载：赋值

voidMakeEmpty()

//置空

{MakeEmpty(root);root=NULL;}voidPrintTree()const{PrintTree(root);}//输出

EMin(){returnMin(root)->data;} //求最小

EMax(){returnMax(root)->data;} //求最大

boolInsert(constE&e1)

//插入新元素

{returnInsert(e1,root);}82boolRemove(constKx){returnRemove(x,root);} //删除含x的结点private:

BSTNode<E,K>*root; //根指针

KRefValue; //输入停止标志

BSTNode<E,K>* //递归：搜索

Search(constKx,BSTNode<E,K>*ptr);voidmakeEmpty(BSTNode<E,K>*&ptr); //递归：置空

voidPrintTree(BSTNode<E,K>*ptr)const; //递归：打印

BSTNode<E,K>* //递归：复制

Copy(constBSTNode<E,K>*ptr); 83BSTNode<E,K>*Min(BSTNode<E,K>*ptr);

//递归：求最小

BSTNode<E,K>*Max(BSTNode<E,K>*ptr);

//递归：求最大

boolInsert(constE&e1,BSTNode<E,K>*&ptr);

//递归：插入

boolRemove(constKx,BSTNode<E,K>*&ptr);

//递归：删除};二叉搜索树的类定义用二叉链表作为它的存储表示，许多操作的实现与二叉树类似。84二叉搜索树的搜索算法在二叉搜索树上进行搜索，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设想要在二叉搜索树中搜索关键码为x

的元素，搜索过程从根结点开始。如果根指针为NULL，则搜索不成功；否则用给定值

x

与根结点的关键码进行比较：若给定值等于根结点关键码，则搜索成功，返回搜索成功信息并报告搜索到结点地址。85若给定值小于根结点的关键码，则继续递归搜索根结点的左子树；否则。递归搜索根结点的右子树。搜索45搜索成功搜索28搜索失败35154550402510203086搜索过程是从根结点开始，沿某条路径自上而下逐层比较判等的过程。搜索成功，搜索指针将停留在树上某个结点；搜索不成功，搜索指针将走到树上某个结点的空子树。设树的高度为h，最多比较次数不超过h。87二叉搜索树的插入算法为了向二叉搜索树中插入一个新元素，必须先检查这个元素是否在树中已经存在。在插入之前，先使用搜索算法在树中检查要插入元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。8835154550402510203028插入新结点28二叉搜索树的插入每次结点的插入，都要从根结点出发搜索插入位置，然后把新结点作为叶结点插入。89输入数据

{53,78,65,17,87,09,81,15}535378537865537865175378658717537865091