C语言非递归创建二叉树与遍历示例

本文档主要探讨的是C语言中的非递归树结构创建与遍历算法。首先，我们定义了两个结构体：`bitnode` 和 `bitree`，它们分别用于表示二叉树的节点和整型链表。`bitnode` 结构包含节点的数据域（int data），以及左孩子指针（lchild）和右孩子指针（rchild）。而 `stacktype` 结构则代表一个带标志的栈。 核心函数 `create` 实现了一个非递归方式创建二叉树的过程。它首先初始化一个大小为20的动态数组 `bitrees` 和一个栈 `s`。用户通过输入 `i` 和 `x` 的值，不断为树添加节点，直到 `i` 变为0。在循环内部，首先为新节点 `q` 分配内存，设置其数据为 `x`，然后将其作为子节点连接到相应的位置，根据 `i` 的奇偶性决定是左子树还是右子树。同时，将新节点 `q` 存入栈 `s`。当所有节点添加完毕后，返回根节点 `T`。 `preorder` 函数执行前序遍历，即先访问根节点，再遍历左子树，最后遍历右子树。这里使用了一个栈 `bitreestack`，当遍历到节点时，先输出节点数据，然后将其压入栈中，以备后续遍历右子树。当遍历完当前节点的所有子树后，弹出栈顶元素并继续处理其右子树。 `inorder` 函数则实现了中序遍历，遵循的原则是先遍历左子树，然后访问根节点，最后遍历右子树。同样使用栈辅助遍历，当节点不为空且栈不为空时，先将当前节点压入栈，然后递归处理左子树，直至栈为空。此时，从栈顶取出节点并访问，然后递归处理其右子树。 这段代码展示了如何用非递归方法构建二叉树，并提供了两种基本的遍历方式（前序和中序）。这对于理解和实现二叉树的非递归操作具有一定的指导意义，对于学习C语言数据结构和算法的同学来说是一个很好的示例。