0

问题：给定一个预排序数组，将其变成二叉搜索树

                 7
           5          9
       3      6    8     10

解决方案：

步骤 1：将数组转换为 Stack

从堆栈中弹出的第一个元素是根。

将其与下一个元素进行比较，如果小于根值，则将其设为左子树，否则将其设为右子树

这是代码

public class reconstruct{
  public static void main(String[] args){

            Stack s = new Stack();
            Integer[] arr = {7,5,3,6,9,8,10};
            List<Integer> l = Arrays.asList(arr);


            for (int i=arr.length-1; i>=0;i--){
                s.push(arr[i]);
            }

            System.out.println(s);
            Node newone = CreateFromPreOrder(s);
            printInorder(newone);





public static Node CreateFromPreOrder(Stack preOrder) {

            if (!preOrder.isEmpty()) {
                //System.out.println("hel");

            int value = (int) preOrder.pop();




            Node root = new Node(value);
            if (!preOrder.isEmpty()){

            if((int)preOrder.peek()<value){
                root.left=CreateFromPreOrder(preOrder);
            }
            else 
                  root.right = CreateFromPreOrder(preOrder);

        }
            return root;
            }
            else return null;

            } 

public static void printInorder(Node root) {

            if (root!=null){
                printInorder(root.left);
                System.out.print(" " + root.data);
                printInorder(root.right);
            }
        }
    }

Output: [10, 8, 9, 6, 3, 5, 7] 3 6 8 10 9 5 7

输出不是预期的有序数组。我无法弄清楚上面的逻辑有什么问题。

4

2 回答 2

2

我没有详细阅读代码，但是从您的描述来看，以下陈述是错误的：

从堆栈中弹出的第一个元素是根。

将其与下一个元素进行比较，如果小于根值，则将其设为左子树，否则将其设为右子树

考虑以下情况：

     7
   5
 3

现在，我们插入 6。根据您的说法，树应该是这样的：

     7
   5
 3
  6

如果您将输入数组反之亦然，此时您将面临相同的情况：

     10
8
   9
  6

这不是有效的二叉搜索树。要完成这项工作，您需要遍历树备份并验证 BST 不变量。

如果要将树 1:1 重建为原始树，只需按照与数组中相同的顺序将节点添加到树中即可。由于预购结构，可以做到这一点。

于 2013-11-09T00:17:51.407 回答
0

缺陷在这部分：

if((int)preOrder.peek()<value){
    root.left=CreateFromPreOrder(preOrder);
}else{ 
    root.right = CreateFromPreOrder(preOrder);
}

else 子句是错误的。正如 Danstahr 解释的那样，您没有检查 BST 不变量。如果下一项大于当前节点的父项，则不会将其添加到此处的右侧。

所以这样的事情会起作用（伪代码是伪代码）：

public Node createTree(Parent,curNode, Stack){
    if(stack empty){
       return null;
    }

    if(Stack.peek().value<curNode.value){
        curNode.left=createTree(curNode,node made from stack.pop,Stack)
    }

    if(stack not empty and next stack item is less than my parent, or I have no parent){
        curNode.right=createTree(curNode,node made from stack.pop,Stack)    
    }

    return curNode;

}
于 2013-11-09T00:25:05.613 回答