java - 如何从平衡二叉搜索树中按升序打印整数？

Question

这个程序从数组整数创建平衡二叉搜索树，然后按顺序打印值(X.left，X，X.right)。任何改进程序的建议表示赞赏。

值得一提的是，还有其他几种遍历 BST 的方法。例如 -预购 : X, X.left, X.right后序:X.left, X.right, X

注意 # 我最终在该程序用户的帮助下解决了这个问题。它需要更改 createMinimalBST 方法中的一些条件。

// we need to stop recursion there as one element exist
if (start == mid-1) {

}

// we need to stop recursion there as one element exist
if (end == mid+1) {

}

谢谢。

// import java.util.Arrays;
// import java.util.LinkedList;
import java.util.*; 

class Node {

    int key;

    Node leftChild;
    Node rightChild;

    Node(int key) {
        this.key = key;
    }

    Node() {
        // null constructor 
    }

    public String toString() {
        return "\n"+key+" ";
    }
}


public class BinaryTree {

    Node root;

    static int TWO_NODES_FOUND = 2;
    static int ONE_NODE_FOUND = 1;
    static int NO_NODES_FOUND = 0;

    BinaryTree (){
        root = null;
    }

    public void addNode(int key) {

        Node newNode = new Node(key);

        // If there is no root this becomes root
        if (root == null) {
            root = newNode;
        } 

        else {

            // Set root as the Node we will start
            // with as we traverse the tree

            Node focusNode = root;
            Node parent;

            while (true) {

                parent = focusNode;

                if (key < focusNode.key) {

                    focusNode = focusNode.leftChild;

                    if (focusNode == null) {

                        parent.leftChild = newNode;
                        return; // All Done
                    }
                } // end of if 

                else { 

                    focusNode = focusNode.rightChild;

                    if (focusNode == null) {

                        parent.rightChild = newNode;
                        return; 
                    }
                }
            }
        }
    }

    // get the height of binary tree 
    public int height(Node root) {

        if (root == null)
            return -1;

        Node focusNode = root; 
        int leftHeight = focusNode.leftChild != null ? height( focusNode.leftChild) : 0;
        int rightHeight = focusNode.rightChild != null ? height( focusNode.rightChild) : 0;
        return 1 + Math.max(leftHeight, rightHeight);
    }

    // METHODS FOR THE TREE TRAVERSAL

    // inOrderTraverseTree : i) X.left ii) X iii) X.right
    public void inOrderTraverseTree(Node focusNode) {

        if (focusNode != null) {

            inOrderTraverseTree(focusNode.leftChild);
            // System.out.println(focusNode);
            System.out.print( focusNode );
            inOrderTraverseTree(focusNode.rightChild);
        }
        // System.out.println();
    }

    // preOrderTraverseTree : i) X ii) X.left iii) X.right
    public void preorderTraverseTree(Node focusNode) {

        if (focusNode != null) {

            System.out.println(focusNode);
            preorderTraverseTree(focusNode.leftChild);
            preorderTraverseTree(focusNode.rightChild);

        }
    }

    // postOrderTraverseTree : i) X.left ii) X.right iii) X
    public void postOrderTraverseTree(Node focusNode) {

        if (focusNode != null) {

            preorderTraverseTree(focusNode.leftChild);
            preorderTraverseTree(focusNode.rightChild);
            System.out.println(focusNode);

        }
    }

    // get certain node from it's key
    public Node findNode(int key) {

        Node focusNode = root;

        while (focusNode.key != key) {

            if (key < focusNode.key) {

                focusNode = focusNode.leftChild;

            } else {

                focusNode = focusNode.rightChild;
            }

            if (focusNode == null)
                return null;
        }
        return focusNode;

    }


