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