c++ - 二叉搜索树节点的结构应该是什么

Question

我正在尝试为二叉搜索树制作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.这是我第一次学习数据结构，所以如果有人能用简单的语言解释二叉树的递归和非递归遍历之间的区别，那将会有很大的帮助考虑中

Answer 1

i change the node structure and add one more pointer pointing to the parent [...] is this considered as normal practice or bad form of programming a binary tree ?

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

This is first time i am learning data structures so it will be a great help if someone can explain in simple words that what is the difference between recursive and non-recursive traversal

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

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

这是一个打印到控制台的示例，它显示了递归和非递归之间的区别(该示例不完整，因为这是家庭作业:]):

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);
}