    public boolean remove(int key) {

        Node focusNode = root;
        Node parent = root;
        boolean isItALeftChild = true;


        // we will remove the focusNode 
        while (focusNode.key != key) {

            parent = focusNode;

            if (key < focusNode.key) {

                isItALeftChild = true;
                focusNode = focusNode.leftChild;
            } 

            else {

                isItALeftChild = false;
                focusNode = focusNode.rightChild;
            }

            if (focusNode == null)
                return false;
        }

        // no child 
        if (focusNode.leftChild == null && focusNode.rightChild == null) {

            if (focusNode == root)
                root = null;

            else if (isItALeftChild)
                parent.leftChild = null;

            else
                parent.rightChild = null;
        }

        // one child ( left child )
        else if (focusNode.rightChild == null) {

            if (focusNode == root)
                root = focusNode.leftChild;

            else if (isItALeftChild)
                parent.leftChild = focusNode.leftChild;

            else
                parent.rightChild = focusNode.leftChild;
        }


        else if (focusNode.leftChild == null) {

            if (focusNode == root)
                root = focusNode.rightChild;

            else if (isItALeftChild)
                parent.leftChild = focusNode.rightChild;

            else
                parent.rightChild = focusNode.rightChild;

        }

        // two children exits 
        else {

            // replacement is the smallest node in the right subtree 
            // we neeed to delete the focusNode 
            Node replacement = getReplacementNode(focusNode);

            if (focusNode == root)
                root = replacement;

            else if (isItALeftChild)
                parent.leftChild = replacement;

            else
                parent.rightChild = replacement;

            replacement.leftChild = focusNode.leftChild;
        }

        return true;
    }



    public Node getReplacementNode(Node replacedNode) {

        Node replacementParent = replacedNode;
        Node replacement = replacedNode;
        Node focusNode = replacedNode.rightChild;

        // find the smallest node of the right subtree of the node to be deleted 
        while (focusNode != null) {

            replacementParent = replacement;
            replacement = focusNode;
            focusNode = focusNode.leftChild;
        }

        // exit when the focusNode is null
        // the replacement is the smallest of the right subtree

        if (replacement != replacedNode.rightChild) {

            replacementParent.leftChild = replacement.rightChild;
            replacement.rightChild = replacedNode.rightChild;
        }

        return replacement;
    }


    private  void createMinimalBST(int arr[], int start, int end, Node newNode){

        if ( end <= start ) return;

        int mid = (start + end) / 2;
        newNode.key = arr[mid];

        // System.out.println("new node = "+ newNode );

         if (start <= mid-1) {
            if ( start < mid-1){
                newNode.leftChild = new Node();
                createMinimalBST( arr, start, mid - 1, newNode.leftChild );
            }
            else {
                newNode.leftChild = new Node();
                newNode.leftChild.key = arr[start];
            }
        }

        if ( mid+1 <= end ) {

            if ( mid+1 < end){

                newNode.rightChild = new Node();
                createMinimalBST(arr, mid + 1, end, newNode.rightChild); 
            }

            else {
                newNode.rightChild = new Node();
                newNode.rightChild.key = arr[end];
            }
        }

        // System.out.println("left child = "+ newNode.leftChild +" "+ " right child = "+ newNode.rightChild);        

    } 

