pascal树.docx

树及其应用

树的定义
树是由n(n>=0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则
（1）有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；
（2）除根以外的其它结点划分为m(m>=0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。

结点(node):各元素及其子树的分支结点的度(degree)：子树的数目
分支(branch)结点：度不为0的结点叶(leaf)结点：度为0的结点
子女(child)、双亲(parent)结点：如B、C、D为A的子女，A是B、C、D的双亲

兄弟(sibling)、祖先(ancestor)、子孙(descendant)结点：EF为兄弟，L的祖先是EBA，
结点所处层次(level)树的高度(depth)：树的最大层次数
树的度(degree)：各结点度的最大值
二叉树(BinaryTree)
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
二叉树的五种不同形态

二叉树的性质
性质1若二叉树的层次从0开始,则在二叉树的第i层最多有2i个结点。(i>=
0)
性质2高度为k的二叉树最多有2k+1-1个结点。(k＞＝1)
性质3对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1
两种特殊的二叉树：满二叉树(FullBinaryTree)完全二叉树(CompleteBinaryTree)

二叉树是一个有根树，并且每个结点最多有2个子结点。
满二叉树是每个结点都有0个或2个子结点的树。
一棵有n个结点的二叉树，按满二叉树的编号方式对它进行编号，若树中所有结点和满二叉树1～n编号完全一致，则称该树为完全二叉树。

二叉树的抽象数据表示
1．数组表示

问题：右图所示为一棵单支二叉树
请用数组表示其存储结构

链表表示

对上述的二叉链表，采用以下表示形式：
（1）静态链式表示（用数组模拟链表），如右图。
该二叉树的生成完成采用给数组赋值的方法

（2）动态链式结构的Pascal描述
type
tree=^struct
struct=record
procedureenter(varP:tree);{二叉树的生成编码}
varch:char;
begin
read(ch);
ifch<>’.’then
begin
new(p);p^.data:=ch;
enter(p^.ltree);enter(p^.rtree);
endelse
p:=nil;
end;
data:treetype;
ltree,rtree:tree;
end;
该二叉树的生成，可按照根、左子树、右子树的顺序进行，对应的输入顺序是ABC..DE..FG...,其中点号表示nil。将其定义成一个过程Enter(varP:tree),P为指向根结点的指针变量。具体编码如右：

二叉树遍历(BinaryTreeTraversal)
所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。其目标是通过完整而有规则的遍历方法，使得对非线性的二叉树结构能获得其中各结点信息的一个线性排列。现设访问根结点记作V
、访问根的左子树记作L
、访问根的右子树记作R

则可能的遍历次序有6种：
前序:VLR/VRL中序:LVR/RVL后序:LRV/RLV
中根遍历(InorderTraversal)

中根遍历二叉树的算法框架是：
若二叉树为空，则空操作；
否则中根遍历左子树(L)；
访问根结点(V)；
中根遍历右子树(R)。
右图所示树的中根
遍历结果：
procedureinOrder(p:tree);{中根遍历}
begin
ifp<>nilthen
begin
inOrder(p^.ltree);
write(p^.data);
inOrder(p^.rtree);
end;
end;
a+b*c-d-e/f

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

遍历结果：+a*b-cd/ef
{中根遍历非递归算法}
procedureinOrder(p:tree);
vars:stack;
begin
push(s,p){根结点进栈}
while(s<>nil)do
begin
whilep^.ltree<>nildo
begin{子树根结点进