二叉树及其遍历

转自：http://www.iteye.com/topic/561141

一、数据结构分类

（一）按逻辑结构

1. 集合(无辑关系)
2. 线性结构(线性表)：数组、链表、栈、队列
3. 非线性结构：树、图、多维数组

（二）按存储结构

顺序（数组）储结构、链式储结构、索引储结构、散列储结构

二、二叉树相关性质

• 结点的度：一个结点的子树的个数记为该结点的度．
• 树的度：所有节点中度数最大的结节的度数，叶子节点的度为零。
• 树的高度：一棵树的最大层次数记为树的高度(或深度)。
• 有序(无序)树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树。否则称为无序树。
• 二叉树第i层（i≥1）上至多有2^(i-1)个节点。
• 深度为k的二叉树至多有2^k-1个节点（k≥1）。
• 对任何一棵二叉，若叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。
• 具有n个节点的完全二叉树的深度为 (㏒2^n)(向下取整)+1。
• 对一棵有n个节点的完全二叉树的节点按层次从上到下，自左至右进行编号，则对任一节点 i(1≤i≤n)有：若 i=1，则节点i是二叉树的根，无双亲；若 i>1，则其双亲为 i/2(向下取整)。若2i>n，则节点i没有孩子节点，否则其左孩子为2i。若2i+1>n，则节点i没有右孩子，否则其右孩子为 2i+1。
• 若深度为k的二叉树有2^k-1个节点，则称其为满二叉树。满二叉树是一棵完全二叉树。

• 对于完全二叉树中，度为1的节点个数只可能为1个或0个。
• 对于二叉树，如果叶子节点数为n0，度为1的节点数为n1，度为2的节点数为n2，则节点总数n = n0 + n1 + n2。
• 对于任意树，总节点数 = 每个节点度数和 + 1
• 二叉树的高度等于根与最远叶节点（具有最多祖先的节点）之间分支数目。空树的高度是-1。只有单个元素的二叉树，其高度为0。
  

.

三、二叉树的遍历

遍历是按某种策略访问树中的每个节点，且仅访问一次。

（一） 二叉树结构实现

package
 tree.bintree;

/**
 * 创建 非完全二叉树、完全二叉树、满二叉树
 *
 * 由于二叉树的节点增加没有什么规则，所以这里只是简单的使用了递一
 * 次性把整棵树创建出来，而没有设计出一个一个添加节点的方法与删除
 *
 * @author jzj
 * @date 2009-12-23
 */
public
 
class
 BinTree {
// Bin=Binary(二进位的, 二元的)

    protected
 Entry root;
//根
    private
 
int
 size;
//树的节点数

    /**
     * 树的节点结构
     * @author jzj
     * @date 2009-12-23
     */
    protected
 
static
 
class
 Entry {
        int
 elem;
//数据域，这里我们作为编号
        Entry left;//左子树
        Entry right;//右子树

        public
 Entry(
int
 elem) {
            this
.elem = elem;
        }

        public
 String toString() {
            return
 
" number="
 + elem;
        }
    }

    /**
     * 根据给定的节点数创建一个完全二叉树或是满二叉树
     * @param nodeCount 要创建节点总数
     */
    public
 
void
 createFullBiTree(
int
 nodeCount) {
        root = recurCreateFullBiTree(1
, nodeCount);
    }

    /**
     * 递归创建完全二叉树
     * @param num 节点编号
     * @param nodeCount 节点总数
     * @return TreeNode 返回创建的节点
     */
    private
 Entry recurCreateFullBiTree(
int
 num, 
int
 nodeCount) {
        size++;
        Entry rootNode = new
 Entry(num);
//根节点
        //如果有左子树则创建左子树
        if
 (num * 
2
 <= nodeCount) {
            rootNode.left = recurCreateFullBiTree(num * 2
, nodeCount);
            //如果还可以创建右子树，则创建
            if
 (num * 
2
 + 
1
 <= nodeCount) {
                rootNode.right = recurCreateFullBiTree(num * 2
 + 
1
, nodeCount);
            }
        }
        return
 (Entry) rootNode;
    }

    /**
     * 根据给定的数组创建一棵树，这个棵树可以是完全二叉树也可是普通二叉树
     * 数组中为0的表示不创建该位置上的节点
     * @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
     */
    public
 
void
 createBinTree(
int
[] nums) {
        root = recurCreateBinTree(nums, 0
);
    }

    /**
     * 递归创建二叉树
     * @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
     * @param index 需要使用数组中的哪个元素创建节点，如果为元素为0，则不创建
     * @return TreeNode 返回创建的节点，最终会返回树的根节点
     */
    private
 Entry recurCreateBinTree(
int
[] nums, 
int
 index) {
        //指定索引上的编号不为零上才需创建节点
        if
 (nums[index] != 
0
) {
            size++;
            Entry rootNode = new
 Entry(nums[index]);
//根节点
            //如果有左子树则创建左子树
            if
 ((index + 
1
) * 
2
 <= nums.length) {
                rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1
) * 
2
 - 
1
);
                //如果还可以创建右子树，则创建
                if
 ((index + 
1
) * 
2
 + 
1
 <= nums.length) {
                    rootNode.right = (Entry) recurCreateBinTree(nums, (index + 1
) * 
2
);
                }
            }
            return
 (Entry) rootNode;
        }
        return
 
