質問
こんにちは、Marc Gravellの助けを借りてこのコードを作成しました
BinarySearchTreeで_leftと_rightが見つからないのはなぜですか?
&
BST C#コードの暗黙的な変換エラーを修正するにはどうすればよいですか
、そのバイナリ検索ツリーですが、論理エラーが発生していますが、結果は間違っています。私のコードの出力は次のとおりです。
2
3
5
6
10
17
------------------------------------------------
17
2
------------------------------------------------
3
6
Press any key to continue . . .
最後の2つの数値は、挿入された要素の合計を6にする必要がありますが、9を示しています
しかし、方法ツリーの高さを取得するにはどうすればよいですか?
using System;
using System.Collections.Generic;
using System.Text;
namespace errors
{
class Program
{
static void Main(string[] args)
{
BinarySearchTree t = new BinarySearchTree();
t.insert(ref t.root, 10);
t.insert(ref t.root, 5);
t.insert(ref t.root, 6);
t.insert(ref t.root, 17);
t.insert(ref t.root, 2);
t.insert(ref t.root, 3);
BinarySearchTree.print(t.root);
Console.WriteLine("------------------------------------------------");
Console.WriteLine(t.FindMax());
Console.WriteLine(t.FindMin());
Console.WriteLine("------------------------------------------------");
Console.WriteLine(t.CountLeaves(t.root));
Console.WriteLine(t.CountNodes(t.root));
}
public class TreeNode
{
public int n;
public TreeNode _left;
public TreeNode _right;
public TreeNode(int n, TreeNode _left, TreeNode _right)
{
this.n = n;
this._left = _left;
this._right = _right;
}
public void DisplayNode()
{
Console.Write(n);
}
}
public class BinarySearchTree
{
public TreeNode root;
public BinarySearchTree()
{
root = null;
}
public void insert(ref TreeNode root, int x)
{
if (root == null)
{
root = new TreeNode(x, null, null);
}
else
if (x < root.n)
insert(ref root._left, x);
else
insert(ref root._right, x);
}
public int FindMin()
{
TreeNode current = root;
while (current._left != null)
current = current._left;
return current.n;
}
public int FindMax()
{
TreeNode current = root;
while (current._right != null)
current = current._right;
return current.n;
}
public TreeNode Find(int key)
{
TreeNode current = root;
while (current.n != key)
{
if (key < current.n)
current = current._left;
else
current = current._right;
if (current == null)
return null;
}
return current;
}
public void InOrder(ref TreeNode root)
{
if (root != null)
{
InOrder(ref root._left);
root.DisplayNode();
InOrder(ref root._right);
}
}
public int CountNodes(TreeNode root)
{
int count=1;
if (root._left != null)
count += CountNodes(root._left);
if (root._right != null)
count += CountNodes(root._right);
return count;
}
public int CountLeaves(TreeNode root)
{
int count = (root._left == null && root._right == null) ? 1 : 0;
if (root._left != null)
count += CountLeaves(root._left);
if (root._right != null)
count += CountLeaves(root._right);
return count;
}
public static void print(TreeNode root)
{
if (root != null)
{
print(root._left);
Console.WriteLine(root.n.ToString());
print(root._right);
}
}
}
}
}
事前に感謝し、Marc Gravellに感謝します。
解決
CountNodes
の意味がすべての非リーフノードをカウントすることである場合、次の行を変更する必要があります。
int count=1;
これを読むには
int count = (root._left == null && root._right == null) ? 0 : 1;
( CountLeaves
にあるものの反対)。
これにより、ツリーの高さが取得されます:
public int Height(TreeNode root)
{
int height = 1;
if (root._left != null)
height = Math.Max(height, Height(root._left));
if (root._right != null)
height = Math.Max(height, Height(root._right));
return height;
}
他のヒント
ツリーの高さの取得については、次の再帰擬似コードを使用して、 nodeHeight(root)
を呼び出します。
nodeHeight(node)
left=0
right=0
if (node == null) return 0
left = 1 + nodeHeight(getLeft(node))
right = 1 + nodeHeight(getRight(node))
return max(left,right)
ツリーのバランスを調整しているようには見えないので、単純なリンクリストを取得するだけで、誤った値を説明できます。適切にバランスの取れたツリーは、log2(n)の最大高さを持ちます。
所属していません StackOverflow