- 每个节点都只有有限个子节点或无子节点。
- 没有父节点的节点称为根节点。
- 每一个非根节点有且只有一个父节点。
- 除了根节点外，每个子节点可以分为多个不相交的子树。
- 树里面没有环路。
- 节点的度：一个节点含有的子树的个数称为该节点的度。
- 树的度：一棵树中，最大的节点度称为树的度。
- 叶节点或终端节点：度为零的节点。(一般叫叶节点居多)
- 非终端节点或分支节点：度不为零的节点。
- 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。
- 兄弟节点：具有相同父节点的节点互称为兄弟节点。
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
- 深度：对于任意节点n，n的深度为从根到n的唯一路径长，根的深度为0。
- 高度：对于任意节点n，n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0。
- 堂兄弟节点：父节点在同一层的节点互为堂兄弟。
- 节点的祖先：从根到该节点所经分支上的所有节点。
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林：由m（m ≥ geq ≥ 0）颗互不相交的树的集合称为森林。
- 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也成为自由树。
- 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树。
- 二叉树：每个节点最多含有两个子树的树称为二叉树。
- 完全二叉树：对于一颗二叉树，假设其深度为d（d>1），除了d层外，其他各层各层的节点数目均已达到最大值，且第d层所有节点从左到右连续地紧密排列，这样的二叉树叫完全二叉树。
- 满二叉树：所有叶节点都在最底层的完全二叉树。
- 平衡二叉树（AVL树）：当且仅当任意节点的两棵子树的高度差不大于1的二叉树。
- 排序二叉树（二叉查找树）：
①若任意节点的左子树不为空，则左子树上所有节点的值都小于它的根节点的值。
②若任意节点的右子树不为空，则右子树上所有节点的值都大于它的根节点的值。
③任意节点的左右子树也分别为二叉查找树。 - 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树。
- B树：一种对读写操作优化的自平衡的二叉查找树，能够保持数据有序，拥有多余2个子树。
- 红黑树： 一种自平衡二叉查找树。
- 二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
- 二叉树的第i层至多拥有 2 i − 1 2^i-1 2i−1个节点；深度为k的二叉树至多总共有 2 k + 1 − 1 2^{k+1}-1 2k+1−1个节点（定义根节点所在深度 k 0 = 0 k_0=0 k0=0）
- 对任何一颗非空的二叉树T，如果其叶片数为n0，分支度为2的节点数为n2，则n0=n2+1
二叉树可以用数组或链接串列来存储。根节点的索引为0，如果某个节点的索引为i，那么它的：
- 左子节点索引为 2 i + 1 2i+1 2i+1
- 右子节点为 2 i + 2 2i+2 2i+2
- 父节点为
i
−
1
2
frac {i-1} {2}
2i−1
伪代码：
#define MAX_TREE_SIZE 100
typedef TELemType SqBiTree[MAX_TREE_SIZE]
typedef struct
{
int level, order;
}position;
1.2 优点：
- 更有利于紧凑存储。
- 更好的访问局部性。
- 前序遍历更方便。
- 需要连续的存储空间，如果深度为h的二叉树其每个节点都只有右子节点，那么需要占用 2 h − 1 2^h-1 2h−1的空间，实际上却只有h个节点，极大的浪费了空间。
在使用记录或存储器地址指针的程序设计语言中，二叉树通常用树结点结构来存储。如果一个结点的子结点个数小于2，一些子结点指针可能为空值，或者为特殊的哨兵结点。
伪代码：
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
2.2 优点
使用链表能避免顺序存储浪费空间的问题，算法和结构相对简单。
2.3 缺点使用二叉链表，由于缺乏父链的指引，在找回父节点时需要重新扫描树得知父节点的节点地址。
3、三叉链表存储表示 3.1 定义改进于二叉链表，增加父节点的指引。
3.2 优点能更好地实现节点间的访问。
3.3 缺点①不过算法相对复杂。
②当二叉树用三叉链表表示时，有N个结点，就会有N+2个空指针。
所有遍历方法的时间复杂度都是O(n)
1、深度优先遍历 1.1 前(先)序遍历先访问根节点，再访问左子节点，最后访问右子节点
visit(node)
print node.value
if node.left != null then visit(node.left)
if node.right != null then visit(node.right)
1.2 中序遍历
先访问左子节点，再访问根节点，最后访问右子节点
visit(node)
if node.left != null then visit(node.left)
print node.value
if node.right != null then visit(node.right)
1.3 后序遍历
先访问左子节点，再访问右子节点，最后访问根节点
visit(node)
if node.left != null then visit(node.left)
if node.right != null then visit(node.right)
print node.value
以上的递归算法使用与树的高度成比例的栈空间
2、广度优先遍历和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。
下面判断完全二叉树的代码，用到了广度优先遍历。
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。。
判断完全二叉树代码：
public class TreeNode
{
public TreeNode LeftNode;
public TreeNode RightNode;
public int Data;
public TreeNode(int d)
{
Data = d;
LeftNode = null;
RightNode = null;
}
}
public class IntTree
{
public TreeNode root;
public bool IsComplete()
{
if (root == null)
{
return false;
}
// 广度优先遍历
Queue q = new Queue();
q.Enqueue(root);
while(q.Count > 0)
{
TreeNode top = q.Dequeue();
bool leftEmpty = top.LeftNode == null;
bool rightEmpty = top.RightNode == null;
if (!leftEmpty && !rightEmpty )
{
q.Enqueue(top.LeftNode);
q.Enqueue(top.RightNode);
}
else if (leftEmpty && !rightEmpty )
{
return false;
}
else if ((!leftEmpty && rightEmpty) || (leftEmpty && rightEmpty))
{
if (!leftEmpty && rightEmpty)
{
q.Enqueue(top.LeftNode);
}
while(q.Count > 0)
{
top = q.Dequeue();
if (top.LeftNode == null && top.rightNode == null)
{
}
else
{
return false;
}
}
}
}
return true;
}
}
