将信息存储在遍历它们的节点中
storing information in nodes traversing them
我的任务是创建一棵存储斐波那契数列的树。我之前回收了一些代码，用于创建一个充满名称的树和每个节点的键。我似乎无法弄清楚为什么当我执行任何遍历时它没有打印出节点的键和存储的值。我觉得我错过了一些如此简单的东西。好的，谢谢您的宝贵时间！或者也许我误解了作业。我不希望直接回答，因为这与我的教育有关！
原始说明
Create a binary tree that stores your calls. How many calls will each internal node make? How many internal nodes will you have for a recursive version of the solution? Now, how big is that number? What if you call 5 “n” and think of Fib(n). What is the runtime complexity of your solution? Do you think you can do better if you simply do away with the recursion and calculate the Fibonacci series iteratively? Write a non-recursive solution and perform a similar analysis on it. How many lines of code would you execute in terms of “n”? Is it better or worse? Why do you think this is true?
class Node {
int key;
int value;
Node leftChild;
Node rightChild;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
剩下的就是这些了
package bigobinarytree;
public class BigOBinaryTree {
Node root;
public void addNode(int key, int value) {
Node newNode;
newNode = new Node(key, value);
if (root == null) {
root = newNode;
}
else {
Node focusNode = root;
Node parent;
while (true) {
parent = focusNode;
if (key < focusNode.key) {
focusNode = focusNode.leftChild;
if (focusNode == null) {
parent.leftChild = newNode;
return;
}
}
else
{
focusNode = focusNode.rightChild;
if (focusNode == null) {
parent.rightChild = newNode;
return;
}
}
}
}
}
public void inOrderTraverse(Node focusNode) {
if (focusNode != null) {
inOrderTraverse(focusNode.leftChild);
System.out.println(focusNode);
inOrderTraverse(focusNode.rightChild);
}
}
public void preorderTraverse(Node focusNode) {
if (focusNode != null) {
System.out.println(focusNode);
preorderTraverse(focusNode.leftChild);
preorderTraverse(focusNode.rightChild);
}
}
public void postOrderTraverse(Node focusNode) {
if (focusNode != null) {
postOrderTraverse(focusNode.leftChild);
postOrderTraverse(focusNode.rightChild);
System.out.println(focusNode);
}
}
public Node findNode(int key) {
Node focusNode = root;
while (focusNode.key != key) {
if (key < focusNode.key) {
focusNode = focusNode.leftChild;
} else {
focusNode = focusNode.rightChild;
}
if (focusNode == null)
return null;
}
return focusNode;
}
public Node findValue(int value) {
Node focusNode = root;
while (focusNode.value != value) {
if (value != focusNode.value) {
focusNode = focusNode.leftChild;
} else {
focusNode = focusNode.rightChild;
}
if (focusNode == null)
return null;
}
return focusNode;
}
public boolean remove(int key) {
Node focusNode = root;
Node parent = root;
boolean isItALeftChild = true;
while (focusNode.key != key) {
parent = focusNode;
if (key < focusNode.key) {
isItALeftChild = true;
focusNode = focusNode.leftChild;
} else {
isItALeftChild = false;
focusNode = focusNode.rightChild;
}
if (focusNode == null)
return false;
}
if (focusNode.leftChild == null && focusNode.rightChild == null) {
if (focusNode == root)
root = null;
else if (isItALeftChild)
parent.leftChild = null;
else
parent.rightChild = null;
}
else if (focusNode.rightChild == null) {
if (focusNode == root)
root = focusNode.leftChild;
else if (isItALeftChild)
parent.leftChild = focusNode.leftChild;
else
parent.rightChild = focusNode.leftChild;
}
else if (focusNode.leftChild == null) {
if (focusNode == root)
root = focusNode.rightChild;
else if (isItALeftChild)
parent.leftChild = focusNode.rightChild;
else
parent.rightChild = focusNode.rightChild;
}
else {
Node replacement = getReplacementNode(focusNode);
if (focusNode == root)
root = replacement;
else if (isItALeftChild)
parent.leftChild = replacement;
else
parent.rightChild = replacement;
replacement.leftChild = focusNode.leftChild;
}
return true;
}
public Node getReplacementNode(Node replacedNode) {
Node replacementParent = replacedNode;
Node replacement = replacedNode;
Node focusNode = replacedNode.rightChild;
while (focusNode != null) {
replacementParent = replacement;
replacement = focusNode;
focusNode = focusNode.leftChild;
}
if (replacement != replacedNode.rightChild) {
replacementParent.leftChild = replacement.rightChild;
replacement.rightChild = replacedNode.rightChild;
}
return replacement;
}
public static void main(String[] args) {
BigOBinaryTree theTree = new BigOBinaryTree();
int fib1=1, fib2=1, nacci=1;
int key = 0;
for (int i=3; i <= 50; i++ ){
nacci = fib1 + fib2;
fib1 = fib2;
fib2 = nacci;
theTree.addNode(key, nacci);
key++;
}
System.out.println();
System.out.println("preorderTraverse");
System.out.println();
theTree.preorderTraverse(theTree.root);
System.out.println("___________________");
}
}
您在主方法中调用了 preorder 方法。
if (focusNode != null) {
System.out.println(focusNode);
preorderTraverse(focusNode.leftChild);
preorderTraverse(focusNode.rightChild);
}
这会给你任何输出吗？如果您得到一些输出，根据您的代码，它将只是 focusNode 对象的标准 toString() 方法。如果要像键一样打印出对象的字段值，则必须访问这些字段或覆盖 toString() 方法。喜欢：
System.out.println(focusNode.key);
你是对的，这很简单，但苦乐参半。你打过电话
System.out.println(focusNode);
但是，对于对象（如 focusNode），System.out.println() 会自动调用该对象的 toString() 方法。对于大多数对象来说，这只是意味着打印出它们的对象 ID，而且对于大多数对象来说，这并不是很有用。至少不适用于这样的程序。不过，好消息是有两个修复方法！首先，您可以覆盖节点的 toString()。喜欢：
@Override
public String toString() {
return "Key:" + key + " Value:" + value;
}
您只需将其放入节点 class。然后，每次调用 System.out.println(focusNode) 时，它实际上是在节点 class 中打印 toString() 方法的输出。或者，使用：
System.out.println(focusNode);
你可以使用：
System.out.println("Key:" + focusNode.key + " Value:" + focusNode.value);
我的任务是创建一棵存储斐波那契数列的树。我之前回收了一些代码，用于创建一个充满名称的树和每个节点的键。我似乎无法弄清楚为什么当我执行任何遍历时它没有打印出节点的键和存储的值。我觉得我错过了一些如此简单的东西。好的，谢谢您的宝贵时间！或者也许我误解了作业。我不希望直接回答，因为这与我的教育有关！
原始说明
Create a binary tree that stores your calls. How many calls will each internal node make? How many internal nodes will you have for a recursive version of the solution? Now, how big is that number? What if you call 5 “n” and think of Fib(n). What is the runtime complexity of your solution? Do you think you can do better if you simply do away with the recursion and calculate the Fibonacci series iteratively? Write a non-recursive solution and perform a similar analysis on it. How many lines of code would you execute in terms of “n”? Is it better or worse? Why do you think this is true?
class Node {
int key;
int value;
Node leftChild;
Node rightChild;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
剩下的就是这些了
package bigobinarytree;
public class BigOBinaryTree {
Node root;
public void addNode(int key, int value) {
Node newNode;
newNode = new Node(key, value);
if (root == null) {
root = newNode;
}
else {
Node focusNode = root;
Node parent;
while (true) {
parent = focusNode;
if (key < focusNode.key) {
focusNode = focusNode.leftChild;
if (focusNode == null) {
parent.leftChild = newNode;
return;
}
}
else
{
focusNode = focusNode.rightChild;
if (focusNode == null) {
parent.rightChild = newNode;
return;
}
}
}
}
}
public void inOrderTraverse(Node focusNode) {
if (focusNode != null) {
inOrderTraverse(focusNode.leftChild);
System.out.println(focusNode);
inOrderTraverse(focusNode.rightChild);
}
}
public void preorderTraverse(Node focusNode) {
if (focusNode != null) {
System.out.println(focusNode);
preorderTraverse(focusNode.leftChild);
preorderTraverse(focusNode.rightChild);
}
}
public void postOrderTraverse(Node focusNode) {
if (focusNode != null) {
postOrderTraverse(focusNode.leftChild);
postOrderTraverse(focusNode.rightChild);
System.out.println(focusNode);
}
}
public Node findNode(int key) {
Node focusNode = root;
while (focusNode.key != key) {
if (key < focusNode.key) {
focusNode = focusNode.leftChild;
} else {
focusNode = focusNode.rightChild;
}
if (focusNode == null)
return null;
}
return focusNode;
}
public Node findValue(int value) {
Node focusNode = root;
while (focusNode.value != value) {
if (value != focusNode.value) {
focusNode = focusNode.leftChild;
} else {
focusNode = focusNode.rightChild;
}
if (focusNode == null)
return null;
}
return focusNode;
}
public boolean remove(int key) {
Node focusNode = root;
Node parent = root;
boolean isItALeftChild = true;
while (focusNode.key != key) {
parent = focusNode;
if (key < focusNode.key) {
isItALeftChild = true;
focusNode = focusNode.leftChild;
} else {
isItALeftChild = false;
focusNode = focusNode.rightChild;
}
if (focusNode == null)
return false;
}
if (focusNode.leftChild == null && focusNode.rightChild == null) {
if (focusNode == root)
root = null;
else if (isItALeftChild)
parent.leftChild = null;
else
parent.rightChild = null;
}
else if (focusNode.rightChild == null) {
if (focusNode == root)
root = focusNode.leftChild;
else if (isItALeftChild)
parent.leftChild = focusNode.leftChild;
else
parent.rightChild = focusNode.leftChild;
}
else if (focusNode.leftChild == null) {
if (focusNode == root)
root = focusNode.rightChild;
else if (isItALeftChild)
parent.leftChild = focusNode.rightChild;
else
parent.rightChild = focusNode.rightChild;
}
else {
Node replacement = getReplacementNode(focusNode);
if (focusNode == root)
root = replacement;
else if (isItALeftChild)
parent.leftChild = replacement;
else
parent.rightChild = replacement;
replacement.leftChild = focusNode.leftChild;
}
return true;
}
public Node getReplacementNode(Node replacedNode) {
Node replacementParent = replacedNode;
Node replacement = replacedNode;
Node focusNode = replacedNode.rightChild;
while (focusNode != null) {
replacementParent = replacement;
replacement = focusNode;
focusNode = focusNode.leftChild;
}
if (replacement != replacedNode.rightChild) {
replacementParent.leftChild = replacement.rightChild;
replacement.rightChild = replacedNode.rightChild;
}
return replacement;
}
public static void main(String[] args) {
BigOBinaryTree theTree = new BigOBinaryTree();
int fib1=1, fib2=1, nacci=1;
int key = 0;
for (int i=3; i <= 50; i++ ){
nacci = fib1 + fib2;
fib1 = fib2;
fib2 = nacci;
theTree.addNode(key, nacci);
key++;
}
System.out.println();
System.out.println("preorderTraverse");
System.out.println();
theTree.preorderTraverse(theTree.root);
System.out.println("___________________");
}
}
您在主方法中调用了 preorder 方法。
if (focusNode != null) {
System.out.println(focusNode);
preorderTraverse(focusNode.leftChild);
preorderTraverse(focusNode.rightChild);
}
这会给你任何输出吗？如果您得到一些输出，根据您的代码，它将只是 focusNode 对象的标准 toString() 方法。如果要像键一样打印出对象的字段值，则必须访问这些字段或覆盖 toString() 方法。喜欢：
System.out.println(focusNode.key);
你是对的，这很简单，但苦乐参半。你打过电话
System.out.println(focusNode);
但是，对于对象（如 focusNode），System.out.println() 会自动调用该对象的 toString() 方法。对于大多数对象来说，这只是意味着打印出它们的对象 ID，而且对于大多数对象来说，这并不是很有用。至少不适用于这样的程序。不过，好消息是有两个修复方法！首先，您可以覆盖节点的 toString()。喜欢：
@Override
public String toString() {
return "Key:" + key + " Value:" + value;
}
您只需将其放入节点 class。然后，每次调用 System.out.println(focusNode) 时，它实际上是在节点 class 中打印 toString() 方法的输出。或者，使用：
System.out.println(focusNode);
你可以使用：
System.out.println("Key:" + focusNode.key + " Value:" + focusNode.value);