2

私は現在、不明な量の子ノードを持つツリー構造を作成しようとしていますが、親ノードも追跡する必要があります。私はこの質問をCで見て、リンクでアドバイスされているものと同様の構造を作りました:

template <class T>
struct treeNode {

public: 

T  * data;
treeNode *parent;
treeNode *kids; //left 
treeNode *siblings; //right


treeNode();
~treeNode();
treeNode(T data);
void treeInsert(T newItem);



};

このようにツリーを作成することで、特定のアルゴリズムをコーディングしやすくすると述べています。ただし、親ノードを追跡する必要があるため、この構造の insert() および search() メソッドを作成する方法を理解するのに苦労しています。これについてどうすればよいかについて何か提案はありますか?

編集：

これが私のinsert（）メソッドです：

template<class T>
bool NewTree<T>::insert( T *data, treeNode<T> * parent)
{
if(this->root == NULL)
{
    this->root = new treeNode<T>();
    this->root->data = data;
    this->root->parent = NULL;
    this->root->children = NULL;
}
else
{
    treeNode temp = new treenode<T>();
    temp.data = data;
    temp.parent = parent;
    parent->children->siblings = temp; // add node to siblings of parent's   children
    parent->children = temp; // add node to children of parent

}

}

これは正しく見えますか？

4

1 に答える 1

1

どのツリー構造でも、検索は比較的同じアルゴリズムを使用します (ソートされていない場合は深さ優先再帰、ソートされている場合は単純なツリー検索 (二分探索ツリーなど))。挿入するときは、新しいノード.parentを親に割り当てるだけです。次に、新しいノードを新しいノードに割り当て.parent.child[1]ます (したがって、親を子にリンクします)。次に、親ノードの他の子をチェックして、新しいノードの兄弟 (存在する場合) を割り当てます。

さて、あなたが提供したリンクの2番目の例を使用して、ノードの作成とそれをツリー構造で維持するための一連の割り当てを実装する疑似コード(主にJavaのようなものです。申し訳ありませんが、今日書いているものです)です。 :

(ノード ソース):

class Node {
  // generic data store
  public int data;
  public Node parent;
  public Node siblings;
  public Node children;
}

(ツリー ソース):

class NewTree {
  // current node
  public Node current;
  // pointer to root node
  public Node root;

  // constructor here
  // create new node
  public boolean insert(int data) {
    // search for the node which is immediately BEFORE where the new node should go
    // remember that with duplicate data values, we can just put the new node in
    // front of the chain of siblings
    Node neighbor = this.search(data);
    // if we've found the node our new node should follow, create it with the 
    // found node as parent, otherwise we are creating the root node
    // so if we're creating the root node, we simply create it and then set its
    // children, siblings, and parent to null
    // i think this is the part you're having trouble with, so look below for a 
    // diagram for visual aid
  }

  public Node search(int target) {
    // basically we just iterate through the chain of siblings and/or children 
    // until this.current.children is null or this.current.siblings is null
    // we need to make certain that we also search the children of 
    // this.index.sibling that may exist (depth-first recursive search)
  }
}

新しいノードが移動する場所を (search() を使用して) 見つけたら、新しいノード内の親、子、および兄弟の「リンク」を新しい親、子、および兄弟に再割り当てする必要があります。たとえば、次のようにします。

A-|
|
B-C-|
| |
| F-G-|  
| |
| -
|
D-E-|
| |
- H-|
  |
  -

そして、F の場所に新しいノード (X) を挿入します。これは、新しいノードの各リンクを再割り当てする方法を説明するためのものです。細かいところは少し違うかもしれませんが、ここで重要なのはリンクの再割り当ての実装例です。

A-|
|
B-C-|
| |
| X-F-G-|  
| | |
| - -
|
D-E-|
| |
- H-|
  |
  -

1) X を作成します。2) x.parent を c に割り当てます。3) c.children を x に再割り当てします。4) x.siblings を f に割り当てます。これにより、新しいノードが挿入されます (挿入はソートとは異なり、特定の順序付けが明示的に必要な場合は、ツリーの再ソートが必要になる場合があることに注意してください)。

于 2013-02-28T03:42:01.337 に答える