二叉树

炒现饭的帖子，内容均来自于网络或者书籍整理。

I)树
它是由N(N>=1)个有限结点组成一个具有层次关系的集合，它具有以下的特点：
a)每个结点有零个或多个子结点，没有子节点的节点称为叶节点(通常称为叶子)
b)没有父结点的结点称为根结点(通常称为根)
c)每一个非根结点有且只有一个父结点(没有多个引用指向同一个节点)
d)除了根结点外，每个子结点可以分为M个不相交的子树

|
r        55
o       /  \
o      /    \
t     88     3
.           /|\
.          / | \
.         67 7 23
l        / \     \
e       /   \     \
a      53    5     9
f
|

        Figure. A

如上图(Figure. A)，它像一棵自然界中倒生长的树，每个枝丫处就是一个节点，方向是由根到叶子，它实际上是一个有向图。

这里我们介绍下节点，节点是包含一个数据项和一个(多个)指向其他节点的引用项的数据结构/记录，通常我们用类似如下代码来表示一个节点：
1)

record SinglyLinkedNode {
    next, // A reference to the next node
    data // Data or reference to data
}

2)

record DoublyLinkedNode {
    previous, // A reference to the previous node
    next, // A reference to the next node
    data // Data or reference to data
}

3)

record BinaryNode {
    parent, // A reference to the parent node                                
    left_child, // A reference to the left child node
    right_child, // A reference to the right child node
    data // Data or reference to data
}

结合上图(Figure. A)我们就很好理解了。

一些有关树的基本概念：
节点的度(node’s degree): 子节点的个数叫做节点的度
树的度: 一棵树中，最大的节点的度称为树的度
节点层次(level): 根为第一层，根的子节点为第二层，以此类推
数的高度或深度(depth): 树中最大的节点层次
兄弟节点(siblings): 具有相同父节点的节点
森林: M(M>=0)棵互不相交的树的集合(删去一棵树的根，就得到一个森林；加上一个结点作树根，森林就变为一棵树)
有序树(ordered tree)/无序树(unodered tree): 若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(ordered tree)；否则称为无序树(unodered tree)
还有诸如子孙/祖先/堂兄弟节点这些概念就不列举了

上图(Figure. A)当中，树的度是3，67节点的度是2，数的深度是4，55节点是根节点等等这些基本属性我们就能很快得出。

II)二叉树
每个结点最多有两个子树的有序树，通常有左子树(left subtree)和右子树(right subtree)，最大的节点的度为2，也就是二叉树的度为2。

满二叉树(full binary tree): 有时被称为proper binary tree或者2-tree或者strictly binary tree，就是每个节点有0或2个子节点。

完全二叉树(complete binary tree): 除了最后一层之外的其他层次(当然也可能包含最后一层)，每个节点都包含2个子节点，并且所有节点都尽可能靠左排列

平衡二叉树: 如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树

二叉树的遍历，前序(pre-order)，中序(in-order)和后序(post-order)，前序是根左右，中序是左根右，后序是左右根。

一些有关二叉树的常用算法参看http://blog.csdn.net/luckyxiaoqiang/article/details/7518888

几个简单的例子:

这里的代码实现都是简单易懂的实现，帮助理解概念，没有做过优化！

参考资料:
http://en.wikipedia.org/wiki/Tree_(data_structure)
http://en.wikipedia.org/wiki/Node_(computer_science)
http://en.wikipedia.org/wiki/Branching_factor
http://en.wikipedia.org/wiki/Binary_tree

http://zhedahht.blog.163.com/blog/static/25411174201142733927831/