数据结构与算法b-2014年5月07日课堂treemay

数据结构与算法

—树主讲教员:段凌宇2014年5月07日

北京大学信息科学与技术学院，转载或翻印必究大纲5.1树的概念5.2树的链式存储5.3树的顺序存储5.4K叉树北京大学信息学院，转载或翻印必究Page2北京大学信息学院，转载或翻印必究Page35.1树的概念5.1.1树和森林5.1.2 森林与二叉树的等价转换5.1.3树的抽象数据类型5.1.4树的周游北京大学信息学院，转载或翻印必究Page4树的逻辑结构包含n个结点的有穷集合K(n>0)，且在K上定义了一个关系N，关系N满足以下条件：

有且仅有一个结点k0∈K，它对于关系N来说没有前驱，

结点k0称作树的根；除结点k0外，K中每个结点对于关系N都有且仅有一个前驱；除结点k0外的任何结点k∈K，都存在一个结点序列k0，k1，…，ks，使得k0就是树根，且ks=k，

其中有序对<ki-1，ki>∈N(1≤i≤s)。

这样的结点序列称为从根到结点k的一条路径。北京大学信息学院，转载或翻印必究Page5树的递归定义树是包括n个结点的有限集合T（n≥1），使得：有一个特别标出的称作根的结点除根以外的其它结点被分成m个(m≥0)不相交的集合T1，T2，…，Tm，而且这些集合的每一个又都是树；

树T1，T2，…，Tm称作这个根的子树。只包含一个结点的树必然仅由根组成，包含n>1个结点的树借助于少于n个结点的树来定义。北京大学信息学院，转载或翻印必究Page6树结构中的概念若有序对<

k，k′>

∈N，则称k是k′的父结点（或“父母”），而k′则是k的子结点(或“儿子”、“子女”)若有序对<k，k′>及<k，k″>

∈N，则称k′和k″互为兄弟若有一条由k到达ks的路径，则称k是ks的祖先，ks

是k的子孙树形结构中，两个结点的有序对，称作连接这两结点的一条边北京大学信息学院，转载或翻印必究Page7没有子树的结点称作树叶或终端结点非终端结点称为分支结点一个结点的子树的个数称为度数根结点的层数为0，其它任何结点的层数等于它的父结点结点的层数加1树T中如果子树T1，T2，…，Tm的相对次序是重要的，则称树T为有向有序树，简称有序树。可以称T1是根的第一棵子树，T2是根的第二棵子树，等等。北京大学信息学院，转载或翻印必究Page8森林与树森林(forest):零棵或多棵不相交的树的集合。(通常是有序集合)自然界的树和森林是不同的概念，而数据结构的树和森林只有微小的差别。删去树根，树就变成森林；加上一个结点作树根，森林就变成树。北京大学信息学院，转载或翻印必究Page95.1树的概念5.1.1树和森林5.1.2 森林与二叉树的等价转换5.1.3树的抽象数据类型5.1.4树的周游北京大学信息学院，转载或翻印必究Page10森林与二叉树的等价转换×××北京大学信息学院，转载或翻印必究Page11森林与二叉树的等价转换树或森林与二叉树之间存在一个自然的一一对应的关系任何森林都唯一地对应到一棵二叉树；反过来，任何二叉树也都唯一地对应到一个森林。树所对应的二叉树里结点n的左子结点是结点n在原来树里的第一个子结点结点n的右子结点是结点n在原来树里的下一个兄弟北京大学信息学院，转载或翻印必究Page12森林到二叉树等价转换

的精确定义森林F看作树的有序集合，F=(T1，T2，…，Tn)，对应于F的二叉树B(F)的定义是：若n=0，则B(F)为空若n>0，则B(F)的根是T1的根W1，B(F)的左子树是B(T11，T12，…，T1m)，其中T11，T12，…，T1m是W1的子树；B(F)的右子树是B(T2，…，Tn)。北京大学信息学院，转载或翻印必究Page13二叉树到森林的等价转换设B是一棵二叉树，r是B的根，L是r的左子树，

R是r的右子树，则对应于B的森林F(B)的定义：若B为空，则F(B)是空的森林；若B不为空，则F(B)是一棵树T1

+森林F(R)，其中树T1的根为r，r的子树为F(L)。北京大学信息学院，转载或翻印必究Page145.1树的概念5.1.1树和森林5.1.2 森林与二叉树的等价转换5.1.3树的抽象数据类型5.1.4树的周游北京大学信息学院，转载或翻印必究Page15树/森林的

