如何创建一个c/C++树脚本？

Question

如何创建一个脚本：

比较两棵树，

在C/C++在非递归模式？

也

如何创建C/C++脚本来验证，如果树是二进制的，在非递归模式？

在此先感谢。

Answer 1

首先，在C/C++中，您不写脚本。你编写程序并用编译器编译它们。

您可以通过显式管理堆栈数据结构来模拟任何递归算法。所以，假设你知道谁在做什么递归，你也可以迭代地做。

验证一棵树是“二元”在C++中确实没有太多意义。在C++中，二叉树的每个节点都有左指针和右指针。要结束二叉树，您需要将数据结构设计为二叉树。

如果您有一个可以拥有任意数量子项的普通树，并且您想验证每个节点都有< = 2个子项，只需遍历所有节点，递归或迭代地检查子项数是否为< = 2.

Answer 2

要比较两个二叉树，您必须访问（遍历）每个节点并比较其内容。您还应该比较节点的数量（如果树头包含一个包含节点数的变量，则这可能会更快）。

没有递归，你必须在遍历子树时记住父节点。一个便利的结构是一个堆栈。一种方法是将当前节点推入堆栈，遍历左侧子树，弹出节点，遍历右侧子树。

在网上搜索一些例子，“遍历二叉树”。我喜欢显示图表的网页与所有文字图表。 :-)