树-java实现

树的概念

在客观世界中许多事物存层次关系,例如:

使用树这种结构的原因是因为层次管理具有更高的效率

树: N个节点构成的有限集合,含有一个称为根(Root)的特殊结点如上图的中国,其余的结点可分为若干个互不相交的树,称为原来结点的子树

基本术语

结点的度: 结点子树个数
树的度: 树中所有的节点中最大的度
叶结点: 度为0的结点
父结点: 有子树的结点是其子树的根节点的父结点
子结点: 若A是B的父结点,B就是A的子结点
结点的层次:根节点为1层子结点的层数是父结点层数+1
树的高度: 树中所有结点的最大层次就是这棵树的高度

注: 子树是不相交的除根结点外,每个结点有且只有一个父结点,一个N结点的树只有N-1条边

二叉树

树的度为2的树,且子树有左右之分

二叉树的应用

编码问题:

给定一段文本对字符串编码使其编码存储空间最少

设一段文本包含58个字符,由一下7个字符构成:

等长ASCII编码: 58 * 8 = 464位
等长3位编码: 58 * 3 = 174位
不等长编码: 10* 3+15 * 2+12 * 2+3 * 5+4 * 4+13 * 2+1*5 = 146位

不等长编码：出现频次高的字符用的编码短些，出现频次低的编码长些

使用二叉树进行编码:
二叉树分支 :0,1,为了避免二义性字符只在叶节点上

哈夫曼树的构造

构造一颗二叉树,该树的带权路径长度达到最小称为最优二叉树也就是哈夫曼树

构造方式:

每次把权重最小的两棵二叉树合并
左节点权值比右节点小

解决上述编码问题

具体代码实现

package 树;

import java.util.ArrayList;
import java.util.List;


public class HuffmanTree {
    
    public static class Node{
        //数据,权重,左右子节点
       private T data;
       private int weight;
       private Node leftChild;
        private Node rightChild;

        public Node(T data,int weight){
            super();
            this.data = data;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Node["+weight+","+"data="+data+"]";
        }
    }

    
    private static Node createTree(List nodes) {
        //判断节点node列表中是否含有2哥及2个以上的节点
        while (nodes.size() > 1) {
            //将list排序按照权重增序方式进行排序,找到最小的
            sort(nodes);
            //左边比右边小
            Node left = nodes.get(0);
            Node right = nodes.get(1);
            //生成一个新的节点,父结点权重为两个子结点之和,
            Node parent = new Node(null, left.weight + right.weight);
            //让子结点与父结点连接
            parent.leftChild = left;
            parent.rightChild = right;
            //删除最小的
            nodes.remove(0);
            //删除第二小的
            nodes.remove(0);
            nodes.add(parent);

        }
        return nodes.get(0);
    }

    
    public static void sort(List nodes) {
        if (nodes.size() <= 1){
            return ;
        }
        
        for (int i = 0; i < nodes.size(); i++){
            
            for (int j = 0; j < nodes.size() - 1 - i; j++){
                
                if (nodes.get(j + 1).weight < nodes.get(j).weight) {
                    Node temp = nodes.get(j + 1);
                    nodes.set(j+1,nodes.get(j));
                    nodes.set(j,temp);
                }
            }
        }
        return ;
    }

    

    public static void printTree(Node root) {
        System.out.println(root.toString());
        if(root.leftChild !=null){
            System.out.print("left:");
            printTree(root.leftChild);
        }
        if(root.rightChild !=null){
            System.out.print("right:");
            printTree(root.rightChild);
        }
    }

    
    public static void main(String[] args) {
        List nodes = new ArrayList();
        //把节点加入至list中
        nodes.add(new Node("a", 10));
        nodes.add(new Node("b", 15));
        nodes.add(new Node("c", 12));
        nodes.add(new Node("d", 3));
        nodes.add(new Node("e", 4));
        nodes.add(new Node("f", 13));
        nodes.add(new Node("g", 1));
        //进行哈夫曼树的构造
        Node root = HuffmanTree.createTree(nodes);
        //打印哈夫曼树
        printTree(root);
    }
}

二叉排序树定义

左子树的所有的值小于根节点的值
右子树的所有的值大于根节点的值
左右子树满足以上两点

Find

查找的值x从根节点开始

