2

我正在尝试为二进制搜索树制作 c++ 程序，该程序将包含以下功能（实际上这是我大学作业的一部分）：

A) 创建二叉搜索树。

B) 中序、前序、后序遍历。（非递归）

C) 在树中搜索 Val。

D) 广度优先遍历。

E) 深度优先遍历

F) 计算叶节点、非叶节点。

G) 计数号。级数

我的疑问是：-

1.通常一个树节点有以下结构：

class node{

 private:
   node *lChild;
   int info;
   node *rChild;
}

因此，如果我想执行深度优先或广度优先遍历，我可以更改节点结构并添加一个指向父节点的指针，以便我可以轻松地在层次结构中向后移动

class node{

 private:
   node *parent //pointer to parent node
   node *lChild;
   int info;
   node *rChild;
}

这被认为是编程二叉树的正常做法还是不好的形式？如果它不被认为是编程树的好方法，还有其他方法还是我必须使用使用堆栈（用于深度优先）和队列（用于广度优先）的书中给出的方法来存储节点（访问过或相应地未访问）

2.这是我第一次学习数据结构，所以如果有人能用简单的话解释一下考虑到二叉树的递归和非递归遍历有什么区别，那将是一个很大的帮助

4

5 回答 5

3

我更改了节点结构并添加了一个指向父级的指针 [...] 这被认为是正常的做法还是编程二叉树的不良形式？

这不是一种正常的做法（但也不是很“糟糕的形式”）。每个节点都是数据和两个指针的集合。如果向每个节点添加第三个指针，则每个节点的开销将增加 50%（每个节点两个指针到三个指针），这对于大型二叉树来说将是相当多的。

这是我第一次学习数据结构，所以如果有人能用简单的语言解释递归和非递归遍历之间的区别，那将是一个很大的帮助

递归实现是仅适用于节点的函数，然后为后续节点调用自身。这利用应用程序调用堆栈来处理树的节点。

非递归实现使用本地堆栈来推送未处理的节点；然后只要堆栈上有数据，它就会循环并处理每个条目。

这是打印到控制台的示例，显示了递归和非递归之间的区别（示例不完整，因为这是家庭作业：]）：

void recursive_print(node* n) {
    std::cout << n->info << "\n";
    if(n->lChild)
        recursive_print(n->lChild); // recursive call
    // n->rChild is processed the same
}
void non_recursive_print(node* n) {
    std::stack<node*> stack;
    stack.push(n);
    while(!stack.empty()) { // behaves (more or less) the same as 
                            // the call-stack in the recursive call
        node* x = stack.top();
        stack.pop();
        std::cout << x->info << "\n";
        if(x->lChild)
            stack.push(x->lChild); // non-recursive: push to the stack
        // x->rChild is processed the same way
    }
}
// client code:
node *root; // initialized elsewhere
if(root) {
    recursive_print(root);
    non_recursive_print(root);
}
于 2013-11-07T14:47:06.653 回答
1

  1. 您不需要指向父节点的指针。想想你会使用它的情况。您可以访问节点的唯一方法是通过其父节点，因此您已经访问了父节点。

  2. 你知道递归是什么意思吗？

于 2013-11-07T14:32:28.323 回答
0

There's nothing to stop you adding a parent pointer if you want to. However, it's not usually necessary, and slightly increases the size and complexity.

The normal approach for traversing a tree is some kind of recursive function. You first call the function and pass in the root node of the tree. The function then calls itself, passing the child pointers (one at a time). This happens recursively all the way down the tree until there are no child nodes left.

The function does whatever processing you want on its own node after the recursive calls have returned. That means you're basically traversing down the tree with each call (making your call stack progressively deeper), and then doing the processing on the way back up as each function returns.

The function should never try to go back up the tree the same way it came down (i.e. passing in a parent pointer), otherwise you'll end up with an infinite recursion.

于 2013-11-07T14:58:40.630 回答
0

通常你只需要一个父指针，如果你需要支持迭代假设你找到了一个叶子节点，然后想要找到下一个节点（最小的键大于当前的键），例如：

mytree::iterator it1=mytree_local.find(7);
if (it1 != mytree_local.end())
{
    mytree::iterator it2=it1.next();  // it1 is a leaf node and next() needs to go up
}

由于这里是从底部而不是顶部开始，因此您需要向上

但是你的分配只需要从根节点开始的操作，你不应该有一个向上的指针，遵循其他答案来避免需要向上的方法。

于 2013-11-07T15:41:15.423 回答
0

我建议您研究一下访问者模式——因为它的味道，而不是专门针对它的结构（它非常复杂）。

本质上，它是一种设计模式，它以这样一种方式断开树的遍历，即您只有一组执行树遍历的代码，并且您使用该组代码在每个节点上执行各种功能。遍历代码一般不属于 Node 类。

具体来说，它将允许您不必多次编写遍历代码 - 例如，utnapistims answer 将迫使您为所需的每个功能编写遍历代码；该示例涵盖了打印 - 到 ouputXML() 将需要另一个遍历代码副本。最终，你的 Node 类变成了一只笨拙的庞然大物。

使用 Visitor，您将拥有 Tree 和 Node 类、一个单独的 Traversal 类以及许多功能类，例如 PrintNode、NodeToXML 和可能的 DeleteNode，以与 Traversal 类一起使用。

至于添加父指针，这仅在您打算在对树的调用之间停放在给定节点上时才有用 - 即您打算从预先选择的任意节点开始进行相对搜索。这可能意味着您最好不要对所述树进行任何多线程工作。父指针也很难更新，因为红/黑树可以很容易地在当前节点和它的“父节点”之间插入一个新节点。

我建议使用 BinaryTree 类，该类具有实例化单个访问者类的方法，并且访问者类接受 Traversal 接口的实现，该接口可以是 Breadth、Width 或 Binary 之一。基本上，当Visitor准备移动到下一个节点时，它会调用Traversal接口实现来获取它（下一个节点）。

于 2014-01-24T21:09:35.697 回答