数据结构之二叉树的Java实现

树由边连接的节点构成。节点一般代表实体数据，如代表某一类数据。windows文件系统就可以看成是一棵树，比如C盘下有一些文件夹，这些文件夹下面又分别有一些文件夹，这样的关系其实就是一棵树。
根：树顶端的节点称为树的根，一棵树只有一个根。
父节点：每一个节点(除了根)都有一条边向上连接到另一个节点，上面的这个节点就称为下面节点的父节点。
子节点：与父节点相反。
子树：每个节点都可以作为子树的根，它和它所有的子节点，还有子节点的子节点都在子树中。
二叉树：如果树中每个节点最多有两个子节点，这样的树就称为二叉树。
二叉树的两个节点分别称为左子节点和右子节点。
Java中表示二叉树，可以用数组表示树，常用的方法是将节点存在无关联的容器中，再通过每个节点指向自己的子节点的引用来连接。

下面的方法用的就是后一种：

package test;
public class BinaryTree {
    static Node root;
    public Node find(int key) {
        Node current = root;// 从根节点开始,用current保存正在查看的节点
        while (current.idata != key) {
            if (key < current.idata)
                current = current.leftChild;
            else
                current = current.rightChild;
            if (current == null)
                return null;
        }
        return current;
    }
    public void insert(int key) {
        // 首先要找到插入的地方
        Node inode = new Node();
        inode.idata = key;// 赋值
        if (root == null)
            root = inode;// 空树，则作为根节点
        else {
            Node current = root;// 从根节点开始比对
            Node parent;
            while (true) {
                // 用parent来存储current,目的是在current变为空的时候，
                // 才知道current== null时对应的上一个节点(parent)没有子节点
                parent = current;
                if (key < current.idata) {
                    current = current.leftChild;
                    if (current == null) {
                        parent.leftChild = inode;
                        return;
                    }
                } else {
                    current = current.rightChild;
                    if (current == null) {
                        parent.rightChild = inode;
                        return;
                    }
                }
            }
        }
    }
    /**
     * 找到要删除的节点 有三种情况：1)该节点是页节点 ,2)该节点有一个子节点 ,3)该节点有两个子节点
     * (删除好复杂,于是可以这样:在每一个节点上添加一个字段isDelete,若需要删除,则置为true)
     */
    public boolean delete(int key) {
        Node current = root;
        Node parent = root;
        boolean isLeftChild = true;
        while (current.idata != key) {
            parent = current;
            if (key < current.idata) {
                isLeftChild = true;
                current = current.leftChild;
            } else {
                isLeftChild = false;
                current = current.rightChild;
            }
            if (current == null)
                return false;
        }// 找到了节点
         // 判断有无子节点
        if (current.leftChild == null && current.rightChild == null) {
            if (current == root)
                root = null;
            else if (isLeftChild)
                parent.leftChild = null;
            else
                parent.rightChild = null;
        } else if (current.rightChild == null) {
            if (current == root)
                root = current.leftChild;
            else if (isLeftChild)
                parent.leftChild = current.leftChild;
            else
                parent.rightChild = current.leftChild;
        } else if (current.leftChild == null) {
            if (current == root)
                root = current.rightChild;
            else if (isLeftChild)
                parent.leftChild = current.rightChild;
            else
                parent.rightChild = current.rightChild;
        }
        /**
         * 删除一个有两个子节点的节点，就不能用它的一个子节点来代替它，而要用它的中序后继代替该节点 如何找？
         * 首先，找到初始节点的右子节点rcn，然后转到rcn的左子节点(有的话)rcnl，然后转到rcnl的左子节点，直到结束。
         * 这里实际上要找的是比初始节点值大的集合中最小的那一个 如果初始节点的右子节点没有左子节点，那么其本身就是后继
         */
        else {
            Node success = getMidPostNode(current);
            if (current == root)
                root = success;
            else if (isLeftChild)
                parent.leftChild = success;
            else
                parent.rightChild = success;
            success.leftChild = current.leftChild;
        }
        return true;
    }
    // 获取当前节点的中序后继
    public Node getMidPostNode(Node delNode) {
        Node successParent = delNode;
        Node success = delNode;
        Node current = delNode.rightChild;
        while (current != null) {// 直到找到当前节点右子节点的最左子孙节点
            successParent = success;
            success = current;
            current = current.leftChild;
        }
        if (success != delNode.rightChild) {
            successParent.leftChild = success.rightChild;
            success.rightChild = delNode.rightChild;
        }
        return success;
    }
    // 前序遍历
    public void preTraverse(Node root) {
        if (root != null) {
            System.out.println(root.idata + " ");
            preTraverse(root.leftChild);
            preTraverse(root.rightChild);
        }
    }
    // 中序遍历
    public void midTraverse(Node root) {
        if (root != null) {
            midTraverse(root.leftChild);
            System.out.println(root.idata + " ");
            midTraverse(root.rightChild);
        }
    }
    // 后续遍历
    public void postTraverse(Node root) {
        if (root != null) {
            postTraverse(root.leftChild);
            postTraverse(root.rightChild);
            System.out.println(root.idata + " ");
        }
    }
    // 递归地交换二叉树的左右子节点
    public void swap(Node root) {
        if(root == null)
            return;
        Node tmp = root.leftChild;
        root.leftChild = root.rightChild;
        root.rightChild = tmp;
        swap(root.leftChild);
        swap(root.rightChild);
    }
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.insert(1);
        bt.insert(2);
        bt.insert(3);
        bt.insert(0);
        bt.insert(5);
// Node f = bt.find(2);
// System.out.println("find = " + f.idata);
// bt.delete(3);
// bt.preTraverse(root);
// System.out.println("----------");
// bt.midTraverse(root);
// System.out.println("----------");
// bt.postTraverse(root);
// System.out.println("---------->");
        bt.printBinaryTree(root, 0);
        bt.swap(root);
        bt.printBinaryTree(root, 0);
    }
    //递归打印树形二叉树
    public static void printBinaryTree(Node root, int level){
        if(root==null)
             return;
        printBinaryTree(root.rightChild, level+1);
        if(level!=0){
            for(int i=0;i<level-1;i++)
                System.out.print("|\t");
                System.out.println("|-------"+root.idata);
        }
        else
            System.out.println(root.idata);
        printBinaryTree(root.leftChild, level+1);
    }
    
}
class Node {
    int idata;
    Node leftChild;
    Node rightChild;
}