二叉树：按升序打印数据

Question

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

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

9,5,2,8,3

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

2 , 3 ,8

节点必须构造函数：

Constructor 1

public Node(int value){
    this.Value=value;
    isEmpty=false;
    this.left=new Node();
    this.right=new Node();
}

Constructor 2

public Node(){
   isEmpty=true; 
}

The Adding method :

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;

            }
        }
    }
}

The Print method

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。

Algorithm Inorder(tree) 1. Traverse the left subtree, i.e., call Inorder(left-subtree) 2. Visit the root. 3. Traverse the right subtree, i.e., call 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));
    }
}

二叉树：按升序打印数据

binary Tree: printing the data in ascending order

java

binary-tree