如果x小于根节点的值,则在左子树中继续查找
如果x大于根节点的值,则在右子树中继续查找
如果x等于根节点的值则返回该节点
查不到就返回null

查找的效率决定于树的高度,最大元素在树的最右支的节点,最小元素在树的最左支的节点上

Insert

插入的值从根节点开始查找

如果x小于根节点的值,则在左子树中继续查找
如果x大于根节点的值,则在右子树中继续查找
如果该节点是叶节点,x小于该节点值则插入左子节点,否则插入右节点

delete

插入的值从根节点开始查找

如果该节点的值为x则删除
如果x小于根节点的值,则在左子树中继续查找
如果x大于根节点的值,则在右子树中继续查找

AVL树

他是一颗二叉排列树,左右2个子树的高度差(平衡因子)的绝对值
不超过1,且左右2个子树都是一颗平衡二叉树

目的: 使得树的高度最低,因为树查找的效率决定于树的高度

二叉平衡树的调整

调整原则根据插入的节点和失衡节点的位置上关系来划分

LL旋转
插入节点在失衡结点的左子树的左边,需要经过一次左旋转即可达到平衡
RR旋转
插入节点在失衡结点的右子树的右边,需要经过一次右旋转即可达到平衡
LR旋转
插入的节点在失衡节点的左子树的右边,失衡节点的左子树先做RR旋转,失衡节点再做LL旋转
RL旋转
插入的节点在失衡节点的右子树的左边,失衡节点的右子树先做LL旋转,失衡节点再做RR旋转

代码实现

package 树;


public class AVLTree {
    //节点
    public static class Node {
        //数据,左子节点,右子节点,记录该节点所在的高度
        int data;
        Node leftChild;
        Node rightChild;
        int height;

        public Node(int data) {
            this.data = data;
        }
    }

    
    public static int getHeight(Node p){
        //空树高度为-1
        return p==null?-1:p.height;
    }

    
    public static void printTree(Node root) {
        System.out.println(root.data);
        if(root.leftChild !=null){
            System.out.print("left:");
            printTree(root.leftChild);
        }
        if(root.rightChild !=null){
            System.out.print("right:");
            printTree(root.rightChild);
        }
    }

    
    public static Node insert(Node root,int data){
        if(root==null){
            root = new Node(data);
            return root;
        }
        if (data<= root.data){
            //插入到其左子树上
            root.leftChild = insert(root.leftChild,data);
            //平衡调整---高度差大于1
            if(getHeight(root.leftChild)-getHeight(root.rightChild)>1){
                //插入的节点在失衡节点的左子树的左边
                if (data<=root.leftChild.data){
                    System.out.println("LL旋转");
                    //LL旋转调整
                    root = LLRotate(root);
                    //插入的节点在失衡节点的左子树的右边
                }else{
                    System.out.println("LR旋转");
                    //LR旋转调整
                    root = LRRotate(root);
                }
            }
            //插入到右子树上
        }else{
            root.rightChild = insert(root.rightChild,data);
            //平衡调整
            if(getHeight(root.leftChild)-getHeight(root.rightChild)>1) {
                //插入节点在失衡结点的右子树的左边
                if (data <= root.rightChild.data) {
                    System.out.println("RL旋转");
                    root = RLRotate(root);
                    //插入节点在失衡结点的右子树的右边
                } else {
                    System.out.println("RR旋转");
                    root = RRRotate(root);
                }
            }
        }
        //重新调整root节点的高度值
        root.height = Math.max(getHeight(root.leftChild),getHeight(root.rightChild))+1;
        return root;
    }


    
    public static Node LLRotate(Node p){
        //失衡点的左子树的根节点作为新节点
        Node LsubTree = p.leftChild;
        //将新节点的右子树25作为失衡点30的左子树
        p.leftChild = LsubTree.rightChild;
        //将失衡点30作为新节点的右子树
        LsubTree.rightChild = p;
        //重新设置失衡点和新节点的高度
        p.height = Math.max(getHeight(p.rightChild),getHeight(p.leftChild))+1;
        LsubTree.height = Math.max(getHeight(LsubTree.leftChild),p.height)+1;
        //新的节点取代原失衡点
        return LsubTree;
    }

    
    public static Node RRRotate(Node p){
        //失衡点的右子树的根节点作为新节点
        Node RsubTree = p.rightChild;
        //将新节点的左子树25作为失衡点20的右子树
        p.rightChild = RsubTree.leftChild;
        //将失衡点20作为新节点的左子树
        RsubTree.leftChild = p;
        //重新设置失衡点和新节点的高度
        p.height = Math.max(getHeight(p.rightChild),getHeight(p.leftChild))+1;
        RsubTree.height = Math.max(getHeight(RsubTree.rightChild),getHeight(RsubTree.leftChild))+1;
        //新的节点取代原失衡点
        return RsubTree;
    }

    
    public static Node RLRotate(Node p){
        // 先将失衡点p的右子树进行LL平衡旋转
        p.rightChild = LLRotate(p.rightChild);
        //再将失衡点p进行RR平衡点旋转返回新节点代替原失衡点p
        return RRRotate(p);
    }

    
    public static Node LRRotate(Node p){
        // 先将失衡点p的左子树进行RR旋转
        p.leftChild = RRRotate(p.leftChild);
        // 再将失衡点p进行LL平衡旋转并返回新节点代替原失衡点p
        return LLRotate(p);
    }

    
    public static void main(String[] args) {
        Node root = null;
        root = insert(root,30);
        root = insert(root,20);
        root = insert(root,40);
        root = insert(root,10);
        root = insert(root,25);
        //插入节点在失衡结点的左子树的左边
        root = insert(root,5);
        //打印树，按照先打印左子树，再打印右子树的方式
        printTree(root);

    }
}