null
;

    }

    public
 
int
 size() {
        return
 size;
    }

    //取树的最左边的节点
    public
 
int
 getLast() {
        Entry e = root;
        while
 (e.right != 
null
) {
            e = e.right;
        }
        return
 e.elem;
    }

    //测试
    public
 
static
 
void
 main(String[] args) {

        //创建一个满二叉树
        BinTree binTree = new
 BinTree();
        binTree.createFullBiTree(15
);
        System.out.println(binTree.size());//15
        System.out.println(binTree.getLast());//15

        //创建一个完全二叉树
        binTree = new
 BinTree();
        binTree.createFullBiTree(14
);
        System.out.println(binTree.size());//14
        System.out.println(binTree.getLast());//7

        //创建一棵非完全二叉树
        binTree = new
 BinTree();
        int
[] nums = 
new
 
int
[] { 
1
, 
2
, 
3
, 
4
, 
0
, 
0
, 
5
, 
0
, 
6
, 
0
, 
0
, 
0
, 
0
, 
7
, 
8
 };
        binTree.createBinTree(nums);
        System.out.println(binTree.size());//8
        System.out.println(binTree.getLast());//8

    }
}

（二）利用二叉树本身特点进行递归遍历（属内部遍历）

由于二叉树所具有的递归性质，一棵非空的二叉树可以看作是由根节点、左子树和右 子树3部分构成，因为若能依次遍历这3部分的信息，也就遍历了整个二叉树。按照左子树的遍历在右子树的遍历之前进行的约定，根据访问根节点位置的不同，可 以得到二叉的前序、中序、后序3种遍历方法。

package
 tree.bintree;

/**
 * 二叉树的三种 内部 遍历：前序、中序、后序
 * 但不管是哪种方式，左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都
 * 必须遵循的约定
 * @author jzj
 * @date 2009-12-23
 */
public
 
class
 BinTreeInOrder 
