c++ - N 叉树的二叉表示

标签 c++ tree binary-tree

我目前正在尝试使用具有未知数量子节点的节点创建树结构,但我还必须跟踪父节点。我看了这个问题N-ary trees in 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

}

}

这看起来正确吗?

最佳答案

对于任何树结构,搜索都将使用相对相同的算法(如果未排序则使用深度优先递归,如果排序则使用简单的树搜索(如二叉搜索树))。插入时,您需要做的就是将新节点的 .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。这会插入一个新节点(请注意,插入不同于排序,如果您明确要求特定顺序,则您的树可能需要求助)。

关于c++ - N 叉树的二叉表示,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15126977/

相关文章:

c++ -/usr/bin/ld 找不到 -l<nameOfLibrary>

c++ - 如何在 C++ 中使用 OpenCV 检测多个对象?

c++ - 如何在 unordered_map 中存储 2 个以上的变量?

tree - 在 Ada 中构建二叉表达式树

tree - 深度优先搜索的完整性

c++ - c++ typedef std::function<> 如何使用?

algorithm - 从 2-3-4 树计算一组插入和删除的摊销时间

Python 从递归 DFS 返回一个元素

java - 计算二叉树中通用对象的频率

data-structures - 什么是 Root过的树?