数据结构第五章 数和二叉树

树的定义和基础术语

1.树的定义 树（Tree）是n（n>=0）个节点的有限集，它或为空树（n=0）；或为非空树，对于非空树T： a.有且仅有一个称之为根的节点； b.除根节点以外的其余节点可分为m个互不相干的有限集T₁,T₂,…..T_i,T_m,其中每一个集合本身又是一颗树，并称之为根的子树（SubTree）。 树的结构是递归的定义，树的定义中又有树的定义，这是树的固有特性；

树的基本术语

结点：树中的一个独立单元。结点的度：结点拥有的子树数称为结点的度。树的度：树内各结点度的最大值。叶子：度为0的结点称为叶子或终端结点。非终端结点：度不为0的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。兄弟：同一个双亲的孩子之间互称兄弟。祖先：从根结点到该结点所经分支上的所有结点。子孙：以某结点为根的子树种的任一结点都称为该结点的子孙。层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任意结点的层次等于其双亲结点层次加1。堂兄弟：其双亲在同一层的结点互为堂兄弟。树的深度：树中结点的最大层次称为树的深度或高度.有序树和无序树：如果将树中结点的各个子树看成从左至右是有次序的（即不能护换），则称该树为有序树，否则为无序树，在有序树中最左边的子树的根称为第一个孩子，右边的称为最后一个孩子.森林：是m颗互不相干的树的集合。对树中的每个结点而言，其子树的集合为森林。 就逻辑结构而言：任何一颗树都是一个二元组（Tree=（root,F））,其中root为根几点，F为m颗树的森林。 RF = {<root,r_i>|i=1,2,3,4,.....m,m>0} 该定义有助于得到深林和树与二叉树之间转换的递归定义。

二叉树

二叉树是一种特殊的树结构，其存储和处理比一般的树要简单，且一般的树可以通过转换得到与之对应的二叉树，这样就可以采用二叉树的存储结构和相关算法来解决树的相关问题。

二叉树的定义（Binary tree） 二叉树是n个结点所构成的集合，它或为空树，或为非空树，对于非空树T： 1.有且仅有一个称之为根的结点： 2.除根结点以外的其余结点分为两个互不相交的子集T₁和T₂，分别称为T的左子树和右子树，且都是二叉树。

二叉树与树的区别 1.二叉树每个结点至多有两颗子树（即二叉树中不存在度大于2的结点）； 2.二叉树的子树有左右之分，切次序不能任意颠倒。

二叉树的性质 1.在二叉树的第i层上最多有2^i-1个结点。 2.深度为k的二叉树至多有2^k-1个结点。 3.对任何一颗二叉树T，如果其终端结点数为n₀,度为2的结点数为n₂则n₀=n₂+1；

特殊二叉树

满二叉树：深度为k且含有2^k-1个结点的二叉树； 完全二叉树：深度为k且有n个结点的二叉树，当且仅当i每一个结点都与深度为k的满二叉树中编号从1-n的结点一一对应时，称为完全二叉树。

完全二叉树 特点： 1.叶子结点只可能在层次最大的两层上出现； 2.对任一结点，若其右分支下的子孙的最大层次为l，其左分支下的子孙的最大层次必为l或l+1。

性质： 1.具有n个结点的完全二叉树的深度为[log₂n]+1。 2.如果对一颗有n个结点的完全二叉树的结点按层序编号，则对任一结点i有： a.如果i=1，则结点i是二叉树的根，无双亲； b.如果i>1,则其双亲PARENT（i）是结点i/2； c.如果2i>n,则结点i无左孩子，否则其左孩子LCHILD(i)是结点2i； d.如果2i+1>n,则结点i无右孩子，否则其右孩子RCHILD(i)是结点2i+1；

二叉树的存储结构

可采用：顺序结构和链式结构两种； 顺序存储结构一般适用于完全二叉树（因为使用顺序存储会浪费空间），所以二叉树通常还是采用链式存储结构。 引出另一种链式存储:线索链表。

遍历二叉树和线索二叉树

1.遍历二叉树（traversing binary tree）：指按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 先序遍历： 1.访问根结点； 2.先序遍历左子树； 3.先序遍历右子树。

中序遍历： 1.中序遍历左子树； 2.访问根结点； 3.中序遍历右子树。

后序遍历： 1.后序遍历左子树； 2.后序遍历右子树； 3.访问根结点。