extends
 BinTree {

    /**
     * 节点访问者，可根据需要重写visit方法
     */
    static
 
abstract
 
class
 Visitor {
        void
 visit(Object ele) {
            System.out.print(ele + " "
);
        }
    }

    public
 
void
 preOrder(Visitor v) {
        preOrder(v, root);
    }

    /**
     * 树的前序递归遍历 pre=prefix(前缀)
     * @param node 要遍历的节点
     */
    private
 
void
 preOrder(Visitor v, Entry node) {
        //如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null
        if
 (node != 
null
) {
            v.visit(node.elem);//先遍历父节点
            preOrder(v, node.left);//再遍历左节点
            preOrder(v, node.right);//最后遍历右节点
        }
    }

    public
 
void
 inOrder(Visitor v) {
        inOrder(v, root);
    }

    /**
     * 树的中序递归遍历 in=infix(中缀)
     * @param node 要遍历的节点
     */
    private
 
void
 inOrder(Visitor v, Entry node) {
        //如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null
        if
 (node != 
null
) {
            inOrder(v, node.left);//先遍历左节点
            v.visit(node.elem);//再遍历父节点
            inOrder(v, node.right);//最后遍历右节点
        }
    }

    public
 
void
 postOrder(Visitor v) {
        postOrder(v, root);
    }

    /**
     * 树的后序递归遍历 post=postfix(后缀)
     * @param node 要遍历的节点
     */
    private
 
void
 postOrder(Visitor v, Entry node) {
        //如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null
        if
 (node != 
null
) {
            postOrder(v, node.left);//先遍历左节点
            postOrder(v, node.right);//再遍历右节点
            v.visit(node.elem);//最后遍历父节点
        }
    }

    //测试
    public
 
static
 
void
 main(String[] args) {

        //创建二叉树
        int
[] nums = 
new
 
int
[] { 
1
, 
2
, 
3
, 
4
, 
0
, 
0
, 
5
, 
0
, 
6
, 
0
, 
0
, 
0
, 
0
, 
7
, 
8
 };
        BinTreeInOrder treeOrder = new
 BinTreeInOrder();
        treeOrder.createBinTree(nums);
        System.out.print("前序遍历 - "
);
        treeOrder.preOrder(new
 Visitor() {
        });
        System.out.println();
        System.out.print("中序遍历 - "
);
        treeOrder.inOrder(new
 Visitor() {
        });
        System.out.println();
        System.out.print("后序遍历 - "
);
        treeOrder.postOrder(new
 Visitor() {
        });
        /*
         * output:
         * 前序遍历 - 1 2 4 6 3 5 7 8
         * 中序遍历 - 4 6 2 1 3 7 5 8
         * 后序遍历 - 6 4 2 7 8 5 3 1
         */
    }
}

（三）二叉树的非递归遍历（属外部遍历）

1、利用栈与队列对二叉树进行非递归遍历

package
 tree.bintree;

import
 java.util.Iterator;
import
 java.util.LinkedList;
import
 java.util.Stack;

/**
 * 二叉树的外部遍历：深度优先（先根）、广度（层次）优先遍历
 *
 * @author jzj
 * @date 2009-12-23
 */
public
 
class
 BinTreeOutOrder 
