我正在尝试为二叉搜索树制作C ++程序，该程序将包含以下功能（实际上这是我大学作业的一部分）：
A） 创建二叉搜索树。
B） 序、预序、后序遍历。（ 非递归 ）
C） 在树中搜索瓦尔。
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.这是我第一次学习数据结构，所以如果有人可以用简单的话解释递归和非递归遍历与二叉树有什么区别
我更改节点结构并添加另一个指向父节点的指针 [...] 这被认为是正常做法还是编写二叉树的不良形式？
这不是正常的做法（但不是很"糟糕的形式"）。每个节点都是数据和两个指针的集合。如果向每个节点添加第三个指针，则将每个节点的开销增加 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);
}
-
不需要指向父节点的指针。想想你会使用它的情况。访问节点的唯一方法是通过其父节点，因此您已经访问了父节点。
-
你知道递归是什么意思吗？
如果需要，没有什么可以阻止您添加父指针。但是，这通常不是必需的，并且会略微增加大小和复杂性。
遍历树的正常方法是某种递归函数。首先调用函数并传入树的根节点。然后，该函数调用自身，传递子指针（一次一个）。这种情况一直递归地沿着树向下发生，直到没有子节点。
该函数在递归调用返回后在其自己的节点上执行您想要的任何处理。这意味着您基本上是在每次调用时向下遍历树（使您的调用堆栈逐渐更深），然后在每个函数返回时在返回的过程中进行处理。
该函数永远不应该尝试以与树相同的方式返回树（即传入父指针），否则最终将得到无限递归。
如果需要支持迭代，则只需要父指针假设您找到了一个叶节点，然后想要查找下一个节点（最低键大于当前键），例如：
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
}
由于这里您是从底部而不是顶部开始的，因此您需要向上
但是你的赋值只需要从根节点开始的操作，你不应该有一个向上指针，按照其他答案来避免需要上升的方法。
我建议你研究一下访客模式 - 因为它的味道，而不是专门针对它的结构（它非常复杂）。
从本质上讲，它是一种设计模式，它断开树的遍历，这样您只有一组代码执行树遍历，并且您可以使用这组代码在每个节点上执行各种功能。 遍历代码通常不是 Node 类的一部分。
具体来说，它将允许您不必多次编写遍历代码 - 例如，utnapistims 答案将强制您为所需的每个功能编写遍历代码; 该示例涵盖打印 - ouputXML（） 将需要遍历代码的另一个副本。 最终，你的 Node 类变成了一头巨大的笨蛋。
使用 Visitor，您将拥有 Tree 和 Node 类、一个单独的 Traversal 类以及许多函数类（如 PrintNode、NodeToXML 和可能的 DeleteNode）来与 Traversal 类一起使用。
至于添加 Parent 指针，这仅在您打算在调用树之间停放在给定节点上时才有用 - 即您将从预先选择的任意节点开始进行相对搜索。 这可能意味着您最好不要对所述树进行任何多线程工作。 父指针也很难更新，因为红/黑树可以轻松地在当前节点及其"父节点"之间插入新节点。
我建议使用BinaryTree类，其方法可以实例化单个Visiter类，并且访问者类接受Traversal接口的实现，该接口将是Widthth，Width或Binary之一。 基本上，当 Visitor 准备好移动到下一个节点时，它会调用 Traversal 接口实现来获取它（下一个节点）。