测试结果:

红黑树

一种特殊的二叉查找树,拥有以下特征

节点非红即黑
根节点和Null节点是黑色的
所有Null节点称为叶节点,且颜色为黑色
所有红色节点的子结点都是黑色
从任意节点到其叶节点的所有路径都包含相同数目的黑色节点
从根节点到叶节点的最长路径不多于最短的可能路径的2倍

插入

插入原则:因为插入节点的颜色为黑色的话那么久破坏了红黑树的性质,所以每次插入的点首先都是红节点

情况一:插入的新节点N位于树的根上,插入的新节点的父结点是黑色的

变色

叔父节点来指新节点的父节点的兄弟节点、祖父节点新节点的父节点的父节点

情况二: 如果新节点的父结点和叔父节点都是红色节点,先插入新节点(红色),新节点的父结点,叔父节点和祖父节点都要变色
的
情况三:如果新节点父结点是红色同时叔父节点是黑色,同时新节点是其父结点的左子节点,而父结点是祖父节点的左子节点,这时要进行一次右旋转调整新节点和其父节点的角色(以父结点为轴)

这里因为根节点是红色所以进行了一次变色,为了满足红黑树的性质所以叔父节点也进行一次变色

情况四: 如果新节点的父结点是红色同时叔父节点都是黑色,新节点是其父节点的右子节点而父结点是祖父节点的右子节点,此时需要对祖父节点进行一次左旋转(以父结点为轴)

这里变色与上述同理

情况五: 如果新节点的父节点是红色同时叔父节点都是黑色，同时新节点是其父节点的右子节点而父节点又是其父节点的左子节点。进行一次左旋转调换新节点和其父节点的角色（第一次旋转），同时发现节点符合情况3，再进行一次右旋转（第二次旋转）

情况六: 如果新节点的父结点是红色同时叔父节点是黑色,同时新节点是其父节点的左子节点而父节点是祖父节点的右子节点,这是要进行一次右旋转变成情况四,在进行一次左旋转

代码实现

package 树;


public class RBTree> {
    //根节点
    private RBTNode mRoot;
    //设置红色为false
    private static final boolean RED = false;
    //设置黑色是true
    private static final boolean BLACK = true;

   public class RBTNode>{
       //颜色,键值,左孩子,右孩子,父结点
       boolean color;
       T key;
       RBTNode left;
       RBTNode right;
       RBTNode parent;

       public RBTNode(boolean color, T key, RBTNode left, RBTNode right, RBTNode parent) {
           this.color = color;
           this.key = key;
           this.left = left;
           this.right = right;
           this.parent = parent;
       }
       public T getKey() {
           return key;
       }

       @Override
       public String toString() {
           return ""+key+(this.color==RED?"(R)":"B");
       }
   }

