数据结构之树&&常见二叉树学习
文章内容来自课件内容，个别细节做了简单的补充！！！
树：数据对象 D：D是具有相同特性数据元素的集合。
数据关系 R：
若D为空集，则称为空树；
否则:
(1) 在D中存在唯一的称为根的数据元素root,
(2) 当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm, 其中每一棵子集本身又是一棵符合本定义的树，
称为根root的子树。
树的基本术语
结点:数据元素+若干指向子树的分支
结点的度:分支的个数
树的度:树中所有结点的度的最大值
叶子结点:度为零的结点
分支结点:度大于零的结点
(从根到结点的)路径：由从根到该结点所经分支和结点构成
孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点、子孙结点
结点的层次:假设根结点的层次为1,第k 层的结点的子树根结点的层次为k+1
树的深度：树中叶子结点所在的最大层次
森林：是m（m≥0）棵互不相交的树的集合
任何一棵非空树是一个二元组Tree = （root，F）
其中：root 被称为根结点，F 被称为子树森林
二叉树的类型定义
1.或为空树；
2.或是由一个根结点构成;
3.或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成;
等价定义：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
二叉树的五种基本形态：
二叉树的特性：
1) 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
2) 树的结点无左、右之分，而二叉树的结点有左、右之分。
二叉树的重要特性
•性质 1 ：在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1)
•性质 2 ：深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）
证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为
2^0+2^1+ …… +2^(k-1) = 2^k-1
§ 性质 3 ：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1
证明：设 二叉树上结点总数 n = n0 + n1 + n2
又 二叉树上分支总数 b = n1 + 2n2 而 b = n-1 (因为除了根节点外每个节点都有树相连！！！)
故 n1 + 2n2= n0 + n1 + n2 - 1 由此， n0 = n2 + 1
两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。
完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。
换句话说，完全二叉树可以理解为从满二叉树自上而下从左到右一个个节点复制但是随时会终止复制的二叉树！！！
也就是除了最底层的节点数没满，其他层数的节点数达到了最大，同时，最底层的节点数从左到右排列
性质 4 ：具有 n 个结点的完全二叉树的深度为 ⌊log2n⌋ +1
例：在含有968个结点的完全二叉树中，
叶子结点的个数为多少？
解：n0 = n2+1；（性质3）n0 ＋ n1＋ n2＝968
2 n2＋ n1 ＋1＝968 2 n2＋ n1 ＝967
完全二叉树中度为1的结点个数为1或0；
如果完全二叉树结点个数为奇数，则度为1的结点个数为0.
在含有968个结点的完全二叉树中，度为1的结点个数为1。 即：n1 = 1;
2n2 +1= 966 n2 = 483 n0 = n2+1 = 484
二叉树的存储结构
一、 二叉树的顺序存储表示 二、二叉树的链式存储表示
•性质 5 ：若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
(1) 若 i=1，则该结点是二叉树的根，无双亲,否则，编号为 ëi/2û 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。
二、二叉树的链式存储表示
1. 二叉链表
2．三叉链表
3．双亲链表
4．线索链表