树的基本概念

树的定义

树是一种递归数据结构，它有n个节点的有限集合T，在一棵树中有且仅有一个称为根的节点，其余节点可分为m个互不相交的集合T1,T2,···,Tm,其中，每一个集合本身又是一棵树，并称为根的子树。
度：树中每个节点具有的子树数或者后继节点数称为该节点的度。一棵树中各节点度数的最大值称为这个树的度
深度：树是层次结构，一颗树中最大层数称为此树的深度或高度。
森林：n个树的集合称为森林。
树状结构的逻辑特征：树中任一节点都可以有0个或多个直接后继节点，但至多只能有一个直接前驱节点。树中只有开始节点无前趋，是开始节点。叶节点无后继，则是终端节点。

二叉树

二叉树是有限元素的集合，该集合或者为空，或者由一个称为根元素及两个不相交的被称为左子树和右子树的二叉树组成，当集合为空时，称该二叉树为空二叉树。
所有分支节点都有左子树和右子树，并且所有叶子节点都在同一层上，这样一颗二叉树称为满二叉树。
叶子节点只出现在最下层和次下层，且最下层的叶子节点集中在树的左部的二叉树称为完全二叉树。

图片.png

二叉树是有序的，左右子树颠倒，就成为另一颗不同的二叉树，即使只有一颗子树，也要区分他是左子树还是右子树。

树和二叉树的区别

没有空树有空二叉树。
树子树直接没序，二叉树子树之间有序。
二叉树最多只能有两个子树。
二叉树有以下几个性质：TODO(上标和下标)

二叉树性质

1. 在二叉树的第ｉ（ｉ>=１）层最多有２＾(ｉ - １)个结点。
2. 深度为k(k>=0)的二叉树最少有k个结点，最多有２＾ｋ－１个结点。
3. 对于任一棵非空二叉树，若其叶结点数为n0，度为2的非叶结点数为n2，则ｎ0 = ｎ2 ＋１。
4. 具有n个结点的完全二叉树的深度为int_UP（log(2，ｎ+1)）。
5. 如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号１，２，３，．．．．．．，ｎ，然后按此结点编号将树中各结点顺序的存放于一个一维数组，并简称编号为i的结点为结点i（ ｉ>=１ && ｉ<=ｎ）,则有以下关系：
   （1）若 ｉ= 1，则结点i为根，无父结点；若 ｉ> 1，则结点 i 的父结点为结点int_DOWN（ｉ / ２）;
   （2）若 ２＊ｉ <= ｎ，则结点 ｉ 的左子女为结点 ２＊ｉ；
   （3）若２＊ｉ＜＝ｎ，则结点ｉ的右子女为结点２＊ｉ＋１；
   （4）若结点编号ｉ为奇数，且ｉ！＝１，它处于右兄弟位置，则它的左兄弟为结点ｉ－１；
   （5）若结点编号ｉ为偶数，且ｉ！＝ｎ，它处于左兄弟位置，则它的右兄弟为结点ｉ＋１；
   （6）结点ｉ所在的层次为 int_DOWN（log（2，ｉ））＋１。

二叉树的存储结构

满二叉树和完全二叉树可采取顺序存储，非完全二叉树，采用链式存储更好。