extends
 BinTree {

    /**
     * 二叉树深序优先遍历（即二叉树的先根遍历）迭代器，外部可以使用该迭代器
     * 进行非递归的遍历，这是一种在二叉树结构外部的一种遍历算法，它没有使用
     * 二叉树本身的结构特点（左右子树递归）进行递归遍历
     * @author jzj
     */
    private
 
class
 DepthOrderIterator 
implements
 Iterator {
        //栈里存放的是每个节点
        private
 Stack stack = 
new
 Stack();

        public
 DepthOrderIterator(Entry node) {

            //根入栈，但在放入左右子节点前会马上出栈，即根先优于左右子节点访问
            stack.push(node);

        }

        //是否还有下一个元素
        public
 
boolean
 hasNext() {
            if
 (stack.isEmpty()) {
                return
 
false
;
            }
            return
 
true
;
        }

        //取下一个元素
        public
 Entry next() {
            if
 (hasNext()) {
                //取栈顶元素
                Entry treeNode = (Entry) stack.pop();//先访问根

                if
 (treeNode.right != 
null
) {
                    stack.push(treeNode.right);//再放入右子节点
                }

                if
 (treeNode.left != 
null
) {
                    stack.push(treeNode.left);//最后放入左子节点，但访问先于右节点
                }

                // 返回遍历得到的节点
                return
 treeNode;

            } else
 {
                // 如果栈为空
                return
 
null
;
            }
        }

        public
 
void
 remove() {
            throw
 
new
 UnsupportedOperationException();
        }

    }

    /**
     * 向外界提供先根遍历迭代器
     * @return Iterator 返回先根遍历迭代器
     */
    public
 Iterator createPreOrderItr() {
        return
 
new
 DepthOrderIterator(root);
    }

    /**
     * 二叉树广度优先遍历迭代器，外部可以使用该迭代器
     * 进行非递归的遍历，这是一种在二叉树结构外部的一种遍历算法，它没有使用
     * 二叉树本身的结构特点（左右子树递归）进行递归遍历
     * @author jzj
     */
    private
 
class
 LevelOrderIterator 
implements
 Iterator {
        //使用队列结构实现层次遍历，队列里存储的为节点
        private
 LinkedList queue = 
new
 LinkedList();

        public
 LevelOrderIterator(Entry node) {

            if
 (node != 
null
) {
                //将根入队
                queue.addLast(node);
            }
        }

        //是否还有下一个元素
        public
 
boolean
 hasNext() {
            if
 (queue.isEmpty()) {
                return
 
false
;
            }
            return
 
true
;
        }

        //取下一个元素
        public
 Entry next() {
            if
 (hasNext()) {
                //取栈顶迭元素
                Entry treeNode = (Entry) queue.removeFirst();

                if
 (treeNode.left != 
null
) {
//如果有左子树，加入有序列表中
                    queue.addLast(treeNode.left);
                }
                if
 (treeNode.right != 
null
) {
//如果有右子树，加入有序列表中
                    queue.addLast(treeNode.right);
                }

                // 返回遍历得到的节点
                return
 treeNode;

            } else
 {
                // 如果队列为空
                return
 
null
;
            }
        }

        public
 
void
 remove() {
            throw
 
new
 UnsupportedOperationException();
        }

    }

    /**
     * 向外界提供广度优先迭代器
     * @return Iterator 返回遍历迭代器
     */
    public
 Iterator createLayerOrderItr() {
        return
 
new
 LevelOrderIterator(root);
    }

    public
 
static
 
void
 main(String[] args) {
        //创建一棵满二叉树
        BinTreeOutOrder treeOrder = new
 BinTreeOutOrder();
        treeOrder.createFullBiTree(15
);
        Iterator preOrderItr = treeOrder.createPreOrderItr();
        System.out.print("深度优先（先根）遍历 - "
);
        while
 (preOrderItr.hasNext()) {
            System.out.print(((Entry) preOrderItr.next()).elem + " "
);
        }
        System.out.println();
        System.out.print("广度优先（层次）遍历 - "
);
        Iterator layerOrderItr = treeOrder.createLayerOrderItr();
        while
 (layerOrderItr.hasNext()) {
            System.out.print(((Entry) layerOrderItr.next()).elem + " "
);
        }
        /*
         * output:
         * 深度优先（先根）遍历 - 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15
         * 广度优先（层次）遍历 - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
         */
    }
}

2、利用二叉树节点的父节点指针进行非递归遍历

要想采用非递归的方法遍历树，又不借助于前面的队列与栈，我们需要该树是一棵可回溯的二叉树，即从子节点要能够知道他的父节点及祖先节点，与前面的二叉树不同的是，树的节点结构体中多一个指向父的节点指针，这样外界可以以非递归的方式来遍历二叉树了 。

package
 tree.bintree;

/**
 *
 * 可回溯的二叉树
 * 二叉树的非递归遍历
 *
 * @author jzj
 * @date 2009-12-23
 */
public
 
