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