2

我目前正在尝试使用具有未知数量的子节点的节点创建树结构，但我还必须跟踪父节点。我在 C 中查看了这个问题N-ary trees并制作了一个类似于链接中建议的结构：

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]新节点（从而将父节点链接到子节点）。然后，检查父节点的其他子节点以分配新节点的兄弟节点（如果有）。

好的，所以这里有一些伪代码（主要像 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 回答