结点抽象数据类型 template<classT> classTreeNode {

public: TreeNode(constT&);//拷贝构造函数

virtual~TreeNode(){};//析构函数

boolisLeaf(); //如果结点是叶，返回true TValue(); //返回结点的值

TreeNode<T>*LeftMostChild();//返回第一个左孩子

TreeNode<T>*RightSibling();//返回右兄弟北京大学信息学院，转载或翻印必究Page16

//设置结点的值

voidsetValue(T&);

//设置左子结点

voidsetChild(TreeNode<T>*pointer);

//设置右兄弟

voidsetSibling(TreeNode<T>*pointer);

//以第一个左子结点身份插入结点

voidInsertFirst(TreeNode<T>*node);

//以右兄弟的身份插入结点

voidInsertNext(TreeNode<T>*node);};北京大学信息学院，转载或翻印必究Page17树/森林的抽象数据类型 template<classT> classTree {

public: Tree(); //构造函数

virtual~Tree(); //析构函数

TreeNode<T>*getRoot();

//返回树中的根结点

//创建树中的根结点，使根结点元素的值为rootValue voidCreateRoot(constT&rootValue);

//判断是否为空树，如果是则返回true boolisEmpty();

北京大学信息学院，转载或翻印必究Page18//返回current结点的父结点 TreeNode<T>*Parent(TreeNode<T>*current);

//返回current结点的前一个邻居结点

TreeNode<T>*PrevSibling(TreeNode<T>*current);

//删除以subroot为根的子树的所有结点 voidDeleteSubTree(TreeNode<T>*subroot);

//先根深度优先周游树 voidRootFirstTraverse(TreeNode<T>*root);

//后根深度优先周游树 voidRootLastTraverse(TreeNode<T>*root); //宽度优先周游树

voidWidthTraverse(TreeNode<T>*root);};北京大学信息学院，转载或翻印必究Page195.1树的概念5.1.1树和森林5.1.2 森林与二叉树的等价转换5.1.3树的抽象数据类型5.1.4树的周游北京大学信息学院，转载或翻印必究Page20森林的深度优先周游

先根次序

a)访问头一棵树的根

b)在先根次序下周游头一棵树树根的所有子树

c)在先根次序下依次周游其他的树

后根次序

a)在后根次序下周游头一棵树树根的所有子树

b)访问头一棵树的根

c)在后根次序下依次周游其他的树北京大学信息学院，转载或翻印必究Page21森林的周游

示例ABCKDEFGHJ先根次序周游：A

B

C

K

D

E

H

F

J

G后根次序周游：BKCAHEJFGD广度优先周游：ADBCEFGKHJ北京大学信息学院，转载或翻印必究Page22先根深度优先

周游树程序实现template<classT>voidTree<T>::RootFirstTraverse(TreeNode<T>*root){if(root!=NULL){Visit(root->Value());//访问当前结点root=root->LeftMostChild(); while(root!=NULL){

RootFirstTraverse(root); root=root->RightSibling();//周游其他的子树

}}}北京大学信息学院，转载或翻印必究Page23后根深度优先

