数据结构 树 二叉树

1. 树

1. 树的定义

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

2. 基础术语

• 结点：树中的一个独立单元。
• 结点的度：结点拥有的子树数称为结点的度。
• 树的度：树内各结点度的最大值。
• 叶子：度为0的结点称为叶子或终端结点。
• 非终端结点：度不为0的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。
• 双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
• 兄弟：同一个双亲的孩子之间互称兄弟。
• 祖先：从根结点到该结点所经分支上的所有结点。
• 子孙：以某结点为根的子树种的任一结点都称为该结点的子孙。
• 层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任意结点的层次等于其双亲结点层次加1。
• 堂兄弟：其双亲在同一层的结点互为堂兄弟。
• 树的深度：树中结点的最大层次称为树的深度或高度.
• 有序树和无序树：如果将树中结点的各个子树看成从左至右是有次序的（即不能护换），则称该树为有序树，否则为无序树，在有序树中最左边的子树的根称为第一个孩子，右边的称为最后一个孩子.
• 森林：是m颗互不相干的树的集合。对树中的每个结点而言，其子树的集合为森林。

就逻辑结构而言：任何一颗树都是一个二元组（Tree=（root,F））,其中root为根几点，F为m颗树的森林。

RF = {<root,r_i>|i=1,2,3,4,.....m,m>0}
该定义有助于得到深林和树与二叉树之间转换的递归定义。

2. 二叉树

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

1. 二叉树的定义（Binary tree）:

二叉树是n个结点所构成的集合，它或为空树，或为非空树，对于非空树T：

1.有且仅有一个称之为根的结点：
2.除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且都是二叉树。

2. 二叉树与树的区别:

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

3. 二叉树的性质**

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

4. 特殊二叉树

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

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

性质：
1.具有n个结点的完全二叉树的深度为[log2n]+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；

5. 二叉树的存储结构

可采用：顺序结构和链式结构两种；

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

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

先序遍历：

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

中序遍历：

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

后序遍历：

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

线索二叉树
有时间再写