二叉树：按升序打印数据

Question

我是java的初学者..我刚开始在线学习数据结构。我想按升序打印我添加到二叉树的值。

我创建了一个方法 print 并尝试使用这些值：

9,5,2,8,3

它打印了这个输出并停止了

2 , 3 ,8

节点必须构造函数：

构造函数 1

public Node(int value){

    this.Value=value;

    isEmpty=false;

    this.left=new Node();

    this.right=new Node();

}

构造函数 2

public Node(){

   isEmpty=true; 

}

添加方法：

public void add(int value) {

    if (Objects.isNull(root)) {

        root = new Node(value);

        root.isEmpty = false;

    }

    Node current = root;

    while (true) {

        if (value < current.Value) {

            if (current.left.isEmpty) {

                current.left.prev = current;

                current = current.left;

                current.Value = value;

                current.isEmpty = false;

                current.left = new Node();

                current.right = new Node();

                break;

            } else {

                current = current.left;

            }

        } else {

            if (current.right.isEmpty) {

                current.right.prev = current;

                current = current.right;

                current.Value = value;

                current.isEmpty = false;

                current.left = new Node();

                current.right = new Node();

                break;

            } else {

                current = current.right;

            }

        }

    }

}

打印方法

ArrayList<Node> list = new ArrayList();

Node current = root;while(true){

 if(!current.left.isEmpty ){

     if(!list.contains(current.left)){

     current=current.left;

     continue;

     }

 } else {

     System.out.println(current.Value);

     list.add(current);

     if(!current.right.isEmpty && !list.contains(current.right)){

       current=current.right;

       continue;

     }

     current=current.prev.prev;

 } 

Answer 1

要从 BST 打印数据，您需要进行顺序遍历。在二叉搜索树 (BST) 的情况下，中序遍历以非递减顺序给出节点。要以非递增顺序获取 BST 的节点，可以使用 Inorder 遍历的变体，其中可以使用 Inorder 遍历 s reversed。算法 Inorder(tree) 1.遍历左子树，即调用Inorder(left-subtree) 2.访问根。3.遍历右子树，即调用Inorder(right-subtree)/* Given a binary tree, print its nodes in inorder*/void printInorder(Node node)&nbsp;{&nbsp;&nbsp; &nbsp; if (node == null)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp;&nbsp; &nbsp; /* first recur on left child */&nbsp; &nbsp; printInorder(node.left);&nbsp;&nbsp; &nbsp; /* then print the data of node */&nbsp; &nbsp; if(!node.isEmpty){&nbsp; &nbsp; &nbsp; &nbsp; System.out.print(node.value+ " ");&nbsp;&nbsp; &nbsp; }&nbsp; &nbsp; /* now recur on right child */&nbsp; &nbsp; printInorder(node.right);&nbsp;}&nbsp;时间复杂度：O(n)如果树不是BST。您可以创建 List 并将树的值写入列表，然后按升序对列表进行排序。List<Integer> treeValues = new ArrayList<Integer>();List<Integer> treeToList(Node node){&nbsp; &nbsp; if (node == null)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp;&nbsp; &nbsp; printInorder(node.left);&nbsp;&nbsp; &nbsp; if(!node.isEmpty){&nbsp; &nbsp; &nbsp; &nbsp; treeValues.add(node.value);&nbsp;&nbsp; &nbsp; }&nbsp; &nbsp; printInorder(node.right);&nbsp;}void sortedTree(Node node){&nbsp; &nbsp; List<Integer> treeData = treeToList(node);&nbsp; &nbsp; Collections.sort(treeData);&nbsp; &nbsp; for(int i=0; i<treeData.size();i++ ){&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(treeData.get(i));&nbsp; &nbsp; }}