我正在为学校做一个练习,我必须在java中创建一个方法(最多O(n)时间)来存储给定值在二叉树中出现的顺序,无论是后序、中序还是前序遍历。到目前为止,我已经有了工作代码,但计数器没有正确增加。有人可以让我知道我做错了什么吗?我的代码如下:
public class Node {
int value; // data used as key value
Node left; // this node's left child
Node right; // this node's right child
int preorderNumber; // node number in preorder
int inorderNumber; // node number in inorder
int postorderNumber; // node number in postorder
public Node(int item) { //instantiates node.
value = item;
left = right = null;
preorderNumber = inorderNumber = postorderNumber = 0;
}
}
/* Given a binary tree, print its nodes according to the postorder traversal. */
private void printPostorder(Node node) {
int counter = 0;
if (node == null) { //the tree is empty.
return;
}
printPostorder(node.left); // first recur on left subtree
printPostorder(node.right); // then recur on right subtree
System.out.print(node.value + " "); // now deal with the node
counter++;
node.postorderNumber = counter;
}
/* Given a binary tree, print its nodes in inorder*/
private void printInorder(Node node) {
int counter = 0;
if (node == null) {
return;
}
printInorder(node.left); // first recur on left child
System.out.print(node.value + " "); // then print the data of node
counter++;
node.inorderNumber = counter;
printInorder(node.right); // now recur on right child
}
/* Given a binary tree, print its nodes in preorder*/
private void printPreorder(Node node) {
int counter = 0;
if (node == null) { //binary tree is empty.
return;
}
System.out.print(node.value + " "); // first print data of node.
counter++;
node.preorderNumber = counter;
printPreorder(node.left); // recur on left subtree
printPreorder(node.right); // now recur on right subtree
}
public int find(int valueToFind) {
Node current = root, prior = null;
while (current != null) {
int compare;
compare = (valueToFind - current.value);
if (compare < 0) {
prior = current;
current = current.left;
} else if (compare > 0) {
current = current.right;
} else {
System.out.println("The node value searched for is : " + valueToFind);
System.out.println("The in order value is: " + current.inorderNumber);
System.out.println("The post order value is: " + current.postorderNumber);
System.out.println("The pre order value is: " + current.preorderNumber);
return current.value;
}
}
return prior == null ? null : prior.value;
}
}
但是,每当我尝试运行此程序时,我都会得到类似以下输出的内容:
节点数量为:2 二叉树的前序遍历为 3 4 二叉树的中序遍历为 3 4 二叉树的后序遍历为 4 3 搜索到的节点值为:4 顺序值为:1 订单后值为:1 预购金额为:1
我不确定如何将计数器的值传递给节点,以便它保存正确的值(在本例中为 2、2 和 1)。谢谢你!
最佳答案
您需要从prv值获取计数器。否则会一直重置。像下面这样做
private void printPostorder(Node node) {
if (node == null) { //the tree is empty.
return;
}
int counter = node.postorderNumber;
printPostorder(node.left); // first recur on left subtree
printPostorder(node.right); // then recur on right subtree
System.out.print(node.value + " "); // now deal with the node
counter++;
node.postorderNumber = counter;
}
预购方法也应该像这样改变,否则计数器不会增加
关于java - 在java中的二叉树递归函数中存储计数器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53353084/