我是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; }
1 回答
Qyouu
TA貢獻1786條經驗 獲得超11個贊
要從 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));
}
}
添加回答
舉報
0/150
提交
取消