class
 BackBinTree {
// Bin=Binary(二进位的, 二元的)

    protected
 Entry root;
//根
    private
 
int
 size;
//树的节点数

    /**
     * 树的节点结构
     * @author jzj
     * @date 2009-12-23
     */
    private
 
static
 
class
 Entry {
        int
 elem;
//数据域，这里为了测试，就作为节点编号吧
        Entry paraent;//父节点
        Entry left;//左节点
        Entry right;//右节点

        //构造函数只有两个参数，左右节点是调用add方法时设置
        public
 Entry(
int
 elem, Entry parent) {
            this
.elem = elem;
            this
.paraent = parent;
        }
    }

    /**
     * 查找前序遍历（根左右）直接后继节点
     *
     * 以非递归 根左右 的方式遍历树
     *
     * @param e 需要查找哪个节点的直接后继节点
     * @return Entry 前序遍历直接后继节点
     */
    public
 Entry preOrderSuccessor(Entry e) {
        if
 (e == 
null
) {
            return
 
null
;
        }//如果左子树不为空，则直接后继为左子节点
        else
 
if
 (e.left != 
null
) {
//先看左子节点是否为空
            return
 e.left;
//如果不为空，则直接后继为左子节点
        }//否则如果右子树不为空，则直接后继为右子节点
        else
 
if
 (e.right != 
null
) {
//如果左子节点为空，则看右子节点是否为空
            return
 e.right;
//如果右子节点不为空，则返回
        }//左右子节点都为空的情况下
        else
 {
            Entry s = e.paraent;
            Entry c = e;

            /*
            * 一直向上，直到c是s的左子树，且s的右子树不为空。请试着找一下36与68节点的
            * 直接后继节点，36的应该是75，而68则没有后继节点了
            *
            *                            50
            *                            /\
            *                          37  75
            *                         /    /
            *                       25    61
            *                      /\     /\
            *                    15 30   55 68
            *                       /\    \
            *                     28 32   59
            *                         \
            *                         36
            */
            while
 (s != 
null
 && (c == s.right || s.right == 
null
)) {
                c = s;
                s = s.paraent;
            }
            //退出循环时 s 可以为null，比如查找 68 节点的直接后继时退出循环时s=null
            if
 (s == 
null
) {
                return
 
null
;
            } else
 {
                return
 s.right;
            }
        }
    }

    /**
     * 查找前序遍历（根左右）直接前驱节点
     *
     * 以非递归 右左根 的方式遍历树
     *
     * @param e 需要查找哪个节点的直接前驱节点
     * @return Entry 前序遍历直接前驱节点
     */
    public
 Entry preOrderAncestor(Entry e) {
        if
 (e == 
null
) {
            return
 
null
;
        }//如果节点为父节点的左节点，则父节点就是直接前驱节点
        else
 
if
 (e.paraent != 
null
 && e == e.paraent.left) {
            return
 e.paraent;
        }//如果节点为父节点的右节点
        else
 
if
 (e.paraent != 
null
 && e == e.paraent.right) {

            Entry s = e.paraent;//前驱节点默认为父节点
            if
 (s.left != 
null
) {
//如果父节点没有左子，前驱节点就为父节点
                s = s.left;//如果父节点的左子节点不空，则初始为父节点左子节点

                /*
                * 只要父节点左子节点还有子节点，则前驱节点要从其子树中找。请试着找
                * 一下75直接前驱节点，应该是36
                *
                *                            50
                *                            /\
                *                          37  75
                *                         /    /
                *                       25    61
                *                      /\     /\
                *                    15 30   55 68
                *                       /\    \
                *                     28 32   59
                *                         \
                *                         36
                */
                while
 (s.left != 
null
 || s.right != 
null
) {
                    //在父节点的左子节点的子树中查找时，一定要先向右边拐
                    if
 (s.right != 
null
) {
                        s = s.right;
                    } else
 {
//如果右边没有，然后才能向左边拐
                        s = s.left;
                    }
                }
            }
            return
 s;
        } else
 {
//如果是根节点，则没有直接前驱节点了
            return
 
null
;
        }
    }

    /**
     * 查找后序遍历（左右根）直接后继节点
     *
     * 以非递归 左右根 的方式遍历树
     *
     * @param e 需要查找哪个节点的直接后继节点
     * @return Entry 后序遍历直接后继节点
     */
    public
 Entry postOrderSuccessor(Entry e) {
        if
 (e == 
null
) {
            return
 
null
;
        }//如果节点为父节点的右子节点，则父节点就是直接后继节点
        else
 
if
 (e.paraent != 
null
 && e == e.paraent.right) {
            return
 e.paraent;
        }//如果节点为父节点的左子节点
        else
 
if
 (e.paraent != 
null
 && e == e.paraent.left) {
            Entry s = e.paraent;//后继节点默认为父节点
            if
 (s.right != 
null
) {
//如果父节点没有右子，后继节点就为父节点
                s = s.right;//如果父节点的右子节点不空，则初始为父节点右子节点
                /*
                 * 只要父节点右子节点还有子节点，则后断节点要从其子树中找，
                 * 如15的后继节点为28
                 *                            50
                 *                            /\
                 *                          37  75
                 *                         /    /
                 *                       25    61
                 *                      /\     /\
                 *                    15 30   55 68
                 *                       /\    \
                 *                     28 32   59
                 *                         \
                 *                         36
                 */

                while
 (s.left != 
null
 || s.right != 
null
) {
                    //在父节点的右子节点的子树中查找时，一定要先向左边拐
                    if
 (s.left != 
null
) {
                        s = s.left;
                    } else
 {
//如果左边没有，然后才能向右边拐
                        s = s.right;
                    }
                }
            }
            return
 s;
        } else
 {
            //如果是根节点，则没有后继节点了
            return
 
null
;
        }
    }

    /**
     * 查找后序遍历（左右根）直接前驱节点
     *
     * 以非递归 根右左 的方式遍历树
     *
     * @param e 需要查找哪个节点的直接前驱节点
     * @return Entry 后序遍历直接前驱节点
     */
    public
 Entry postOrderAncestor(Entry e) {

        if
 (e == 
null
) {
            return
 
null
;
        }//如果右子树不为空，则直接前驱为右子节点
        else
 
if
 (e.right != 
null
) {
//先看右子节点是否为空
            return
 e.right;
//如果不为空，则直接后继为右子节点
        }//否则如果左子树不为空，则直接前驱为左子节点
        else
 
if
 (e.left != 
null
) {
            return
 e.left;
        }//左右子节点都为空的情况下
        else
 {
            Entry s = e.paraent;
            Entry c = e;

            /*
            * 一直向上，直到c是s的右子树，且s的左子树不为空。请试着找一下59与15节点的
            * 直接后继节点，59的应该是37，而15则没有后继节点了
            *
            *                            50
            *                            /\
            *                          37  75
            *                         /    /
            *                       25    61
            *                      /\     /\
            *                    15 30   55 68
            *                       /\    \
            *                     28 32   59
            *                         \
            *                         36
            */
            while
 (s != 
null
 && (c == s.left || s.left == 
null
)) {
                c = s;
                s = s.paraent;
            }
            if
 (s == 
null
) {
                return
 
null
;
            } else
 {
                return
 s.left;
            }
        }
    }

    /**
     * 查找中序遍历（左根右）直接后继节点
     *
     * 以非递归 左根右 的方式遍历树
     *
     * @param e 需要查找哪个节点的直接后继节点
     * @return Entry 中序遍历直接后继节点
     */
    public
 Entry inOrderSuccessor(Entry e) {
        if
 (e == 
null
) {
            return
 
null
;
        }//如果待找的节点有右子树，则在右子树上查找
        else
 
if
 (e.right != 
null
) {
            //默认后继节点为右子节点（如果右子节点没有左子树时即为该节点）
            Entry p = e.right;
            while
 (p.left != 
null
) {
                //注，如果右子节点的左子树不为空，则在左子树中查找，且后面找时要一直向左拐
                p = p.left;
            }
            return
 p;
        }//如果待查节点没有右子树，则要在祖宗节点中查找后继节点
        else
 {
            //默认后继节点为父节点（如果待查节点为父节点的左子树，则后继为父节点）
            Entry p = e.paraent;
            Entry current = e;//当前节点，如果其父不为后继，则下次指向父节点
            //如果待查节点为父节点的右节点时，继续向上找，一直要找到current为左子节点，则s才是后继
            while
 (p != 
null
 && current == p.right) {
                current = p;
                p = p.paraent;
            }
            return
 p;
        }
    }

    /**
     * 查找中序遍历（左根右）直接前驱节点
     *
     * 以非递归 右根左 的方式遍历树
     *
     * @param e 需要查找哪个节点的直接前驱节点
     * @return Entry 中序遍历直接前驱节点
     */
    public
 Entry inOrderAncestor(Entry e) {
        if
 (e == 
null
) {
            return
 
null
;
        }//如果待找的节点有左子树，则在在子树上查找
        else
 
if
 (e.left != 
null
) {
            //默认直接前驱节点为左子节点（如果左子节点没有右子树时即为该节点）
            Entry p = e.left;
            while
 (p.right != 
null
) {
                //注，如果左子节点的右子树不为空，则在右子树中查找，且后面找时要一直向右拐
                p = p.right;
            }
            return
 p;
        }//如果待查节点没有左子树，则要在祖宗节点中查找前驱节点
        else
 {
            //默认前驱节点为父节点（如果待查节点为父节点的右子树，则前驱为父节点）
            Entry p = e.paraent;
            Entry current = e;//当前节点，如果其父不为前驱，则下次指向父节点
            //如果待查节点为父节点的左节点时，继续向上找，一直要找到current为p的右子节点，则s才是前驱
            while
 (p != 
null
 && current == p.left) {
                current = p;
                p = p.paraent;
            }
            return
 p;
        }
    }

    /**
     * 查找指定的节点
     * @param num
     * @return Entry
     */
    public
 Entry getEntry(
int
 num) {
        return
 getEntry(root, num);
    }

    /**
     * 使用树的先序遍历递归方式查找指定的节点
     *
     * @param entry
     * @param num
     * @return
     */
    private
 Entry getEntry(Entry entry, 
int
 num) {

        //如果找到，则停止后续搜索，并把查找到的节点返回给上层调用者
        if
 (entry.elem == num) {
//1、先与父节点比对
            return
 entry;
        }

        Entry tmp = null
;

        if
 (entry.left != 
null
) {
//2、再在左子树上找
            tmp = getEntry(entry.left, num);
            //如果左子树上找到，返回并停止查找，否则继续在后续节点中找
            if
 (tmp != 
null
) {
                //节点在左子树中找到，返回给上层调用者
                return
 tmp;
            }
        }

        if
 (entry.right != 
null
) {
//3、否则在右子树上找
            tmp = getEntry(entry.right, num);
            //如果右子树上找到，返回并停止查找，否则继续在后续节点中找
            if
 (tmp != 
null
) {
                //节点在右子树中找到，返回给上层调用者
                return
 tmp;
            }
        }

        //当前比较节点 entry 子树为空或不为空时没有找到，直接返回给上层调用者null
        return
 
null
;
    }

    /**
     * 根据给定的数组创建一棵树，这个棵树可以是完全二叉树也可是普通二叉树
     * 数组中为0的表示不创建该位置上的节点
     * @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
     */
    public
 
void
 createBinTree(
int
[] nums) {
        root = recurCreateBinTree(nums, null
, 
0
);
    }

    /**
     * 递归创建二叉树
     * @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
     * @param paraent 父节点
     * @param index 需要使用数组中的哪个元素创建节点，如果为元素为0，则不创建
     * @return Entry 返回创建的节点，最终会返回树的根节点
     */
    private
 Entry recurCreateBinTree(
int
[] nums, Entry pararent, 
int
 index) {
        //指定索引上的编号不为零上才需创建节点
        if
 (nums[index] != 
0
) {
            size++;
            Entry root = new
 Entry(nums[index], pararent);
//根节点
            //如果有左子树则创建左子树
            if
 ((index + 
1
) * 
2
 <= nums.length) {
                root.left = (Entry) recurCreateBinTree(nums, root, (index + 1
) * 
2
 - 
1
);
                //如果还可以创建右子树，则创建
                if
 ((index + 
1
) * 
2
 + 
1
 <= nums.length) {
                    root.right = (Entry) recurCreateBinTree(nums, root, (index + 1
) * 
2
);
                }
            }
            return
 (Entry) root;
        }
        return
 
null
;

    }

    public
 
int
 size() {
        return
 size;
    }

    //测试
    public
 
static
 
void
 main(String[] args) {

        //创建一棵非完全二叉树
        BackBinTree binTree = new
 BackBinTree();
        /*
        *                            50
        *                            /\
        *                          37  75
        *                         /    /
        *                       25    61
        *                      /\     /\
        *                    15 30   55 68
        *                       /\    \
        *                     28 32   59
        *                         \
        *                         36
        */
        int
[] nums = 
new
 
int
[] { 
50
, 
37
, 
75
, 
25
, 
0
, 
61
, 
0
, 
15
, 
30
, 
0
, 
0
, 
55
, 
68
, 
0
, 
0
, 
0
,
                0
, 
28
, 
32
, 
0
, 
0
, 
0
, 
0
, 
0
, 
59
, 
0
, 
0
, 
0
, 
0
, 
0
, 
0
, 
0
, 
0
, 
0
, 
0
, 
0
, 
0
, 
0
, 
36
 };
        binTree.createBinTree(nums);

        Entry entry = binTree.getEntry(50
);
        System.out.print("根左右（先序遍历）- "
);
        while
 (entry != 
null
) {
            System.out.print(entry.elem + " "
);
            entry = binTree.preOrderSuccessor(entry);
        }
        System.out.println();
        entry = binTree.getEntry(68
);
        System.out.print("右左根（先序的逆）- "
);
        while
 (entry != 
null
) {
            System.out.print(entry.elem + " "
);
            entry = binTree.preOrderAncestor(entry);
        }
        System.out.println();
        entry = binTree.getEntry(15
);
        System.out.print("左右根（后序遍历）- "
);
        while
 (entry != 
null
) {
            System.out.print(entry.elem + " "
);
            entry = binTree.postOrderSuccessor(entry);
        }
        System.out.println();

        entry = binTree.getEntry(50
);
        System.out.print("根右左（后序的逆）- "
);
        while
 (entry != 
null
) {
            System.out.print(entry.elem + " "
);
            entry = binTree.postOrderAncestor(entry);
        }
        System.out.println();

        entry = binTree.getEntry(15
);
        System.out.print("左根右（中序遍历）- "
);
        while
 (entry != 
null
) {
            System.out.print(entry.elem + " "
);
            entry = binTree.inOrderSuccessor(entry);
        }
        System.out.println();

        entry = binTree.getEntry(75
);
        System.out.print("右根左（中序的逆）- "
);
        while
 (entry != 
null
) {
            System.out.print(entry.elem + " "
);
            entry = binTree.inOrderAncestor(entry);
        }
        System.out.println();
        /*
         * output:
         * 根左右（先序遍历）- 50 37 25 15 30 28 32 36 75 61 55 59 68
         * 右左根（先序的逆）- 68 59 55 61 75 36 32 28 30 15 25 37 50
         * 左右根（后序遍历）- 15 28 36 32 30 25 37 59 55 68 61 75 50
         * 根右左（后序的逆）- 50 75 61 68 55 59 37 25 30 32 36 28 15
         * 左根右（中序遍历）- 15 25 28 30 32 36 37 50 55 59 61 68 75
         * 右根左（中序的逆）- 75 68 61 59 55 50 37 36 32 30 28 25 15
         */
    }
}