0
私はフィボナッチ数を格納するツリーを作成するように任命されました。以前は、各ノードの名前とキーでいっぱいのツリーを作成するために使用されたコードをリサイクルしました。私は、トラバーサルを実行したときにノードとキーの値のキーを出力しないのはなぜか分かりません。私はとてもシンプルなものを見逃しているように感じます。あなたの時間をありがとう！または、私は割り当てを誤解しているかもしれません。これは私の教育に関連しているので、私は直接的な答えを期待していません！それらを横断するノードに情報を格納
元の指示
あなたの呼び出しを格納するバイナリツリーを作成します。各内部ノードはいくつのコールを発信しますか？再帰的なバージョンのソリューションでは、内部ノードはいくつありますか？今、その数字はどれくらい大きいですか？あなたが5 "n"と呼んでFib（n）を考えるとどうなりますか？ソリューションのランタイムの複雑さは？単純に再帰をやめ、フィボナッチ級数を繰り返し計算すれば、もっとうまくいくと思いますか？非再帰的な解を作成し、同様の解析を実行します。あなたは "n"という言葉でいくつの行のコードを実行しますか？それは良いか悪いですか？なぜこれは本当だと思いますか？
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("___________________");
}
}