    public RBTree() {
        mRoot=null;
    }

    private RBTNode parentOf(RBTNode node) {
        return node!=null ? node.parent : null;
    }
    private boolean colorOf(RBTNode node) {
        return node!=null ? node.color : BLACK;
    }
    private boolean isRed(RBTNode node) {
        return ((node!=null)&&(node.color==RED)) ? true : false;
    }
    private boolean isBlack(RBTNode node) {
        return !isRed(node);
    }
    private void setBlack(RBTNode node) {
        if (node!=null) {
            node.color = BLACK;
        }
    }
    private void setRed(RBTNode node) {
        if (node!=null) {
            node.color = RED;
        }
    }
    private void setParent(RBTNode node, RBTNode parent) {
        if (node!=null) {
            node.parent = parent;
        }
    }
    private void setColor(RBTNode node, boolean color) {
        if (node!=null) {
            node.color = color;
        }
    }

    
    private RBTNode search(RBTNode x,T key){
       if (x==null){
           return x;
       }
       int cmp = key.compareTo(x.key);
       //小于则去左子树找,大于则去右子树找
       if (cmp<0){
           return search(x.left,key);
       }else if (cmp>0){
           return search(x.right,key);
       }else{
           return x;
       }
    }

    
    private RBTNode minNum(RBTNode tree){
        if (tree== null){
            return null;
        }
        //在左子树上找
        while (tree.left!=null){
            tree = tree.left;
        }
        return tree;
    }

    
    public T miniNum(){
        RBTNode p = minNum(mRoot);
        if (p!=null){
            return p.key;
        }
        return null;
    }

    
    private RBTNode maxiNum(RBTNode tree) {
        if (tree == null) {
            return null;
        }

        while(tree.right != null) {
            tree = tree.right;
        }
        return tree;
    }

