第6章树和二叉树（1）

树型结构——非线性数据结构

6.1 树的定义和基本术语

树 Tree：是n（n>=0）个结点的有限集

根节点 Root：在任意一棵非空树中，有且仅有一个

子树 SubTree：n>1时，除根节点外的m（m>0）个互不相交的有限集T1，T2 … Tm

（a）是只有根结点的树

（b）一般的树，有13个结点，A是根，其余结点分为3个互不相交的子集：T1={B,E,F,K,L}，T2={C,G}，T3={D,H,I,J,M}；T1，T2，T3都是根A的子树，且本身也是一棵树

上述树的结构定义加上树的一组基本操作就构成了抽象数据类型树的定义。

树的结构定义是一个递归的定义，即树中又有树。

（a）以嵌套集合的形式表示

（b）以广义表的形式表示，根作为由子树森林组成的名字的名字写在表的左边

（c）用凹入表示法

基本术语：

树的结点包含一个数据元素及若干指向其子树的分支。

（1）结点的度（Degree）

树中的一个结点拥有的子树数称为该结点的度。图6.1（b）中，A的度为3，C的度为1，F的度为0。

度为0的结点，称为叶子（Leaf）或终端结点。图6.1（b）中的结点K、L、F、G、M、I、J都是树的叶子。

度不为0的结点，称为非终端结点或分支结点。

树的度是树内各结点的度的最大值。

除根结点之外，分支结点也称为内部结点。

根结点又称为开始结点。

（2）孩子（Child）和双亲（Parent）

结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent）。

同一个双亲的孩子之间互称兄弟（Silbling）。

（3）祖先(Ancestor)和子孙(Descendant)

结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

①路径（path）
若树中存在一个结点序列k1，k2，…，ki，使得ki是ki+1的双亲(1≤i<j)，则称该结点序列是从kl到kj的一条路径(Path)或道路。
路径的长度指路径所经过的边(即连接两个结点的线段)的数目，等于j-1。
注意：
若一个结点序列是路径，则在树的树形图表示中，该结点序列"自上而下"地通过路径上的每条边。
从树的根结点到树中其余结点均存在一条惟一的路径。

②祖先(Ancestor)和子孙(Descendant)
若树中结点k到ks存在一条路径，则称k是ks的祖先(Ancestor)，ks是k的子孙(Descendant)。
一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。
约定：结点k的祖先和子孙不包含结点k本身。

（3）结点的层数（Level）和树的深度（Depth）

结点的层数(Level)从根起算：
根的层数为1
其余结点的层数等于其双亲结点的层数加1。
双亲在同一层的结点互为堂兄弟。
树中结点的最大层数称为树的深度(Depth)或高度。

（4）有序树（OrderedTree）和无序树（UnoderedTree）
若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树，否则称为无序树。
注意：若不特别指明，一般讨论的树都是有序树。

（5）森林(Forest)
森林(Forest)是m(m≥0)棵互不相交的树的集合。
树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。

ADT Tree{
    //数据对象 D（data）：D 是具有相同特性的数据元素的集合
    //数据关系 R（Relation）：若D为空集，则称为空树

    //若D仅含有一个数据元素，则R为空集，否则 R={H}，H是如下二元关系：
    //（1）在 D 中仅存在惟一的称为根的元素 root，在关系 H 下无前驱
    //（2）

    //基本操作 P（）：
    InitTree(&T);
     //操作结果：构造空树T
    DestroyTree(&T);
    //初始条件：树T存在
    //操作结果：销毁树T
    CreateTree(&T,definition);
    //初始条件：definition 给出树T的定义
    //操作结果：按definition构造树
    ClearTree(&T);
    //初始条件：树T存在
    //操作结果：将树T清为空树
    TreeEmpty(&T);
    //初始条件：树T存在
    //操作结果：若T为空树，则返回TRUE，否则FALSE
    TreeDepth(T);
    //初始条件：树T存在
    //操作结果：返回T的深度
    Root(T);
    //初始条件：树T存在
    //操作结果：返回T的根
    Value(T,cur_e);
    //初始条件：树T存在，cur_e是T中某个结点
    //操作结果：返回cur_e的值
    Parent(T,cur_e);
    //初始条件：树T存在，cur_e是T中某个结点
    //操作结果：若cur_e是T的非根结点，则返回它的双亲，构造函数值为“空”
    LeftChild(T,cur_e);
    //初始条件：树T存在，cur_e是T中某个结点
    //操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”
    RightSilbling(T,cur_e);
    //初始条件：树T存在，cur_e是T中某个结点
    //操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”
    InsertChild(&T,&p,i,c);
    //初始条件：树T存在。p指向T中某个结点，1<=i<=p所指结点的度+1，非空树c与T不相交
    //操作结果：插入c为T中p指结点的第i棵子树
    DeleteChild(&T,&p.i);
    //初始条件：树T存在。p指向T中某个结点，1<=i<=p指结点的度。
    //操作结果：删除T中p所指结点的第i棵子树
    TraverseTree(T.Visit());
    //初始条件：树T存在，Visit是对结点操作的应用函数
    //操作结果：按某种次序对T的每个结点调用函数visit() 一次且至多一次。一旦visit()失败，则操作失败。
}ADT Tree

第6章 树和二叉树（1）

第6章树和二叉树（1）