本文主要实现C语言二叉树的构造，存储复杂数据类型，通过栈对其进行非递归遍历，有详细备注。
1 二叉树构造
typedef struct Student
{
int id;
char name[10];
} Student;
typedef struct Tree
{
Student *data;//暂存储Student*
struct Tree *left;
struct Tree *right;
} Tree;
2 根据数据data创建树节点
Tree *createTreeNode(Student *stu)
{
Tree *node = (Tree *)malloc(sizeof(Tree *));
node->left = NULL;
node->right = NULL;
node->data = stu;
}
3 中序遍历代码（文末有详细流程）
void inOrderList(Tree *root) //中序遍历，先左、后根、再右
{
Tree **stk = (Tree **)malloc(sizeof(Tree *) * SIZE); //向堆区申请内存构造栈，栈内存储节点地址Tree*
int top = 0;
while (root != NULL || top > 0) //当root==NULL且top==0说明栈内已经没有元素，且没有新元素再入栈，跳出循环
{
while (root != NULL) //一直入栈，直到root=NULL，
{
stk[top++] = root; //先是根节点入栈//栈顶索引top不断增加
root = root->left; //然后传入左子节点，左子树入栈//这样出栈时是左子树先出栈，根节点后出栈
} //循环结束时，root及root.left全部入栈//栈顶索引top比实际值大1
root = stk[--top]; //获取到栈顶的节点
//上2次陆续入栈的是root和root->left，栈顶获取的是后者
printf("{id:%d name:%s} ", root->data->id, root->data->name); //输出栈顶,输出root
root = root->right; //再将栈顶的右子节点传入循环
}
}
4 前序遍历代码
void preOrderList(Tree *root) //前序遍历，先根，后左，再右
{
Tree **stk = (Tree **)malloc(sizeof(Tree *) * SIZE); //向堆区申请内存构造栈，栈内存储节点地址Tree*
int top = 0;
while (root != NULL || top > 0) //当root==NULL且top==0说明栈内已经没有元素，且没有新元素再入栈，跳出循环
{
while (root != NULL) //一直入栈，直到root=NULL，
{
stk[top++] = root; //根节点入栈//栈顶索引top不断增加
printf("{id:%d name:%s} ", root->data->id, root->data->name); //输出栈顶root
root = root->left; //然后传入左子节点，左子树入栈//这样出栈时根节点先出，左子树再出栈
}
root = stk[--top]; //获取到栈顶的节点
root = root->right; //再将栈顶的右子节点传入循环，右子树入栈前相应节点左子树已完成出栈操作
}
}
5 后序遍历代码
- 中序遍历中，从栈中弹出的节点，其左子树是访问完了，可以直接访问该节点，然后接下来访问右子树。
- 后序遍历中，从栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。
- 因此，我们在后序遍历中，引入了一个preNode来记录历史访问记录。
- 当访问完一棵子树的时候，我们用preNode指向该节点。
- 这样，在回溯到父节点的时候，我们可以依据preNode是指向左子节点，还是右子节点，来判断父节点的访问情况。
- 主要思想如下：
- 由于在某颗子树访问完成以后，接着就要回溯到其父节点去
- 因此可以用prev来记录访问历史，在回溯到父节点时，可以由此来判断，上一个访问的节点是否为右子树
void postOrderList(Tree *root) //后序遍历，先左，后右，再根
{
Tree **stk = (Tree **)malloc(sizeof(Tree *) * SIZE); //向堆区申请内存构造栈，栈内存储节点地址Tree*
int top = 0;
Tree *preNode = NULL;
while (root != NULL || top > 0) //当root==NULL且top==0说明栈内已经没有元素，且没有新元素再入栈，跳出循环
{
while (root != NULL) //一直入栈，直到root=NULL，
{
stk[top++] = root; //根节点入栈//栈顶索引top不断增加
root = root->left; //然后传入左子节点，左子树入栈//这样出栈时是左子树先出栈，根节点后出栈
}
//从栈中弹出的元素，左子树一定是访问完了的
root = stk[--top]; //获取到栈顶的节点
//现在需要确定的是是否有右子树，或者右子树是否访问过
//如果没有右子树，或者右子树访问完了，也就是上一个访问的节点是右子节点时
//说明可以访问当前节点
if (root->right == NULL || root->right == preNode)
{
printf("{id:%d name:%s} ", root->data->id, root->data->name); //输出栈顶root
preNode = root; //更新历史访问记录，这样回溯的时候父节点可以由此判断右子树是否访问完成
root = NULL;
}
else //如果右子树没有被访问，那么将当前节点压栈，访问右子树
{
stk[top++] = root;
root = root->right;
}
}
}
6 总体测试代码
#include#include #define SIZE 100 typedef struct Student { int id; char name[10]; } Student; typedef struct Tree { Student *data; struct Tree *left; struct Tree *right; } Tree; Tree *createTreeNode(Student *stu) { Tree *node = (Tree *)malloc(sizeof(Tree *)); node->left = NULL; node->right = NULL; node->data = stu; } void inOrderList(Tree *root) //中序遍历，先左、后根、再右 { Tree **stk = (Tree **)malloc(sizeof(Tree *) * SIZE); //向堆区申请内存构造栈，栈内存储节点地址Tree* int top = 0; while (root != NULL || top > 0) //当root==NULL且top==0说明栈内已经没有元素，且没有新元素再入栈，跳出循环 { while (root != NULL) //一直入栈，直到root=NULL， { stk[top++] = root; //先是根节点入栈//栈顶索引top不断增加 root = root->left; //然后传入左子节点，左子树入栈//这样出栈时是左子树先出栈，根节点后出栈 } //循环结束时，root及root.left全部入栈//栈顶索引top比实际值大1 root = stk[--top]; //获取到栈顶的节点 //上2次陆续入栈的是root和root->left，栈顶获取的是后者 printf("{id:%d name:%s} ", root->data->id, root->data->name); //输出栈顶,输出root root = root->right; //再将栈顶的右子节点传入循环 } } void preOrderList(Tree *root) //前序遍历，先根，后左，再右 { Tree **stk = (Tree **)malloc(sizeof(Tree *) * SIZE); //向堆区申请内存构造栈，栈内存储节点地址Tree* int top = 0; while (root != NULL || top > 0) //当root==NULL且top==0说明栈内已经没有元素，且没有新元素再入栈，跳出循环 { while (root != NULL) //一直入栈，直到root=NULL， { stk[top++] = root; //根节点入栈//栈顶索引top不断增加 printf("{id:%d name:%s} ", root->data->id, root->data->name); //输出栈顶root root = root->left; //然后传入左子节点，左子树入栈//这样出栈时根节点先出，左子树再出栈 } root = stk[--top]; //获取到栈顶的节点 root = root->right; //再将栈顶的右子节点传入循环，右子树入栈前相应节点左子树已完成出栈操作 } } void postOrderList(Tree *root) //后序遍历，先左，后右，再根 { Tree **stk = (Tree **)malloc(sizeof(Tree *) * SIZE); //向堆区申请内存构造栈，栈内存储节点地址Tree* int top = 0; Tree *preNode = NULL; while (root != NULL || top > 0) //当root==NULL且top==0说明栈内已经没有元素，且没有新元素再入栈，跳出循环 { while (root != NULL) //一直入栈，直到root=NULL， { stk[top++] = root; //根节点入栈//栈顶索引top不断增加 root = root->left; //然后传入左子节点，左子树入栈//这样出栈时是左子树先出栈，根节点后出栈 } //从栈中弹出的元素，左子树一定是访问完了的 root = stk[--top]; //获取到栈顶的节点 //现在需要确定的是是否有右子树，或者右子树是否访问过 //如果没有右子树，或者右子树访问完了，也就是上一个访问的节点是右子节点时 //说明可以访问当前节点 if (root->right == NULL || root->right == preNode) { printf("{id:%d name:%s} ", root->data->id, root->data->name); //输出栈顶root preNode = root; //更新历史访问记录，这样回溯的时候父节点可以由此判断右子树是否访问完成 root = NULL; } else //如果右子树没有被访问，那么将当前节点压栈，访问右子树 { stk[top++] = root; root = root->right; } } } int main() { Student stu[7] = { {1, "jakes1"}, {2, "jakes2"}, {3, "jakes3"}, {4, "jakes4"}, {5, "jakes5"}, {6, "jakes6"}, {7, "jakes7"}, }; Tree *root = (Tree *)malloc(sizeof(Tree)); root->data = &stu[0]; root->left = createTreeNode(&stu[1]); root->right = createTreeNode(&stu[2]); root->left->left = createTreeNode(&stu[3]); root->left->left->right = createTreeNode(&stu[6]); root->right->left = createTreeNode(&stu[4]); root->right->right = createTreeNode(&stu[5]); //完成一棵树的构建 printf("中序遍历:n"); inOrderList(root); puts(""); printf("前序遍历:n"); preOrderList(root); puts(""); printf("后序遍历:n"); postOrderList(root); return 0; }
7 以中序遍历为例解析
主函数中构造的二叉树如下：
前序遍历通过栈实现，执行流程如下：（三种遍历方式均可通过这种方式理解）
main函数测试输出如下：
暑期编程PK赛 得CSDN机械键盘等精美礼品！
