二叉树遍历（非递归版） 谁践踏了优雅 2022-06-16 05:16 192阅读 0赞 问题描述： 以一定的方式输入数据（本文是以先序遍历的方式输入），程序根据数据进行解析，创建二叉树，然后对二叉树进行操作，主要操作包括以下几种： 1. 求二叉树的高度 2. 先序遍历二叉树 3. 中序遍历二叉树 4. 后序遍历二叉树 5. 层序遍历二叉树 先序遍历： 根节点->左子树->右子树 中序遍历： 左子树->根节点->右子树 先序遍历： 左子树->右子树->根节点 层序遍历： 第一层（根节点）->第二层->第三次->…. PS： 1. 大家可以清楚的看到，先序，中序和后序是相对于根节点而言的 2. 非递归版代码描述起来比递归版略显复杂 3. 递归版本可以查看我的另外一篇文章： [http://blog.csdn.net/yi\_ming\_he/article/details/71248881][http_blog.csdn.net_yi_ming_he_article_details_71248881] 以下面的例子进行说明： ![这里写图片描述][SouthEast] 如图所示，根据上面的遍历顺序，我们可以得到以下遍历结果： 先序遍历： a b d h e c f g 中序遍历： h d b e a f c g 后序遍历： h d e b f g c a 层序遍历： a b c d e f g h 参考代码： #include <stdio.h> #include <malloc.h> #include <string.h> #include <queue> #include <stack> #define MAXNODE 1024 char str[MAXNODE]; typedef struct BiTNode { char data; struct BiTNode* lchild; struct BiTNode* rchild; }BiTNode, *Bitree; void CreateBiTree(Bitree& T) { //这是根据先序遍历建立的一棵树 scanf_s("%s", str, MAXNODE); Bitree tempT, tempQ; T = (Bitree)malloc(sizeof(BiTNode)); T->data = str[0]; T->lchild = NULL; T->rchild = NULL; std::stack<Bitree>st; st.push(T); for (int i = 1; i < (int)strlen(str); i++) { if (str[i] == '#') { tempT = st.top(); st.pop(); if (NULL == tempT->lchild) i++; } else { tempT = st.top(); tempQ = (Bitree)malloc(sizeof(BiTNode)); tempQ->data = str[i]; tempQ->lchild = NULL; tempQ->rchild = NULL; if (tempT->lchild) { tempT->rchild = tempQ; st.pop(); } else tempT->lchild = tempQ; st.push(tempQ); } } } void PreOrderTraverseByNonRecursion(Bitree T) { if (!T) return; std::stack<std::pair<Bitree, bool>> st; st.push(std::make_pair(T, false)); bool bVisited = false; while (!st.empty()) { T = st.top().first; bVisited = st.top().second; st.pop(); if (!T) continue; if (bVisited) printf("%c ", T->data); else { st.push(std::make_pair(T->rchild, false)); st.push(std::make_pair(T->lchild, false)); st.push(std::make_pair(T, true)); } } } void InOrderTraverseByNonRecursion(Bitree T) { if (!T) return; std::stack<std::pair<Bitree, bool>> st; st.push(std::make_pair(T, false)); bool bVisited = false; while (!st.empty()) { T = st.top().first; bVisited = st.top().second; st.pop(); if (!T) continue; if (bVisited) printf("%c ", T->data); else { st.push(std::make_pair(T->rchild, false)); st.push(std::make_pair(T, true)); st.push(std::make_pair(T->lchild, false)); } } } void PostOrderTraverseByNonRecursion(Bitree T) { if (!T) return; std::stack<std::pair<Bitree, bool>> st; st.push(std::make_pair(T, false)); bool bVisited = false; while (!st.empty()) { T = st.top().first; bVisited = st.top().second; st.pop(); if (!T) continue; if (bVisited) printf("%c ", T->data); else { st.push(std::make_pair(T, true)); st.push(std::make_pair(T->rchild, false)); st.push(std::make_pair(T->lchild, false)); } } } int GetBiTreeHeightByNonRecursion(Bitree T) { if (!T) return 0; int nVisitedNodeCount = 0;//已经访问过的节点数 int nPushQueueNumber = 1;//记录入队列的节点的最大序号 int nLevelMaxNumber = 1;//记录每一次的最大的序号 int nTreeHeight = 0;//记录树的高度 std::queue<Bitree> Q; Q.push(T); while (!Q.empty()) { T = Q.front(); Q.pop(); nVisitedNodeCount++; if (T->lchild) { Q.push(T->lchild); nPushQueueNumber++; } if (T->rchild) { Q.push(T->rchild); nPushQueueNumber++; } if (nVisitedNodeCount == nLevelMaxNumber) { nTreeHeight++; nLevelMaxNumber = nPushQueueNumber; } } return nTreeHeight; } void LevelOrderTraverseByNonRecursion(Bitree T) { if (!T) return; std::queue<Bitree> Q; Q.push(T); while (!Q.empty()) { T = Q.front(); Q.pop(); printf("%c ", T->data); if (T->lchild) Q.push(T->lchild); if (T->rchild) Q.push(T->rchild); } } int main() { Bitree T; CreateBiTree(T); printf("树的高度是: %d\n", GetBiTreeHeightByNonRecursion(T)); printf("先序遍历(非递归)：\n"); PreOrderTraverseByNonRecursion(T); printf("\n"); printf("中序遍历(非递归)：\n"); InOrderTraverseByNonRecursion(T); printf("\n"); printf("后序遍历(非递归)：\n"); PostOrderTraverseByNonRecursion(T); printf("\n"); printf("层序遍历(非递归)：\n"); LevelOrderTraverseByNonRecursion(T); printf("\n"); return 0; } 运行结果： ![这里写图片描述][SouthEast 1] [http_blog.csdn.net_yi_ming_he_article_details_71248881]: http://blog.csdn.net/yi_ming_he/article/details/71248881 [SouthEast]: /images/20220616/22f54d233ec6475caf7c01b638674698.png [SouthEast 1]: /images/20220616/590d77bb6c1048a4a47501f5e12d8c23.png
还没有评论，来说两句吧...