[理学]第6章 树_new.ppt

2、树的定义 树（Tree）是n（n≥0）个结点的有限集合T，当n=0时称为空树，否则，称为非空树。在任一棵非空树中： （1）有且仅有一个称为树根的结点。 （2）除根结点之外的其余结点可分为m（m≥0）个互不相交的集合T1，T2，…，Tm，其中每一个集合本身又都是一棵树，一般称为根的子树。 树的定义是一个递归的定义，它反映了树的固有特性，即一棵树由若干棵子树构成，且各子树间互不相交，而每棵子树又由若干棵更小的子树构成。例如，在图6.2中，（a）是只有一个根结点的树；（b）是有8个结点的一般树，其中A是根，其余结点分成三个互不相交的子集：T1={B、E、F}，T2 ={C}，T3={D、G、H}，而且它们都是A的子树，且其本身也是一棵树。 6.1.2 树的常用术语 树的结点：是指一个数据元素及若干指向其子树的分支，通常用一个结构体或记录来描述，在树形表示中用一个圆圈及短线表示。 结点的度：是指结点的子树数目。 叶子或终端结点：是指度为零的结点。 分支结点或非终端结点：是指度不为零的结点。 树的度：是指树中各结点度的最大值。 有时，在实际应用中也引用家族树中的一些习惯用语来描述树，如孩子、双亲、祖先、子孙和兄弟等。如将某结点的子树的根称为该结点的孩子，相应地，将该结点称为孩子的双亲；同一个双亲的孩子之间互称为兄弟等等。祖先则是从根结点到该结点所经过分支上的所有结点，而以某结点作为根的子树中任一个结点都称为该结点的子孙。 结点的层次：从根开始定义，根为第一层，根的孩子为第二层，以此类推，即设根结点的层数为1，其余结点的层数等于其双亲结点的层数加1。若某结点在第i层，则其孩子结点就在第i+1层。 树的深度或高度：是指树中结点的最大层次数。 路径：若树中存在一个结点序列k1，k2，…，kj，使得ki是k i＋1的双亲（1≤ij），则称该结点序列是从k1到kj的一条路径，且路径的长度为j-1，即等于路径上分支的数目。在树形表示中，路径表示从k1出发自上而下地通过k2，k3，…，kj各结点。 有序树和无序树：若将树中每个结点的各子树看成是从左至右有序且不能交换，则称该树为有序树，否则称为无序树。图6.4给出了两棵不同的有序树。 森林：是指m（m≥0）棵互不相交的树的集合。 显然，树形结构不同于线性结构。在树中，一个结点至多只有一个直接前趋（双亲），却可以有多个直接后继（孩子），即结点之间的关系不象线性结构中的结点关系是一一对应关系，而是呈现出一对多的层次关系。 6.2 二叉树 二叉树（Binary Tree）是另一种重要的树形结构，在实际应用中具有重要的意义。本节将详细地讨论二叉树的定义、重要性质、存储方式、运算及其应用。 2、二叉树基本形态 3、二叉树的基本运算 （1）setnull（bt）：置bt为空二叉树 （2）求根函数root（bt）或root（x） （3）求双亲函数parent（bt，x） （4）求孩子结点函数lchild（bt，x）和rchild（bt，x） （5）插入运算addlchild(b，x，y)和addrchild(bt，x，y) （6）二叉树建立运算create（x，lbt，rbt） （7）删除子树运算dellchild（bt， x）和delrchild（bt， x） （8）遍历运算traverse（bt） 6.2.2 二叉树的性质 性质1 在二叉树的第i层上至多有2i-1结点（i≥1）。 性质2 深度为h的二叉树至多有2h-1个结点（h≥l）。 性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0= n2＋1。 性质4 具有n个结点的完全二叉树的深度为?log2n?+1。 性质5 如果对一棵有n个结点的完全二叉树（其深度为?log2n?＋1），按照从根结点起，自上而下，从左到右的约定对所有结点从1到n进行编号，则对于任意的编号为i的结点（1≤i≤n）有以下性质： （1）如果i=1，则结点i是二叉树的根，无双亲；如果i＞1，则其双亲的编号是?i/2?。 （2）如果2in，则结点i无左孩子（结点i为叶子结点），否则其左孩