    public static int getHeight(Node root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.leftChild), getHeight(root.rightChild)) + 1;
    }

    public static boolean isBalanced( Node root) {
        if (root == null) {
            return true;
        }
        int heightDiff = getHeight(root.leftChild) - getHeight(root.rightChild);

        if (Math.abs(heightDiff) > 1) {
            return false;
        }
        else {
            return isBalanced(root.leftChild ) && isBalanced(root.rightChild );
        }       
    }

    public void createMinimalBST(int array[]) {

        // Node n = new Node();
        Arrays.sort(array);
        root = new Node();
        createMinimalBST(array, 0, array.length - 1, root);
    }

    // create linked list of the same level of the tree
    public static ArrayList<LinkedList<Node>> createLevelLinkedList( Node root) {

        ArrayList<LinkedList<Node>> result = new ArrayList<LinkedList<Node>>();

        /* "Visit" the root */
        LinkedList<Node> current = new LinkedList<Node>();

        if ( root != null) {
            current.add(root);
        }

        while ( current.size() > 0) {

            result.add(current); // Add previous level
            LinkedList<Node> parents = current; // Go to next level

            current = new LinkedList<Node>(); 

            for ( Node parent : parents) {

                /* Visit the children */
                if (parent.leftChild != null) {
                    current.add(parent.leftChild);
                }

                if (parent.rightChild != null) {
                    current.add(parent.rightChild );
                }
            }   

        }

        return result;
    }

    // print values in the same level of the tree gradually 
    public static void printResult(ArrayList<LinkedList<Node>> result){

        int depth = 0;      

        for(LinkedList<Node> entry : result) {

            Iterator<Node> i = entry.listIterator();
            System.out.print("Link list at depth " + depth + ":");

            while(i.hasNext()){
                System.out.print(" " + ((Node)i.next()).key );
            }

            System.out.println();
            depth++;    
        }       
    }


    // using a key, check whether the node is inside of the BST or not 
    public boolean isBST (int n){

        if ( n == root.key ){
            return true;
        }

        else {

            Node focusNode = root;
            Node parent; 

            while( focusNode != null){

                parent = focusNode;

                if (focusNode != null){

                    if (n < focusNode.key){

                        focusNode = focusNode.leftChild;
                    }

                    else {

                        focusNode = focusNode.rightChild;

                    }
                }

                if ( focusNode != null &&   n == focusNode.key ){
                    return true;

                }
            }
        }
        return false;
    }


    // 
    public Node getNode (int n){

        if ( n == root.key ){
            return root;
        }

        else {

            Node focusNode = root;
            Node parent; 

            while( focusNode != null){

                parent = focusNode;

                if (focusNode != null){

                    if (n < focusNode.key){

                        focusNode = focusNode.leftChild;
                    }

                    else {

                        focusNode = focusNode.rightChild;

                    }
                }

                if ( focusNode != null &&   n == focusNode.key ){
                    return focusNode;

                }
            }
        }
        return null;
    }


    // get the parent of using the key of certain node 
    public Node getParent (int n){

        if ( !isBST (n)){
            return null;
        }

        if ( n == root.key ){
            return null;
        }

        else {

            Node focusNode = root;
            Node parent; 

            while( focusNode != null){

                parent = focusNode;

                if (focusNode != null){

                    if (n < focusNode.key){

                        focusNode = focusNode.leftChild;
                    }

                    else {

                        focusNode = focusNode.rightChild;

                    }
                }

                if ( focusNode != null && n == focusNode.key ){
                    return parent;
                }
            }
        }

        return null;
    }


    /* get in-order successive node of the certain node */
    public  Node inorderSucc( Node n) { 

        if (n == null) return null;

        // Found right children -> return left most node of right subtree
        if ( getParent(n.key)    == null || n.rightChild != null) { 
            return leftMostChild( n.rightChild ); 
        } 

        else { 

            Node q = n;
            Node x = getParent(q.key);

            // Go up until we’re on left instead of right
            while (x != null && x.leftChild != q) {
                q = x;
                x = getParent(x.key);
            }
            return x;
        }  
    } 

    /* get the left most/ smallest node of the sub tree of the certain node */
    public  Node leftMostChild( Node n) {

        if (n == null) {
            return null;
        }

        while (n.leftChild != null) {
            n = n.leftChild; 
        }
        return n; 
    }


    // SECOOND SOLUTION TO FIND OUT THE COMMON ANCESTOR OF TWO NODES 

    public static boolean covers2( Node root, Node p) { 

        if (root == null) return false;
        if (root == p) return true;
        return covers2(root.leftChild , p) || covers2(root.rightChild , p); 
    }

    public static Node commonAncestorHelper( Node root, Node p, Node q) {
        if (root == null) {
            return null;
        }
        boolean is_p_on_left = covers2(root.leftChild , p);
        boolean is_q_on_left = covers2(root.leftChild , q);
        if (is_p_on_left != is_q_on_left) { // Nodes are on different side
            return root;
        }

        // nodes are the same sides
        Node child_side = is_p_on_left ? root.leftChild : root.rightChild;
        return commonAncestorHelper(child_side, p, q);

    }

    public static Node commonAncestor2( Node root, Node p, Node q) {

        if (!covers2(root, p) || !covers2(root, q)) { // Error check - one node is not in tree
            return null;
        }
        return commonAncestorHelper(root, p, q);
    }
    // END OF THE SECOND SOLUTION 


    // FIRST SOLUTION TO FIND OUT THE COMMON ANCESTOR OF TWO NODES
      // Checks how many “special” nodes are located under this root
    public static int covers( Node root, Node p, Node q) {
        int ret = NO_NODES_FOUND;
        if (root == null) return ret;
        if (root == p || root == q) 
            ret += 1;
        ret += covers(root.leftChild , p, q);
        if(ret == TWO_NODES_FOUND) // Found p and q 
            return ret;
        return ret + covers(root.rightChild , p, q);
    }


    public static Node commonAncestor( Node root, Node p, Node q) {

        if (q == p && (root.leftChild == q || root.rightChild == q)) 
            return root;

        int nodesFromLeft = covers(root.leftChild, p, q); // Check left side

        if ( nodesFromLeft == TWO_NODES_FOUND ) {

            if(root.leftChild == p || root.leftChild == q) 
                return root.leftChild;
            else return commonAncestor(root.leftChild , p, q);
        } 

        else if (nodesFromLeft == ONE_NODE_FOUND) {

            if (root == p) return p;
            else if (root == q) return q;
        }

        int nodesFromRight = covers(root.rightChild, p, q); // Check right side

        if(nodesFromRight == TWO_NODES_FOUND) {

            if(root.rightChild == p || root.rightChild == q) 
                return root.rightChild;

            else return commonAncestor(root.rightChild , p, q);
        } 

        else if (nodesFromRight == ONE_NODE_FOUND) {
            if (root == p) return p;
            else if (root == q) return q;
        }

        if (nodesFromLeft == ONE_NODE_FOUND && 
            nodesFromRight == ONE_NODE_FOUND) return root;
        else return null;
    }
    // END OF THE FIRST SOLUTION 


    // METHODS FOR SUBTREE CHECK 
    // Check if T2 is subtree of T1     
    public static boolean containsTree( Node t1, Node t2) {
        if (t2 == null)
            return true; // The empty tree is a subtree of every tree.
        else
            return subTree(t1, t2);
    }


    /* Checks if the binary tree rooted at r1 contains the binary tree 
     * rooted at r2 as a subtree somewhere within it.
     */

    public static boolean subTree( Node r1, Node r2) {

        if (r1 == null)
            return false; // big tree empty & subtree still not found.
        if (r1.key == r2.key) {
            if (matchTree(r1,r2)) return true;
        }
        return (subTree(r1.leftChild , r2) || subTree(r1.rightChild , r2)); 
    }

    /* 
      Checks if the binary tree rooted at r1 contains the 
      binary tree rooted at r2 as a subtree starting at r1.
     */

    public static boolean matchTree( Node r1, Node r2) {

        if (r2 == null && r1 == null) 
            return true; // nothing left in the subtree
        if (r1 == null || r2 == null) 
            return false; //  big tree empty & subtree still not found
        if (r1.key != r2.key) 
            return false;  // data doesn’t match
        return (matchTree(r1.leftChild, r2.leftChild) && 
                matchTree(r1.rightChild , r2.rightChild ));
    }
    // END OF SUBTREE CHECK 


        /* Creates tree by mapping the array left to right, top to bottom. */
    public  Node createTreeFromArray(int[] array) {

        if (array.length > 0) {

            root = new Node(array[0]);
            java.util.Queue<Node> queue = new java.util.LinkedList<Node>();
            queue.add(root);
            boolean done = false;
            int i = 1;

            while (!done) {

                Node r = (Node) queue.element();

                if (r.leftChild == null) {

                    r.leftChild = new Node(array[i]);
                    i++;
                    queue.add(r.leftChild);
                } 

                else if (r.rightChild == null) {
                    r.rightChild = new Node(array[i]);
                    i++;
                    queue.add(r.rightChild );
                } 

                else {
                    queue.remove();
                }

                if (i == array.length)
                    done = true;
            }

            return root;
        } 

        else {
            return null;
        }
    }


    // ALGORITHM TO FIND ALL THE PATHS TO CERTAIN SUM VALUE 

    public static void findSum( Node node, int sum, int[] path, int level) {

        if (node == null) {
            return;
        }

        /* Insert current node into path */
        path[level] = node.key; 

        int t = 0;
        for (int i = level; i >= 0; i--){

            t += path[i];
            if (t == sum) {
                print(path, i, level);
            }
        }

        findSum( node.leftChild, sum, path, level + 1);
        findSum( node.rightChild , sum, path, level + 1);

        /* Remove current node from path. Not strictly necessary, since we would
         * ignore this value, but it's good practice.
         */
        path[level] = Integer.MIN_VALUE; 
    }

    public static int depth( Node node) {

        if (node == null) {
            return 0;
        } 

        else {
            return 1 + Math.max(depth(node.leftChild), depth(node.rightChild));
        }
    }

    public static void findSum( Node node, int sum) {

        int depth = depth(node);
        int[] path = new int[depth];
        findSum(node, sum, path, 0);
    }

    private static void print(int[] path, int start, int end) {
        for (int i = start; i <= end; i++) {
            System.out.print(path[i] + " ");
        }
        System.out.println();
    }

    // END PATH ALGORITHM 


    public static void main(String[] args) {

        int[] myArr = {5, 3, 1, 4, 8, 2, 6}; 
        // int[] myArr = { 10,32,63,44,115,66,7,18,999 }; // sortedArrayToBST
        BinaryTree myTr = new BinaryTree();

        for( int j=0; j < myArr.length; j++){
            myTr.addNode(myArr[j]);
        }

        // Node n = BinaryTree.createMinimalBST(myArr);

        /*question 4-3
        create a binary tree with minimal height ( balanced tree )*/
        /*myTr.createMinimalBST(myArr);*/

        // System.out.println("The root is = "+myTr.root);
        myTr.inOrderTraverseTree(myTr.root);

        System.out.println("\n\n");

        /*get the height of the binary search tree*/
        /*System.out.println( "the height of the tree is = "+myTr.height(myTr.root));
        System.out.println("\n\n");*/

        /*question 4-1
        check whether the tree is balanced */

        /*boolean isBalanced = myTr.isBalanced(myTr.root);
        if (isBalanced) {
            System.out.println("The tree is balanced \n\n");
        }*/

        /*question 4-4
        create a linked list of all the nodes in the same level of the BST
        breadth first search ( BFS ) is used for implementation */ 

        /*ArrayList<LinkedList<Node>> list = createLevelLinkedList(myTr.root);
        printResult(list);*/

        /* ge parent of the elements */
        /*
        for(int j = 0; j < myArr.length ; j++){
            int checkParent = myArr[j];
            System.out.println("the parent of "+ checkParent +"  is = "+ myTr.getParent( checkParent) );
        }
        */      

        // using an integer value, get the node that contains that int element 
        /*Node myNode = myTr.getNode(44);
        System.out.println("Get my node = "+ myNode.key );  */

        /* get in-order successive node of certain node */
        /*int getInOrderSuccessive = 44 ;
        System.out.println( myTr.inorderSucc( myTr.getNode( getInOrderSuccessive)) );*/



        /* question 4-6 
        get the first common ancestor of two nodes */

        /*int firstNodeInteger = 7;
        int secondNodeInteger = 66;
        // try the first solution 
        System.out.println( myTr.commonAncestor( myTr.root, myTr.getNode(firstNodeInteger), myTr.getNode(secondNodeInteger) ));
        // try the second solution 
        System.out.println( myTr.commonAncestor2( myTr.root, myTr.getNode(firstNodeInteger), myTr.getNode(secondNodeInteger) ));
        */


        /* question 4-7 */
        /* check whether one tree is sub-set of the another tree */
        /*      
        int[] array1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
        int[] array2 = {2, 4, 5, 8, 9, 10, 11};

        Node t1 = myTr.createTreeFromArray(array1);
        Node t2 = myTr.createTreeFromArray(array2);

        if (containsTree(t1, t2))
            System.out.println("t2 is a subtree of t1");
        else
            System.out.println("t2 is not a subtree of t1");


        int[] array3 = {1, 2, 3};
        Node t3 = myTr.createTreeFromArray(array1);
        Node t4 = myTr.createTreeFromArray(array3);

        if (containsTree(t3, t4))
            System.out.println("t4 is a subtree of t3");
        else
            System.out.println("t4 is not a subtree of t3");
        */

        /*  question 4-8 
        algorithm to get all the paths equal to given value */

        /*int testValue  = 7;
        myTr.findSum( myTr.root, testValue );*/

    }

}

Answer 1

只需在 bbst() 方法中使用 root 而不是声明 n。

public void bbst(int array[]) {

    root = new TreeNode();
    balancedBST(array, 0, array.length - 1, root);
}