N元树的二进制表示 [英] Binary Representation of N-ary Tree

问题描述

我目前正在尝试使用具有未知数量子节点的Node来构建树结构，但是我还必须跟踪父Node.我查看了这个问题 C语言中的N元树，并做了类似的结构在链接中建议:

I am currently trying to make a tree structure with Nodes having an unknown amount of children but I also have to keep track of parent Nodes. I looked at this question N-ary trees in C and made a structure similar to that advised in the link:

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()方法，因为我需要跟踪父节点.关于我该如何处理，有什么建议吗?

It says that by making the tree in this way, it makes certain algorithms easier to code. However, I am having a difficult time figuring out how I would create insert() and search() methods for this structure, seeing that I need to keep track of parent nodes. Are there any suggestions as to how I may go about this?

这是我的insert()方法:

Here is my insert() method:

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

}

}

这看起来正确吗?

推荐答案

对于任何树结构，搜索都将使用相对相同的算法(如果未排序，则采用深度优先递归；如果进行排序，则采用简单的树搜索(例如二进制搜索)树)).插入时，您要做的就是将新节点的.parent分配给父节点.然后将新节点的.parent.child[1]分配给新节点(从而将父节点链接到子节点).然后，检查父节点的其他子节点，以分配新节点的兄弟姐妹(如果有).

With any tree structure, searching is going to use relatively the same algorithm (depth-first recursion if unsorted, or simple tree-searching if sorted (like binary search tree)). When you insert, all you need to do is assign the new node's .parent to the parent. Then assign the new node's .parent.child[1] to the new node (thus linking the parent to the child). Then, check the other children of the parent node to assign your new node's siblings (if any).

好的，所以这里有一些伪代码(大多数情况下像java一样-抱歉，这就是我今天写的东西)，它将使用第二个示例来实现节点创建和一系列分配以将其维护在树结构中.您提供的链接:

Okay, so here's some pseudocode (mostly like java -- sorry, it's what i've been writing today) that will implement node creation and the series of assignments to maintain it in a tree structure, using the second example in the link you provided:

(节点源):

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())时，我们需要将父节点，子节点和兄弟姐妹重新链接到新节点内的新父节点，子节点和兄弟姐妹中.例如，我们这样做:

When we find the spot (using search()) where our new node should go, we need to reassign the parent, children, and siblings "links" inside the new node to its new parent, children, and siblings. For example, we take this:

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

然后我们将在F插入一个新节点(X).这只是为了说明我们如何重新分配每个新节点的链接.更好的细节可能会稍有不同，但是这里重要的是链接重新分配的实现示例:

And we will insert a new node (X) where F is. This is just to illustrate how we reassign each of the new node's links. The finer details may be slightly different, but what's important here is the implementation example of the link reassignment:

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

我们要做的是:1)创建X.2)将x.parent分配给c. 3)将c.children重新分配给x. 4)将x.siblings分配给f.这样会插入一个新节点(请注意，插入不同于排序，如果您明确地要求特定顺序，则树可能需要重新排序).

What we do is: 1) Create X. 2) Assign x.parent to c. 3) Reassign c.children to x. 4) Assign x.siblings to f. This inserts a new node (be mindful that an insertion is different than a sort and your tree may need resorting if you explicitly require a specific ordering).

这篇关于N元树的二进制表示的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！