周游树程序实现template<classT>voidTree<T>::RootLastTraverse(TreeNode<T>*root){TreeNode<T>*pointer=root;if(root!=NULL){pointer=root->LeftMostChild(); while(pointer!=NULL){

RootLastTraverse(pointer); pointer=pointer->RightSibling();//周游其他的子树

}Visit(root->Value());//访问当前结点}}北京大学信息学院，转载或翻印必究Page24宽度优先

周游树的程序实现template<classT>voidTree<T>::WidthTraverse(TreeNode<T>*root){ usingstd::queue; //使用STL队列

queue<TreeNode<T>*>aQueue; TreeNode<T>*pointer=root; if(pointer)

aQueue.push(pointer); while(!aQueue.empty()){pointer=aQueue.front();//取队列首结点指针Visit(pointer->Value());//访问当前结点北京大学信息学院，转载或翻印必究Page25

pointer=pointer->LeftMostChild();

while(pointer){aQueue.push(pointer);pointer=pointer->RightSibling();};aQueue.pop(); //出队列}}北京大学信息学院，转载或翻印必究Page26深度优先周游森林

versus

深度优先周游等价的二叉树按先根次序周游森林等同按前序法周游对应的二叉树按后根次序周游森林等同按中序法周游对应的二叉树北京大学信息学院，转载或翻印必究Page27先根深度优先

周游森林程序实现template<classT>voidTree<T>::RootFirstTraverse(TreeNode<T>*root){while(root!=NULL){Visit(root->Value());//访问当前结点

RootFirstTraverse(root->LeftMostChild()root=root->RightSibling();//周游其他的树}}template<classT>voidTree<T>::RootLastTraverse(TreeNode<T>*root){ while(root!=NULL){

RootLastTraverse(root->LeftMostChild()); Visit(root->Value());//访问当前结点

root=root->RightSibling();//周游其他的树

}}北京大学信息学院，转载或翻印必究Page28后根深度优先

周游森林程序实现大纲5.1树的概念5.2树的链式存储5.3树的顺序存储5.4K叉树北京大学信息学院，转载或翻印必究Page29北京大学信息学院，转载或翻印必究Page305.2树的链式存储5.2.1子结点表表示法5.2.2左子结点/右兄弟结点表示法5.2.3动态结点表示法5.2.4动态“左子结点/右兄弟结点”二叉链表表示法5.2.5父指针表示法北京大学信息学院，转载或翻印必究Page315.2.1子结点表表示法“子结点表”表示法在数组中存储树的结点。每个结点包括结点值、一个父指针以及一个指向子结点链表的指针。每个分支结点均存储其子结点信息，子结点按照从左至右的顺序形成一个链表(叶子结点的子结点链表指针为空)。结点的最左子结点可由链表的第一个表项直接找到。找到结点的右侧兄弟结点要困难一些。北京大学信息学院，转载或翻印必究Page325.2.2左子结点/右兄弟结点

表示法每个结点存储结点值，指向父结点、最左子结点、右侧兄弟结点的指针。ADT的基本操作可通过读取结点中的一个值来实现。如果两棵树存储在同一个数组中，那么把其中一个添加为另一棵树的子树只需简单设置三个指针值即可。这种表示法比子结点表表示法空间效率更高，而且结点数组中的每个结点仅需要固定大小的存储空间。北京大学信息学院，转载或翻印必究Page335.2.3动态结点表示法为每个结点分配可变的存储空间。每个结点存储一个基于数组的子结点指针表。子结点的数目不变时，这种方法效果最佳；如果子结点的数目发生变动（特别是增加），就必须提供一种专门的校正机制来改变子结点指针数组的大小每个结点存储一条子结点指针链表，动态地分配指针空间。本质上与“子结点表”表示法相同(少了指向父结点的指针，且链表中指针不是数组中的整数下标索引)北京大学信息学院，转载或翻印必究Page345.2.4动态“左子结点/右兄弟结点”

二叉链表表示法本质上，我们使用二叉树来替换树。左子结点在树中是结点的最左子结点，右子结点是结点原来的右侧兄弟结点。由于树的每个结点均包含固定数目的指针，而且树的ADT的每个函数均能有效实现，因此动态“左子结点/右兄弟结点”表示法比以上介绍的其他方法更为常用。可以很容易地把这种转化推广到森林，因为森林中每棵树的根结点可以看成互为兄弟结点。北京大学信息学院，转载或翻印必究Page355.2.4动态“左子结点/右兄弟结点”

二叉链表表示法本质上，我们使用二叉树来替换树。左子结点在树中是结点的最左子结点，右子结点是结点原来的右侧兄弟结点。由于树的每个结点均包含固定数目的指针，而且树的ADT的每个函数均能有效实现，因此动态“左子结点/右兄弟结点”表示法比以上介绍的其他方法更为常用。可以很容易地把这种转化推广到森林，因为森林中每棵树的根结点可以看成互为兄弟结点。北京大学信息学院，转载或翻印必究Page36树结点抽象数据类型

的程序实现//补充与具体实现相关的私有成员变量申明…private: Tm_Value; //树结点的值

TreeNode<T>* pChild; //第一个左子结点

TreeNode<T>* pSibling; //右兄弟结点北京大学信息学院，转载或翻印必究Page37树结点抽象数据类型

的程序实现

//公有成员函数的具体实现

template<classT>

TreeNode<T>::TreeNode(constT&value)

{

m_Value=value; pChild=NULL; pSibling=NULL; }

template<classT>

TTreeNode<T>::Value()

{

returnm_Value;

}

template<classT>

boolTreeNode<T>::isLeaf()

{

if(pChild==NULL)

returntrue;

returnfalse;

}北京大学信息学院，转载或翻印必究Page38template<classT>void

TreeNode<T>::setValue(T&value) {

m_Value=value;

//设置结点的值}template<classT>TreeNode<T>*

TreeNode<T>::LeftMostChild(){

returnpChild;

//返回第一个左子结点}template<classT>TreeNode<T>*

TreeNode<T>::RightSibling(){

returnpSibling;

//返回右兄弟}北京大学信息学院，转载或翻印必究Page39template<classT>voidTreeNode<T>::setChild(TreeNode<T>*pointer){

pChild=pointer;

//设置左子结点}template<classT>voidTreeNode<T>::setSibling(TreeNode<T>*pointer){

pSibling=pointer;

//设置右兄弟}北京大学信息学院，转载或翻印必究Page40template<classT>voidTreeNode<T>::InsertFirst(TreeNode<T>*node){

if

(!pChild)

pChild=node;

//若当前结点原先无子女 else

{

//若当前结点原先已有子女

node->pSibling=pChild;

pChild=node; }}以当前结点TreeNode第一个子结点的身份插入结点北京大学信息学院，转载或翻印必究Page41以当前结点TreeNode右兄弟的身份插入结点template<classT>voidTreeNode<T>::InsertNext(TreeNode<T>*node){

if(!pSibling) pSibling=node;//若当前结点原先无右兄弟 else{

//若当前结点原先已有右兄弟

node->pSibling=pSibling; pSibling=node; }}北京大学信息学院，转载或翻印必究Page42树抽象数据类型的

程序实现private: TreeNode<T>*root;

//树根结点

//返回current的父结点，由函数Parent调用

TreeNode<T>*getParent(TreeNode<T>*root,

TreeNode<T>*current);

//删除以root为根的子树的所有结点

voidDeleteNodes(TreeNode<T>*root); 北京大学信息学院，转载或翻印必究Page43template<classT>Tree<T>::Tree() {

root=NULL;}template<classT>Tree<T>::~Tree()

{

while(root)

DeleteSubTree(root);}template<classT>TreeNode<T>*Tree<T>::getRoot()

{

returnroot;}北京大学信息学院，转载或翻印必究Page44template<classT>voidTree<T>::CreateRoot(constT&rootValue){//创建树中的根结点，使根结点元素的值为rootValue

if(!root)

root=newTreeNode<T>(rootValue);}template<classT>boolTree<T>::isEmpty(){//判断是否为空树，如果是则返回true if(root)

returnfalse; returntrue;}北京大学信息学院，转载或翻印必究Page45返回current结点的

前一个邻居结点的程序实现template<classT>TreeNode<T>*

Tree<T>::PrevSibling

(TreeNode<T>*current){

usingstd::queue;

//使用STL队列

queue<

TreeNode<T>*

>aQueue;

//标识当前结点 TreeNode<T>*pointer=root;

//标识当前结点的前一个兄弟结点

TreeNode<T>*prev=NULL;

北京大学信息学院，转载或翻印必究Page46if

((current==NULL)||(pointer==NULL)

||(current==pointer))

//当前结点为空、树为空、当前结点为根结点 returnNULL; while(pointer){//找到当前结点 if(pointer==current) returnprev;

aQueue.push(pointer); prev=pointer;//沿当前结点右兄弟结点链寻找 pointer=pointer->pSibling;}//以广度优先周游方式寻找前一邻结点

while(!aQueue.empty()){ prev=NULL; pointer=aQueue.front(); //出队列 aQueue.pop();

//下降到左子结点

pointer=pointer->LeftMostChild();

北京大学信息学院，转载或翻印必究Page47北京大学信息学院，转载或翻印必究Page48while(pointer){ if(pointer==current)returnprev; aQueue.push(pointer); prev=pointer; pointer=pointer->pSibling;

} } returnNULL;}北京大学信息学院，转载或翻印必究Page49

template<classT> voidTree<T>::DeleteNodes(TreeNode<T>*root) {

if(root){

//递归删除第一子树

DeleteNodes(root->LeftMostChild());

//递归删除其他子树

DeleteNodes(root->RightSibling()); //删除根结点

deleteroot;

} }删除以root为根的子树的所有结点

template<classT> voidTree<T>::

DeleteSubTree(TreeNode<T>*subroot) {

TreeNode<T>*pointer=PrevSibling(subroot); if(pointer==NULL) {//subroot为最左子结点的情况

pointer=Parent(subroot); if(pointer){ pointer->pChild=subroo