我是java的初學(xué)者..我剛開始在線學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)。我想按升序打印我添加到二叉樹的值。我創(chuàng)建了一個方法 print 并嘗試使用這些值：9,5,2,8,3它打印了這個輸出并停止了2 , 3 ,8節(jié)點必須構(gòu)造函數(shù)：構(gòu)造函數(shù) 1public Node(int value){ this.Value=value; isEmpty=false; this.left=new Node(); this.right=new Node();}構(gòu)造函數(shù) 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條經(jīng)驗 獲得超11個贊
要從 BST 打印數(shù)據(jù)，您需要進行順序遍歷。在二叉搜索樹 (BST) 的情況下，中序遍歷以非遞減順序給出節(jié)點。要以非遞增順序獲取 BST 的節(jié)點，可以使用 Inorder 遍歷的變體，其中可以使用 Inorder 遍歷 s reversed。
算法 Inorder(tree) 1.遍歷左子樹，即調(diào)用Inorder(left-subtree) 2.訪問根。3.遍歷右子樹，即調(diào)用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);
}
時間復(fù)雜度：O(n)
如果樹不是BST。您可以創(chuàng)建 List 并將樹的值寫入列表，然后按升序?qū)α斜磉M行排序。
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
提交
取消