C++打印出二叉搜索树

Question

这个圣诞节假期没有更好的事情可做，所以我决定尝试制作一棵二叉搜索树。我被打印功能困住了。其背后的逻辑应该如何运作？由于树已经按照某种排序顺序插入它，并且我想从最小值到最大值打印树。

所以我需要移动到树的最左边的分支来打印第一个值。对了，那么之后我怎么记住备份的方式，需要保存之前的节点吗？在维基百科中搜索给了我一个他们使用堆栈的解决方案。和其他解决方案，我不太明白他们是如何做到的，所以我在这里问，而不是希望有人能启发我。

我也想知道我的插入功能是否正常。我见过其他人的解决方案更小。

void treenode::insert(int i)
{

   if(root == 0)
   {
      cout << "root" << endl;
      root = new node(i,root);
   }
   else
   {
      node* travel = root;
      node* prev;
      while(travel)
      {
         if(travel->value > i)
         {
            cout << "travel left" << endl;
            prev = travel;
            travel = travel->left;
         }
         else
         {
            cout << "travel right" << endl;
            prev = travel;
            travel = travel->right;
         }
      }
      //insert
      if(prev->value > i)
      {
         cout << "left" << endl;
         prev->left = new node(i);
      }
      else
      {
         cout << "right" << endl;
         prev->right = new node(i);
      }
   }

}

void treenode::print()
{

   node* travel = root;
   while(travel)
   {
      cout << travel->value << endl;
      travel = travel->left;
   }

}

Answer 1

您可以使用递归（伪代码）：

prin-tree(node):
   print-tree(left-subnode) if exists
   print(node-value)
   print-tree(right-subnode) if exists
...
print(root-of-tree)

Answer 2

遍历二叉树执行任何操作（打印、搜索、插入等）的传统 CS101 方法是使用递归。让（无论什么）例程检查其当前节点，然后如果这不是它要查找的节点，则使用左子树和/或右子树（如果有）调用自身。

有关 psedocode 的精彩讨论，请查看有关树遍历的维基百科文章。它甚至展示了如何不使用递归来完成此操作，这将与您的插入方式相匹配。

Answer 3

这一切都取决于树的定义。如果节点不包含返回父节点的指针，则需要使用堆栈来打印有序横截面。最简单的方法是编写一个递归函数来使用应用程序的堆栈。该算法之前已经展示过，但基本上是：

in-order(node):
   in-order(node.left) if node.left not null
   process(node)
   in-order(node.right) if node.right not null

如果节点保留指向父节点的指针，那么您可以编写一个迭代版本，但这可能不值得付出努力（除了发人深省之外）