二叉树遍历(非递归版)

xiaoxiao2021-02-28  134

问题描述: 以一定的方式输入数据(本文是以先序遍历的方式输入),程序根据数据进行解析,创建二叉树,然后对二叉树进行操作,主要操作包括以下几种:

求二叉树的高度先序遍历二叉树中序遍历二叉树后序遍历二叉树层序遍历二叉树

先序遍历: 根节点->左子树->右子树 中序遍历: 左子树->根节点->右子树 先序遍历: 左子树->右子树->根节点 层序遍历: 第一层(根节点)->第二层->第三次->….

PS: 1. 大家可以清楚的看到,先序,中序和后序是相对于根节点而言的 2. 非递归版代码描述起来比递归版略显复杂 3. 递归版本可以查看我的另外一篇文章: http://blog.csdn.net/yi_ming_he/article/details/71248881

以下面的例子进行说明:

如图所示,根据上面的遍历顺序,我们可以得到以下遍历结果: 先序遍历: 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; }

运行结果:

转载请注明原文地址: https://www.6miu.com/read-57489.html

最新回复(0)