-
定义二叉树节点（BTree）：
ElemType value：存储节点的值。struct BTree* LeftChild：指向左子节点的指针。struct BTree* RightChild：指向右子节点的指针。
-
节点访问函数（visit）：
- 用于在遍历过程中访问节点的值，这里简单地打印出来。
-
创建新节点函数（createNode）：
- 动态分配内存来创建一个新的节点，并初始化其值和子节点指针。
-
栈结构体（Stack）及其操作函数：
- 用于存储节点指针的栈，最大长度为100。
initStack：初始化栈。IsEmpty：检查栈是否为空。IsFull：检查栈是否已满。Push：将节点压入栈。Pop：从栈中弹出节点。
-
非递归遍历函数：
- 前序遍历（PreorderTraversalNonRecursive）：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。这里使用栈来模拟递归过程，先遍历左子树，然后处理根节点，最后处理右子树。
- 中序遍历（InorderTraversalNonRecursive）：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。使用栈来保证左子树先被处理。
- 后序遍历（PostorderTraversalNonRecursive）：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。这是最复杂的，因为它需要确保根节点是最后被访问的。这里使用了一个额外的指针
lastVisited来记录上一个访问的节点，以确保右子树在根节点之前被访问。
-
释放二叉树内存（freeTree）：
- 递归地释放每个节点的内存，以避免内存泄漏。
-
主函数（main）：
- 创建一个简单的二叉树，用于测试非递归遍历函数。
- 执行前序、中序和后序遍历，并打印结果。
- 释放二叉树占用的内存。
#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct BTree {ElemType value;struct BTree* LeftChild;struct BTree* RightChild;
} BTree;// 访问节点的函数
void visit(ElemType value) {printf("%d ", value);
}// 创建新节点
BTree* createNode(ElemType value) {BTree* newNode = (BTree*)malloc(sizeof(BTree));if (newNode == NULL) {printf("Memory allocation failed!\n");exit(1);}newNode->value = value;newNode->LeftChild = NULL;newNode->RightChild = NULL;return newNode;
}// 栈相关函数的声明
typedef struct Stack {BTree* elements[100]; // 假设栈最大长度为100int top;
} Stack;void initStack(Stack* S) {S->top = -1;
}int IsEmpty(Stack S) {return S.top == -1;
}int IsFull(Stack S) {return S.top == 99;
}void Push(Stack* S, BTree* p) {if (IsFull(*S)) {printf("Stack is full!\n");return;}S->elements[++S->top] = p;
}void Pop(Stack* S, BTree** p) {if (IsEmpty(*S)) {printf("Stack is empty!\n");return;}*p = S->elements[S->top--];
}// 前序遍历（非递归）
void PreorderTraversalNonRecursive(BTree* root) {Stack S;initStack(&S);BTree* node = root;while (node != NULL || !IsEmpty(S)) {while (node != NULL) {visit(node->value);Push(&S, node->RightChild);node = node->LeftChild;}if (!IsEmpty(S)) {Pop(&S, &node);}}
}// 中序遍历（非递归）
void InorderTraversalNonRecursive(BTree* root) {Stack S;initStack(&S);BTree* node = root;while (node != NULL || !IsEmpty(S)) {while (node != NULL) {Push(&S, node);node = node->LeftChild;}if (!IsEmpty(S)) {Pop(&S, &node);visit(node->value);node = node->RightChild;}}
}// 后序遍历（非递归）
void PostorderTraversalNonRecursive(BTree* root) {if (root == NULL) return;Stack S;initStack(&S);BTree* node = root;BTree* lastVisited = NULL;while (node != NULL || !IsEmpty(S)) {while (node != NULL) {Push(&S, node);node = node->LeftChild;}BTree* temp = NULL;if (!IsEmpty(S)) {temp = S.elements[S.top];if (temp->RightChild == NULL || temp->RightChild == lastVisited) {Pop(&S, &temp);visit(temp->value);lastVisited = temp;}else {node = temp->RightChild;}}}
}void freeTree(BTree* root) {if (root != NULL) {freeTree(root->LeftChild);freeTree(root->RightChild);free(root);}
}int main() {// 创建一个简单的二叉树进行测试BTree* root = createNode(1);root->LeftChild = createNode(2);root->RightChild = createNode(3);root->LeftChild->LeftChild = createNode(4);root->LeftChild->RightChild = createNode(5);root->RightChild->LeftChild = createNode(6);root->RightChild->RightChild = createNode(7);printf("Preorder traversal (non-recursive): ");PreorderTraversalNonRecursive(root);printf("\n");printf("Inorder traversal (non-recursive): ");InorderTraversalNonRecursive(root);printf("\n");printf("Postorder traversal (non-recursive): ");PostorderTraversalNonRecursive(root);printf("\n");// 释放内存freeTree(root);return 0;
}结果如下：
