Java数据结构和算法--树(转)

(1)二叉树

class Tree {   
    class Node {   
        public long value;   
  
        public Node leftChild;   
  
        public Node rightChild;   
  
        public Node(long value) {   
            this.value = value;   
            leftChild = null;   
            rightChild = null;   
        }   
    }   
  
    public Node root;   
  
    public Tree() {   
        root = null;   
    }   
  
    // 向树中插入一个节点   
    public void insert(long value) {   
        Node newNode = new Node(value);   
        // 树是空的   
        if (root == null)   
            root = newNode;   
        else {   
            Node current = root;   
            Node parentNode;   
            while (true) {   
                parentNode = current;   
                if (value < current.value) {   
                    current = current.leftChild;   
                    // 要插入的节点为左孩子节点   
                    if (current == null) {   
                        parentNode.leftChild = newNode;   
                        return;   
                    }   
                } else {   
                    // 要插入的节点为右孩子节点   
                    current = current.rightChild;   
                    if (current == null) {   
                        parentNode.rightChild = newNode;   
                        return;   
                    }   
                }   
            }   
        }   
    }   
  
    // 先续遍历树中的所有节点   
    public void preOrder(Node currentRoot) {   
        if (currentRoot != null) {   
            System.out.print(currentRoot.value + " ");   
            preOrder(currentRoot.leftChild);   
            preOrder(currentRoot.rightChild);   
        }   
    }   
  
    // 中续遍历树中的所有节点   
    public void inOrder(Node currentNode) {   
        if (currentNode != null) {   
            inOrder(currentNode.leftChild);   
            System.out.print(currentNode.value + " ");   
            inOrder(currentNode.rightChild);   
        }   
    }   
  
    // 后续遍历树中的所有节点   
    public void postOrder(Node currentNode) {   
        if (currentNode != null) {   
            postOrder(currentNode.leftChild);   
            postOrder(currentNode.rightChild);   
            System.out.print(currentNode.value + " ");   
        }   
    }   
  
    public void traverse(int traverseType) {   
        switch (traverseType) {   
        case 1:   
            preOrder(root);   
            break;   
        case 2:   
            inOrder(root);   
            break;   
        case 3:   
            postOrder(root);   
            break;   
        default:   
            break;   
        }   
    }   
  
    // 依据树节点的值删除树中的一个节点   
    public boolean delete(int value) {   
        // 遍历树过程中的当前节点   
        Node current = root;   
        // 要删除节点的父节点   
        Node parent = root;   
        // 记录树的节点为左孩子节点或右孩子节点   
        boolean isLeftChild = true;   
        while (current.value != value) {   
            parent = current;   
            // 要删除的节点在当前节点的左子树里   
            if (value < current.value) {   
                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 == null)   
                root = current.leftChild;   
            // 要删除的节点为左孩子节点   
            else if (isLeftChild)   
                parent.leftChild = current.leftChild;   
            // 要删除的节点为右孩子节点   
            else  
                parent.rightChild = current.leftChild;   
        }   
        // 要删除的节点没有左孩子节点，有右孩子节点   
        else if (current.leftChild == null) {   
            // 要删除的节点为根节点   
            if (current == root)   
                root = root.rightChild;   
            // 要删除的节点为左孩子节点   
            else if (isLeftChild)   
                parent.leftChild = current.rightChild;   
            // 要删除的节点为右孩子节点   
            else  
                parent.rightChild = current.rightChild;   
        }   
        // 要删除的接节点既有左孩子节点又有右孩子节点   
        else {   
            Node successor = getSuccessor(current);   
            // 要删除的节点为根节点   
            if (current == root)   
                root = successor;   
            // 要删除的节点为左孩子节点   
            else if (isLeftChild)   
                parent.leftChild = successor;   
            // 要删除的节点为右孩子节点   
            else  
                parent.rightChild = successor;   
        }   
        return true;   
    }   
  
    // 找到要删除节点的替补节点   
    private Node getSuccessor(Node delNode) {   
        // 替补节点的父节点   
        Node successorParent = delNode;   
        // 删除节点的替补节点   
        Node successor = delNode;   
        Node current = delNode.rightChild;   
        while (current != null) {   
            // successorParent指向当前节点的上一个节点   
            successorParent = successor;   
            // successor变为当前节点   
            successor = current;   
            current = current.leftChild;   
        }   
        // 替补节点的右孩子节点不为空   
        if (successor != delNode.rightChild) {   
            successorParent.leftChild = successor.rightChild;   
            successor.rightChild = delNode.rightChild;   
        }   
        return successor;   
    }   
}   
  
public class TreeApp {   
    public static void main(String[] args) {   
        Tree tree = new Tree();   
        tree.insert(8);   
        tree.insert(50);   
        tree.insert(45);   
        tree.insert(21);   
        tree.insert(32);   
        tree.insert(18);   
        tree.insert(37);   
        tree.insert(64);   
        tree.insert(88);   
        tree.insert(5);   
        tree.insert(4);   
        tree.insert(7);   
  
        System.out.print("PreOrder : ");   
        tree.traverse(1);   
        System.out.println();   
  
        System.out.print("InOrder : ");   
        tree.traverse(2);   
        System.out.println();   
  
        System.out.print("PostOrder : ");   
        tree.traverse(3);   
        System.out.println();   
  
        System.out.println(tree.delete(7));   
  
        System.out.print("PreOrder : ");   
        tree.traverse(1);   
        System.out.println();   
  
        System.out.print("InOrder : ");   
        tree.traverse(2);   
        System.out.println();   
  
        System.out.print("PostOrder : ");   
        tree.traverse(3);   
        System.out.println();   
  
    }   
}

 

原文：http://yongsky.iteye.com/blog/130878