清华大学计算机程序设计基础-14.ppt
第14章二叉树及其应用;本章主要内容;树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。;结点的度：一个结点的子结点的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。;路径：如果存在树中的一个结点序列K1,K2,..,Kj，使得结点Ki是结点Ki+1的父结点(1≤i≤j)，那么称该结点序列是树中从结点K1到结点Kj的一条路径或道路。;层：从树根到任一结点n有惟一的一条路径，这条路径的长度称为结点n的深度或层数。;14.3二叉树的特点与数学性质;14.3.1二叉树的特点;(a)只有左子树;14.3.2两种特殊形态的二叉树;近似满二叉树;非近似满二叉树;14.3.3二叉树的数学性质;14.4二叉树的根本操作及其实现;二叉树的常用操作如下：
InitTree(T)：构造一棵空二叉树；
DestroyTree(T)：销毁一棵二叉树；
Parent(T,e)：返回二叉树T中e结点的父结点，假设不存在那么返回“空”；
LeftChild(T,e)：返回二叉树T中e结点的左儿子结点，假设不存在那么返回“空”；
RightChild(T,e)：返回二叉树T中e结点的右儿子结点，假设不存在那么返回“空”；
Value(T,e)：返回二叉树T中e结点的值；
Root(T)：返回二叉树T的根结点。;1二叉树的顺序存储结构;顺序存储结构实现ADT二叉树的操作:
voidInitTree(Tree*T)//构造空树
{ inti;
T-nTreeSize=0;
for(i=0;iMAXLENGTH;i++)
T-node[i]=0;
}
?voidDestroyTree(Tree*T)//销毁树
{ inti;
T-nTreeSize=0;
for(i=0;iMAXLENGTH;i++)
T-node[i]=0;
};TYPEParent(TreeT,inte) //返回父结点
{if(e0)returnT.node[(e-1)/2];
else return0;
}
?
TYPELeftChild(TreeT,inte)
//返回二叉树T中e结点的左儿子结点
{ if(e*2+1MAXLENGTH)
returnT.node[e*2+1];
else
return0;
};TYPERightChild(TreeT,inte)
//返回二叉树T中e结点的右儿子结点
{ if(e*2+2MAXLENGTH)
returnT.node[e*2+2];
elsereturn0;
}
?TYPEValue(TreeT,inte)//返回结点值
{ if(e=0eMAXLENGTH)
returnT.node[e];
else return0;
}
?TYPERoot(TreeT) //返回根结点
{ returnT.node[0];};2二叉树的链式存储结构;带有指向其父结点指针的二叉树的结构定义如下：
#defineTYPEint
structTNode
{ TYPEelement;
structTNode*parent;
structTNode*left;
structTNode*right;
};
typedefstructTNodeNode;
typedefstructTNode*Tree;;二叉树的存储表示方法：;A;由于二叉树结构本身的定义是递归的，因此对于二叉树的访问也必然是递归的。
先序遍历，先访问结点，然后遍历左结点、遍历右结点。
中序遍历，先遍历左结点，然后访问该结点，最后遍历右结点。
后序遍历，先遍历左结点，然后遍历右结点，最后访问该结点。;10.7二叉树的应用举例;当二叉树生成后，用中序遍历对二叉树进行遍历，就得到一个由小到大的顺序序列，那么什么是中序遍历呢？
实际上，遍历有三类，它都是对树中全部节点逐一进行某种处理的方法，只是顺序不同
先序(根)遍历树
中序(根)遍历树
后序(根)遍历树
用LDR〔L：Left,D：Data,R：Right)分别表示左子树，根节点，右子树那么有六种排列方案，假设限定先左后右，那么只有三种。;生成二叉排序树的方法;遍历二叉树的算法
——中序遍历二叉树;二叉树的遍历算法