二分探索木という意味ではありません。
たとえば、値1,2,3,4,5を二分探索木に挿入すると、インオーダートラバーサルは出力として1,2,3,4,5を返します。
しかし、同じ値を二分木に挿入すると、インオーダートラバーサルは出力として4,2,5,1,3を与えるはずです。
二分木は、動的配列を使用して作成できます。動的配列では、インデックスnの各要素について、2n+1と2n+2がそれぞれその左と右の子を表します。
したがって、ここでは表現とレベル順序の走査が非常に簡単です。
でも、インオーダー、ポストオーダー、プレオーダーは難しいと思います。
私の質問は、二分探索木のような二分木をどのように作成できるかということです。すなわち。配列の代わりにデータ、左および右のポインタを含むツリークラスがあります。再帰的にトラバーサルを実行できるようにします。
私があなたを正しく理解しているなら、あなたは配列から二分木を作りたいと思うでしょう
int[] values = new int[] {1, 2, 3, 4, 5};
BinaryTree tree = new BinaryTree(values);
これにより、次のようにバイナリツリーに値1〜5が事前入力されます。
1
/ \
2 3
/ \
4 5
これは、次のクラスを使用して実行できます。
class BinaryTree
{
int value;
BinaryTree left;
BinaryTree right;
public BinaryTree(int[] values) : this(values, 0) {}
BinaryTree(int[] values, int index)
{
Load(this, values, index);
}
void Load(BinaryTree tree, int[] values, int index)
{
this.value = values[index];
if (index * 2 + 1 < values.Length)
{
this.left = new BinaryTree(values, index * 2 + 1);
}
if (index * 2 + 2 < values.Length)
{
this.right = new BinaryTree(values, index * 2 + 2);
}
}
}
ツリー クラスの宣言部分は、確かに、ここで難しいことではありません。あなたは基本的に、質問でそれを宣言する方法を正確に述べました：
class BinaryTree
{
private:
int data;
BinaryTree *left, *right;
};
これは、次のようなさまざまな形式のトラバーサルをサポートします。
void Inorder(const BinaryTree *root)
{
if(root == 0)
return;
Inorder(root->left);
printf("now at %d\n", root->data);
Inorder(root->right);
}
そこから、前後のトラバーサルを推測できるはずです。実際の実装では、ツリーはおそらくランダム データを格納するようにテンプレート化され、トラバーサル ルーチンはより一般的になります (ユーザー データ入力、またはユーザー提供のノードごとのコールバックなどを使用)。
私が尋ねた質問に対する回答を受け取っていないので、配列を使用したバイナリ ツリーの独自の実装を投稿します。配列の実装は思ったより簡単であることがわかりましたが、リンクされたリストを使用して同じものを実装する方法はまだわかりません。
コードはC＃です
class BinaryTree
{
private static int MAX_ELEM = 100; //initial size of the array
int lastElementIndex;
int?[] dataArray;
public BinaryTree()
{
dataArray = new int?[MAX_ELEM];
lastElementIndex = -1;
}
//function to insert data in to the tree
//insert as a complete binary tree
public void insertData(int data)
{
int?[] temp;
if (lastElementIndex + 1 < MAX_ELEM)
{
dataArray[++lastElementIndex] = data;
}
else
{ //double the size of the array on reaching the limit
temp = new int?[MAX_ELEM * 2];
for (int i = 0; i < MAX_ELEM; i++)
{
temp[i] = dataArray[i];
}
MAX_ELEM *= 2;
dataArray = temp;
dataArray[++lastElementIndex] = data;
}
}
//internal function used to get the left child of an element in the array
int getLeftChild(int index) {
if(lastElementIndex >= (2*index+1))
return (2*index + 1);
return -1;
}
//internal function used to get the right child of an element in the array
int getRightChild(int index) {
if(lastElementIndex >= (2*index+2))
return (2*index + 2);
return -1;
}
//function to check if the tree is empty
public bool isTreeEmpty() {
if (lastElementIndex == -1)
return true;
return false;
}
//recursive function for inorder traversal
public void traverseInOrder(int index) {
if (index == -1)
return;
traverseInOrder(getLeftChild(index));
Console.Write("{0} ", dataArray[index]);
traverseInOrder(getRightChild(index));
}
//recursive function for preorder traversal
public void traversePreOrder(int index) {
if (index == -1)
return;
Console.Write("{0} ", dataArray[index]);
traversePreOrder(getLeftChild(index));
traversePreOrder(getRightChild(index));
}
//recursive function for postorder traversal
public void traversePostOrder(int index) {
if (index == -1)
return;
traversePostOrder(getLeftChild(index));
traversePostOrder(getRightChild(index));
Console.Write("{0} ", dataArray[index]);
}
//function to traverse the tree in level order
public void traverseLevelOrder()
{
Console.WriteLine("\nPrinting Elements Of The Tree In Ascending Level Order\n");
if (lastElementIndex == -1)
{
Console.WriteLine("Empty Tree!...press any key to return");
Console.ReadKey();
return;
}
for (int i = 0; i <= lastElementIndex; i++)
{
Console.Write("{0} ", dataArray[i]);
}
Console.WriteLine("\n");
}
}
包括的な BinaryTree 実装のソースを探している場合は、The C5 Generic Collection Libraryを見て学ぶことができます。