TableOfContents

树

树形结构是一种非线性结构。

树形结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。

树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。

树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。

1. 树的实例

家族树：在现实生活中，有入如下血统关系的家族可用树形图表示：

• 张源有三个孩子张明、张丽和张亮；
• 张明有两个孩子张林和张维；
• 张亮有三个孩子张平、张华和张群；
• 张平有两个孩子张晶和张磊。

attachment:tree.jpg

树的定义

树是由n (n≥0)个结点构成的有限集合；n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：

• 有且仅有一个特定的结点称之为根，它没有前驱结点；

• 其余结点分成m(m≥0)个互不相交的有限集合latex($$T_1, T_2,\cdots,T_m$$)，其中每一个集合又都是一棵树，称latex($$T_1, T_2,\cdots,T_m$$)为根结点的子树。

树的图示

倒置的树形图表示

attachment:tree2.jpg

凹入表示

嵌套集合表示（文氏图表示）

嵌套括号表示（广义表表示）

(A(B(E,F),C,D(G,H(J,K),I)))

术语

• 子结点：树中某个结点的子树之根称为该结点的孩子(Child)或子结点
• 父结点：该结点称为孩子的双亲(Parents)或父亲或父结点。
• 兄弟结点：同一个双亲的孩子称为兄弟(Sibling)结点。
• 结点的度：树中的一个结点拥有的子树数称为该结点的度(Degree)。
• 树的度：一棵树的度是指该树中结点的最大度数。：
• 叶结点：度为零的结点称为叶子(Leaf)或终端结点。
• 分支节点：度不为零的结点称分支结点或非终端结点。

• 路径：若树中存在一个结点序列k1，k2，…，kj，使得ki是ki+1的双亲(1≤i<j)，则称该结点序列是从kl到kj的一条路径(Path)或道路。

• 路径的长度：路径的长度指路径所经过的边(即连接两个结点的线段)的数目，等于j-1。
• 祖先和子孙：若树中结点k到ks存在一条路径，则称k是ks的祖先(Ancestor)，ks是k的子孙(Descendant)。一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。（结点k的祖先和子孙不包含结点k本身。）
• 结点的层次：根结点的层次为1（也有将根的层次定义为0的），其余结点的层次为父结点的层次加1。即从根结点到该结点的路径长度加1。
• 树的高度：树中结点的最大层数称为树的高度(Height)或深度(Depth)。
• 堂兄弟：双亲在同一层的结点互为堂兄弟。

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

• 森林：森林(Forest)是m(m≥0)棵互不相交的树的集合。
• 同构：

树形结构的特点：

• 树中任一结点都可以有零个或多个直接后继(即孩子)结点，但至多只能有一个直接前趋(即双亲)结点。
• 树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。
• 祖先与子孙的关系是对父子关系的延拓，它定义了树中结点之间的纵向次序。
• 有序树中，同一组兄弟结点从左到右有长幼之分。对这一关系加以延拓，规定若k1和k2是兄弟，且k1在k2的左边，则k1的任一子孙都在k2的任一子孙的左边，那么就定义了树中结点之间的横向次序。
• 将一棵树的根结点去掉，它的子树的集合即为一个森林。而在森林中的每棵树之上加一个共同的根，森林就成为了一棵树。
• 从树的根结点到树中其余结点均存在一条惟一的路径。

树的基本操作：

• init_tree(t)初始化
• destroy_tree(t)销毁树
• create_tree(t)创建树
• tree_empty(t)判断空树
• root(t)返回树根
• parent(t, node)返回树t中node结点的父结点
• first_child(t, node)返回树t中node结点的第一个子结点
• next_sibling(t, node)返回树t中node结点的下一个兄弟结点
• insert_child(t, parent, child)在树t中插入子child结点作为parent结点的子结点
• delete_child(t, parent, child)删除树t中parent结点的子结点child
• tranverse_tree(t, visit)遍历树t，对t的每个结点做一次visit操作且仅作一次。

二叉树的定义：

二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

二叉树与度为2的有序树不同：在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。

术语：

• 左孩子
• 右孩子

二叉树五种基本形态：

attachment:binarytree.jpg

二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

二叉树的特殊形态：

1、满二叉树(FullBinaryTree)

一棵深度为k且有2k-1个结点的二又树称为满二叉树。

满二叉树的特点：

• 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
• 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。

2、完全二叉树(Complete BinaryTree)

若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

attachment:completetree.jpg

完全二叉树的特点：

• 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
• 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
• 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
• 完全二叉树中除最下面一层外，各层都充满了结点，每一层的结点个数恰好是上一层结点个数的2倍。

编号：在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列。

从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。假设编号为i的结点是ki(1≤i≤n)，则有：

• 若i>1，则ki的双亲编号为[i/2]；若i=1，则Ki是根结点，无双亲。

• 若2i≤n，则Ki的左孩子的编号是2i；否则，Ki无左孩子，即Ki必定是叶子。因此完全二叉树中编号 的结点必定是叶结点。
• 若2i+1≤n，则Ki的右孩子的编号是2i+1；否则，Ki无右孩子。
• 若i为奇数且不为1，则Ki的左兄弟的编号是i-1；否则，Ki无左兄弟。
• 若i为偶数且小于n，则Ki的右兄弟的编号是i+1；否则，Ki无右兄弟。

二叉树具有以下重要性质：

性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。

性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。

性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。

性质4 具有n个结点的完全二叉树的深度为