definition

树是多种数据逻辑结构中的其中一种分支结构，基本定义如下：

树(tree)是包含n(n>0)个结点的有穷集，其中： 每个元素称为结点(node)； 有一个特定的结点被称为根结点或树根(root)。 除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti(1<=i<=m)本身也是一棵树，被称作原树的子树(subtree)

在这种结构下可以分成多种不同类型的树，以不同的分类方式可以分成多种不同的树。如下：

  1. 按节点的数量：
    • 二叉树
    • 三叉树
    • 多叉树
/*   A simple binary tree
 *        A ---------> A is root node
 *      /   \
 *     B     C ---> leaves: B, C
 *       (1)      ---> Height: 2
 *       
 *        A ---------> A is root node
 *      / | \
 *     B  C  E ---> leaves: B, C, E
 *       (1)      ---> Height: 2  
 *       
 *        A ---------> A is root node
 *      //|\\
 *    / / | \ \
 *   B C  E  F G
 *     ---> leaves: B, C, E, F, G
 *       (1)      ---> Height: 2        
 * */
  1. 按左右子树高度是否平衡：
    • 平衡树
    • 普通树
  2. 按节点是否排序：
    • 排序树
    • 无序树

basic operators

对树的基本操作实质上如同对其他类型的数据结构的操作一样，也是由基本的CURD组成的，如下：

(1)InitTree(T)
   操作结果：构造空树T。
(2) DestroyTree(T)
   初始条件：树T存在。
   操作结果：销毁树T。
(3)CreateTree(T,definition)
    初始条件：definition给出树T的定义
    操作结果：按definition构造树T
(4)ClearTree(T)
    初始条件：树T存在
    操作结果：将树T清为空树
(5)TreeEmpty(T)
    初始条件：树T存在
    操作结果：若T为空树，则返回TRUE，否则FALSE
(6)Root(T)
    初始条件：树T存在
    操作结果：返回T的根
(7)Value(T,cur_e)
    初始条件：树T存在,cur_e是T中某个结点。
    操作结果：返回cur_e的值
(8)Assign(T,cur_e,value)
    初始条件：树T存在
    操作结果：结点cur_e赋值为value
(9)InsertChild(T,p,i,c)
    初始条件：树T存在,p指向T中某个结点，1<=i<=p所指结点的度+1，非空树c与T不想交。
    操作结果：插入c为T中p指结点的第i棵子树
(10)DeleteChild(T,p,i)
    初始条件：树T存在，p指向T中某个结点，1<=i<=p指结点的度
    操作结果：删除T中p所指结点的第i棵子树。
(11)TraverseTree(T,Visit())
    初始条件：树T存在,Visit是对结点操作的应用函数。
    操作结果：按某种次序对T的每个结点调用函数Visit()一次且至多一次。一旦Visit()失败，则操作失败

create tree

对于树的任何操作都有一个大前提，这个前提是有一颗可供操作的树，所以对树的构建是所有操作的大前提。而树的构建方式就决定了树拥有的性质和特点。

树的构建实质上是等同于将集合中的元素按先后次序插入一颗空树中，所以插入操作是构建树的最基本操作，如下：

/**
* 构建二叉查找树
*/
List : {E, B, C, F, G, D, H, A}
Pseudo code:
    root = E
    for i in List
        insert(root, i)
    end
Tree: 
        E
       / \
      B   F
     / \   \
    A   C   G
         \   \
          D   H

insert child

对于树的所有操作中，插入操作可以说是最为基础的操作，所以使用的频率也几乎是最高的，但复杂的并不是插入操作的本身，而是为了保持树的某种特性而附加的操作，如：在二叉平衡树中添加保持左右子树平衡的操作。

所以插入操作的实现一般是在原有的普通插入操作上附加上其他操作，下面以红黑树的插入操作作为例子：

private Node put(Node h, Key key, Value val) {
    if (h == null) return new Node(key, val, RED, 1);

    //普通的排序插入操作
    int cmp = key.compareTo(h.key);
    if      (cmp < 0) h.left  = put(h.left,  key, val);
    else if (cmp > 0) h.right = put(h.right, key, val);
    else              h.val   = val;

    // fix-up any right-leaning links
    if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
    if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
    if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);
    h.size = size(h.left) + size(h.right) + 1;

    return h;
}

traverse tree

由于树的遍历对于树来说是一个最为基本的操作，几乎所有

reference