java - 二叉树 : printing the data in ascending order

Question

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

我创建了一个方法 print 并尝试使用以下值:

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 的节点，可以使用中序遍历的变体，其中中序遍历相反。

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<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));
    }
}