二叉树：按升序打印数据

Question

我是java的初学者..我刚开始在线学习数据结构。我想按升序打印我添加到二叉树的值。我创建了一个方法 print 并尝试使用这些值：9,5,2,8,3它打印了这个输出并停止了2 , 3 ,8节点必须构造函数：构造函数 1public Node(int value){    this.Value=value;    isEmpty=false;    this.left=new Node();    this.right=new Node();}构造函数 2public 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) 

{ 

    if (node == null) 

        return; 

    /* first recur on left child */

    printInorder(node.left); 

    /* then print the data of node */

    if(!node.isEmpty){

        System.out.print(node.value+ " "); 

    }

    /* now recur on right child */

    printInorder(node.right); 

} 

时间复杂度：O(n)

如果树不是BST。您可以创建 List 并将树的值写入列表，然后按升序对列表进行排序。

List<Integer> treeValues = new ArrayList<Integer>();

List<Integer> treeToList(Node node){

    if (node == null) 

        return; 

    printInorder(node.left); 

    if(!node.isEmpty){

        treeValues.add(node.value); 

    }

    printInorder(node.right); 

}

void sortedTree(Node node){

    List<Integer> treeData = treeToList(node);

    Collections.sort(treeData);

    for(int i=0; i<treeData.size();i++ ){

        System.out.println(treeData.get(i));

    }

}