    public T maxiNum() {
        RBTNode p = maxiNum(mRoot);
        if (p != null) {
            return p.key;
        }

        return null;
    }

    
    public RBTNode successor(RBTNode x){
        //如果存在右孩子,则x的后继节点为以其右孩子为根的子树的最小节点
        if (x.right!=null){
            return minNum(x.right);
        }

        //如果没有右孩子,则x有一下2种可能:
        // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
        // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
        RBTNode y = x.parent;
        while ((y!=null) && (x==y.right)) {
            x = y;
            y = y.parent;
        }

        return y;
    }

    
    public RBTNode predecessor(RBTNode x) {
        // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
        if (x.left != null) {
            return maxiNum(x.left);
        }

        // 如果x没有左孩子。则x有以下两种可能：
        // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
        // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
        RBTNode y = x.parent;
        while ((y!=null) && (x==y.left)) {
            x = y;
            y = y.parent;
        }

        return y;
    }

    
    private void leftRotate(RBTNode x){
        //设置右孩子为y(17)
        RBTNode y = x.right;
        //将y的左孩子设置为x右孩子
        //如果y的左孩子非空,将x设置为y的左孩子的父亲
        x.right = y.left;
        if (y.left!=null){
            y.left.parent = x;
        }
        //x的父亲设为y的父亲
        y.parent = x.parent;

        // 如果 “x的父亲” 是空节点，则将y设为根节点
        if (x.parent == null) {
            this.mRoot = y;
        } else {
            // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
            if (x.parent.left == x) {
                x.parent.left = y;
            } else {
                // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
                x.parent.right = y;
            }
        }
        // 将 “x” 设为 “y的左孩子”
        y.left = x;
        // 将 “x的父节点” 设为 “y”
        x.parent = y;
    }

    
    private void rightRotate(RBTNode y){
        //设置x为当前节点的左孩子
        RBTNode x = y.left;
        // 将 “x的右孩子” 设为 “y的左孩子”；
        // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
        y.left = x.right;
        if (x.right != null) {
            x.right.parent = y;
        }

        // 将 “y的父亲” 设为 “x的父亲”
        x.parent = y.parent;

        if (y.parent == null) {
            // 如果 “y的父亲” 是空节点，则将x设为根节点
            this.mRoot = x;
        } else {
            if (y == y.parent.right) {
                // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
                y.parent.right = x;
            } else {
                // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
                y.parent.left = x;
            }
        }

        // 将 “y” 设为 “x的右孩子”
        x.right = y;

        // 将 “y的父节点” 设为 “x”
        y.parent = x;
    }

    
    private void insertFixUp(RBTNode node){
        RBTNode parent,gparent;
        //若父结点存在,且父节点的颜色是红色的
        while (((parent = parentOf(node))!=null)&&isRed(parent)){
            //祖父节点
            gparent = parentOf(parent);
            //若父结点是祖父节点的左孩子
            if (parent==gparent.left){
                RBTNode uncle = gparent.right;
                //情况二:叔叔节点是红色的
                if (uncle!=null&&isRed(uncle)){
                    setBlack(uncle);
                    setBlack(parent);
                    setRed(gparent);
                    node = gparent;
                    continue;
                }

                //情况五:叔叔是黑色的,当前节点是右孩子(两次旋转,先左后右)
                if (parent.right == node){
                    RBTNode temp;
                    //左旋转
                    leftRotate(parent);
                    temp = parent;
                    parent = node;
                    node = temp;
                }

                //情况三:叔叔是黑色的,当前节点是左孩子(一次右旋转)
                setBlack(parent);
                setRed(gparent);
                rightRotate(gparent);
            }else {
                //父结点是祖父节点的右孩子
                RBTNode uncle = gparent.left;
                // 情况2：叔叔节点是红色
                if ((uncle!=null) && isRed(uncle)) {
                    setBlack(uncle);
                    setBlack(parent);
                    setRed(gparent);
                    node = gparent;
                    continue;
                }

                //情况六:叔叔是黑色的,当且节点是左孩子(先右后左)
                if (parent.left==node){
                    RBTNode temp;
                    rightRotate(parent);
                    temp = parent;
                    parent = node;
                    node = temp;
                }

                //情况四:叔叔是黑色的,当前节点是右孩子(一次左旋)
                setBlack(parent);
                setRed(gparent);
                leftRotate(gparent);
            }
        }
        //将根节点设为黑色
        setBlack(this.mRoot);
    }

    
    private void insert(RBTNode node){
        int cmp;
        RBTNode y = null;
        RBTNode x = this.mRoot;

        // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
        while (x != null) {
            y = x;
            cmp = node.key.compareTo(x.key);
            if (cmp < 0) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        node.parent = y;
        if (y!=null) {
            cmp = node.key.compareTo(y.key);
            if (cmp < 0) {
                y.left = node;
            } else {
                y.right = node;
            }
        } else {
            this.mRoot = node;
        }
        // 2. 设置节点的颜色为红色
        node.color = RED;
        // 3. 将它重新修正为一颗二叉查找树
        insertFixUp(node);
    }

    
    public void insert(T key){
        RBTNode node = new RBTNode(BLACK,key,null,null,null);
        // 如果新建结点失败，则返回。
        if (node != null) {
            insert(node);
        }
    }

    
    private void removeFixUp(RBTNode node, RBTNode parent) {
        RBTNode other;

        while ((node==null || isBlack(node)) && (node != this.mRoot)) {
            if (parent.left == node) {
                other = parent.right;
                if (isRed(other)) {
                    // Case 1: x的兄弟w是红色的
                    setBlack(other);
                    setRed(parent);
                    leftRotate(parent);
                    other = parent.right;
                }

                if ((other.left==null || isBlack(other.left)) &&
                        (other.right==null || isBlack(other.right))) {
                    // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
                    setRed(other);
                    node = parent;
                    parent = parentOf(node);
                } else {

                    if (other.right==null || isBlack(other.right)) {
                        // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
                        setBlack(other.left);
                        setRed(other);
                        rightRotate(other);
                        other = parent.right;
                    }
                    // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
                    setColor(other, colorOf(parent));
                    setBlack(parent);
                    setBlack(other.right);
                    leftRotate(parent);
                    node = this.mRoot;
                    break;
                }
            } else {

                other = parent.left;
                if (isRed(other)) {
                    // Case 1: x的兄弟w是红色的
                    setBlack(other);
                    setRed(parent);
                    rightRotate(parent);
                    other = parent.left;
                }

                if ((other.left==null || isBlack(other.left)) &&
                        (other.right==null || isBlack(other.right))) {
                    // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
                    setRed(other);
                    node = parent;
                    parent = parentOf(node);
                } else {

                    if (other.left==null || isBlack(other.left)) {
                        // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
                        setBlack(other.right);
                        setRed(other);
                        leftRotate(other);
                        other = parent.left;
                    }

                    // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
                    setColor(other, colorOf(parent));
                    setBlack(parent);
                    setBlack(other.left);
                    rightRotate(parent);
                    node = this.mRoot;
                    break;
                }
            }
        }

        if (node!=null) {
            setBlack(node);
        }
        
    }

    
    private void remove(RBTNode node) {
        RBTNode child, parent;
        boolean color;

        // 被删除节点的"左右孩子都不为空"的情况。
        if ( (node.left!=null) && (node.right!=null) ) {
            // 被删节点的后继节点。(称为"取代节点")
            // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
            RBTNode replace = node;

            // 获取后继节点
            replace = replace.right;
            while (replace.left != null) {
                replace = replace.left;
            }

            // "node节点"不是根节点(只有根节点不存在父节点)
            if (parentOf(node)!=null) {
                if (parentOf(node).left == node) {
                    parentOf(node).left = replace;
                } else {
                    parentOf(node).right = replace;
                }
            } else {
                // "node节点"是根节点，更新根节点。
                this.mRoot = replace;
            }

            // child是"取代节点"的右孩子，也是需要"调整的节点"。
            // "取代节点"肯定不存在左孩子！因为它是一个后继节点。
            child = replace.right;
            parent = parentOf(replace);
            // 保存"取代节点"的颜色
            color = colorOf(replace);

            // "被删除节点"是"它的后继节点的父节点"
            if (parent == node) {
                parent = replace;
            } else {
                // child不为空
                if (child!=null) {
                    setParent(child, parent);
                }
                parent.left = child;

                replace.right = node.right;
                setParent(node.right, replace);
            }

            replace.parent = node.parent;
            replace.color = node.color;
            replace.left = node.left;
            node.left.parent = replace;

            if (color == BLACK) {
                removeFixUp(child, parent);
            }

            node = null;
            return ;
        }

        if (node.left !=null) {
            child = node.left;
        } else {
            child = node.right;
        }

        parent = node.parent;
        // 保存"取代节点"的颜色
        color = node.color;

        if (child!=null) {
            child.parent = parent;
        }

        // "node节点"不是根节点
        if (parent!=null) {
            if (parent.left == node) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        } else {
            this.mRoot = child;
        }

        if (color == BLACK) {
            removeFixUp(child, parent);
        }
        node = null;
    }

    
    public void remove(T key) {
        RBTNode node;

        if ((node = search(mRoot, key)) != null) {
            remove(node);
        }
    }

    
    private void destroy(RBTNode tree) {
        if (tree==null) {
            return ;
        }

        if (tree.left != null) {
            destroy(tree.left);
        }
        if (tree.right != null) {
            destroy(tree.right);
        }
        tree = null;
    }

    public void clear() {
        destroy(mRoot);
        mRoot = null;
    }

    
    private void print(RBTNode tree, T key, int direction) {

        if(tree != null) {

            if(direction==0){    // tree是根节点
                System.out.printf("%2d(B) is rootn", tree.key);
            } else{                // tree是分支节点
                System.out.printf("%2d(%s) is %2d's %6s childn", tree.key, isRed(tree)?"R":"B", key, direction==1?"right" : "left");
            }

            print(tree.left, tree.key, -1);
            print(tree.right,tree.key,  1);
        }
    }

    public void print() {
        if (mRoot != null) {
            print(mRoot, mRoot.key, 0);
        }
    }
    
    private void preOrder(RBTNode tree) {
        if(tree != null) {
            System.out.print(tree.key+" ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    public void preOrder() {
        preOrder(mRoot);
    }

    
    private void inOrder(RBTNode tree) {
        if(tree != null) {
            inOrder(tree.left);
            System.out.print(tree.key+" ");
            inOrder(tree.right);
        }
    }

    public void inOrder() {
        inOrder(mRoot);
    }


    
    private void postOrder(RBTNode tree) {
        if(tree != null)
        {
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.print(tree.key+" ");
        }
    }

    public void postOrder() {
        postOrder(mRoot);
    }

}

树-java实现

Java相关栏目本月热门文章