王道数据结构 (11) 树的后序遍历非递归代码实现
2023-09-11 14:22:18 时间
代码实现:
#include <stdio.h> #include <string.h> #include <stdlib.h> #define ElementType char int top_S1 = -1; //定义栈S1 top下标 int top_S2 = -1; //定义栈S2 top下标 // 结点结构体 typedef struct BinTNode { ElementType data; struct BinTNode *left; struct BinTNode *right; } BinTNode, *BinTree; // 初始化树形结构 BinTNode *CreateBiTree(BinTNode *T) { T = (BinTNode *)malloc(sizeof(BinTNode)); T->data = 'A'; T->left = (BinTNode *)malloc(sizeof(BinTNode)); T->left->data = 'B'; T->right = (BinTNode *)malloc(sizeof(BinTNode)); T->right->data = 'C'; T->left->left = (BinTNode *)malloc(sizeof(BinTNode)); T->left->left->data = 'D'; T->left->right = (BinTNode *)malloc(sizeof(BinTNode)); T->left->right->data = 'E'; T->left->right->left = NULL; T->left->right->right = NULL; T->left->left->left = (BinTNode *)malloc(sizeof(BinTNode)); T->left->left->left->data = 'H'; T->left->left->left->left = NULL; T->left->left->left->right = NULL; T->left->left->right = (BinTNode *)malloc(sizeof(BinTNode)); T->left->left->right->data = 'I'; T->left->left->right->left = NULL; T->left->left->right->right = NULL; T->right->left = (BinTNode *)malloc(sizeof(BinTNode)); T->right->left->data = 'F'; T->right->left->left = NULL; T->right->left->right = NULL; T->right->right = (BinTNode *)malloc(sizeof(BinTNode)); T->right->right->data = 'G'; T->right->right->left = NULL; T->right->right->right = NULL; return T; } // 栈S1 - 进栈push void push_S1(BinTNode **stack, BinTNode *elem) { stack[++top_S1] = elem; } // 栈S2 - 进栈push void push_S2(BinTNode **stack, BinTNode *elem) { stack[++top_S2] = elem; } //栈S1 - 弹栈pop void pop_S1() { if (top_S1 == -1) { return; } top_S1--; } //栈S2 - 弹栈pop void pop_S2() { if (top_S2 == -1) { return; } top_S2--; } // 遍历过程中,输出结点值 void printElement(BinTNode *elem) { printf("%c ", elem->data); } //获取栈顶元素 BinTNode *getTop_S1(BinTNode **stack) { return stack[top_S1]; } //获取栈顶元素 BinTNode *getTop_S2(BinTNode **stack) { return stack[top_S2]; } //非递归遍历 - 左右根 void PostOrderTraverse(BinTNode *Tree) { BinTNode *S1[30]; // 辅助栈 BinTNode *S2[30]; BinTNode *T = Tree; // 定义临时指针 BinTNode *Temp; push_S1(S1, T); // 初始化S1的top元素是树的根结点 while (top_S1 != -1) { T = getTop_S1(S1); // S1的栈顶元素弹出 pop_S1(); // 栈顶元素弹栈 push_S2(S2, T); if (T->left != NULL || T->right != NULL) { // 栈顶元素有孩子结点 if (T->left != NULL) push_S1(S1, T->left); if (T->right != NULL) push_S1(S1, T->right); } } // 逐个弹出S2的元素 while (top_S2 != -1) { printElement(getTop_S2(S2)); pop_S2(); } } int main() { BinTNode *Tree; Tree = CreateBiTree(Tree); printf("后序遍历:\t"); PostOrderTraverse(Tree); printf("\n"); return 0; }
输出:
相关文章
- C++ 进程遍历(最简单)
- 数据结构基础 后序遍历和中序遍历还原二叉树
- Java实现二叉树及相关遍历方式
- Python递归文件夹遍历所有文件夹及文件
- 二叉树,二叉树的归先序遍历,中序遍历,后序遍历,递归和非递归实现
- 1053 Path of Equal Weight (30 分)【难度: 一般 / 树的遍历】
- C#类的属性遍历及属性值获取
- 漏洞复现----35、uWSGI PHP 目录遍历漏洞 (CVE-2018-7490)
- 力扣解法汇总589- N 叉树的前序遍历
- JS高阶---闭包(循环遍历+监听)
- ES9的新特性:异步遍历Async iteration
- 数据结构 | 二叉线索树——创建中序二叉线索树、查找前驱、查找后继、按照前驱或后继遍历
- 【数据结构/二叉树/二叉树遍历】题解+详细备注(共14题)
- JavaScript 的 4 种数组遍历方法: for VS forEach() VS for/in VS for/of
- Delphi 遍历类中的属性
- robot:循环遍历数据库查询结果是否满足要求
- 遍历当前USB设备信息
- 王道数据结构 (9) 树的中序遍历非递归代码实现
- Python 遍历Sheet 每个Sheet都单独保存为一个Excel
- twonkyserver 目录遍历(CVE-2018-7171)漏洞复现【VULFOCUS靶场-初级】
- Java 遍历Map的2种方法(KeySet、EntrySet)