二叉树中阶，前阶和后阶的递归和非递归遍历算法，层级非递归遍历算法的实现

#ifndef TREE_H#定义TREE_H #include #include #include #include #include 使用命名空间std; typedef int ElemType; typedef struct treeT {ElemType键； struct treeT *左； struct treeT * right;} treeT，* pTreeT; / ** // * ============================================ ============================= * *函数名称: 访问*参数: root: 树根节点指针*前提: *描述: *返回值: *作者: 刘琦，//-==================================== ===================================== * /静态无效访问（pTreeT根）{if （NULL！= root）{printf（“％d \ n”，root->键）;}} / ** // * ==================== ================================================== ===== *函数名称: BT_MakeNode *参数: target: 元素值*前提条件: 无*前提条件: NULL！ = PTreeT *描述: 构造一个树节点，将左指针和右指针留空，然后将指针返回到新节点*返回值: 指向新节点的指针*作者: 刘琦，[12/30/2005] == = ================================================== = / =静态pTreeT BT_MakeNode（ElemType目标）（pTreeT pNode =（pTreeT）malloc（sizeof（treeT））;断言（NULL ！= pNode）; pNode->键=目标; pNode->左= NULL; pNode->右= NULL;返回pNode;} / ** // * =============== = ================================================== = ========= * *函数名称: BT_Insert *参数: target: 要插入的元素的值，pNode: 指向某个节点的指针*前提: NULL！= PpTree *描述: 在之后插入目标pNode *返回值: 指向新节点的指针*作者: 刘琦，[12/29/2005] ============================= =========================================== * / pTreeT BT_Insert（ElemType目标，pTreeT * ppTree）（pTreeT节点;断言（NULL！= PpTree）; N ode = * ppTree; if（NULL ==节点）（return * ppTree = BT_MakeNode（target）;）if（Node-> key == target）//不允许同一个元素{return NULL;} else if（Node-> key> target ）//向左（返回BT_Insert（目标和节点->左）；}其他{返回BT_Insert（目标和节点->右）;}} / ** // * =========== ================================================== ============== * *函数名称: BT_PreOrder *参数: root: 树根节点指针*前提: 无*说明: 遍历*返回值: void *作者: Liu Qi，[ 2005年12月29日] ============================================= ============================= * / void BT_PreOrder（pTreeT root）{if（NULL！= root）（访问（ root）; BT_PreOrder（root-> left）; BT_PreOrder（root-> right）;}} / ** // * ====================== ================================================= ====== *函数名称: BT_PreOrderNoRec *参数: root: 树根节点指针*先决条件: 节点*描述: 预遍历（第一个根）遍历非递归算法thm *返回值: void *作者: 刘琦递归 2次调用，[1/1/2006] =============================== = ======================================== * /无效BT_PreOrderNoRec（pTreeT root）{stack s; while（（（NULL！= root）||！s.empty（））（如果（NULL！= root）{访问（root）; s.push（root）; root = root-> left;}否则{root = s.top（）; s.pop（）; root = root-> right;}}} / ** // * ===================== ================================================= ==== *函数名称: BT_InOrder *参数: root: 树根节点指针*前提: 无*描述: 中阶遍历*返回值: void *作者: 刘琦，[12/30/2005] === ================================================== * / void BT_InOrder（pTreeT root）{if（NULL！= root）{BT_InOrder（root-> left）; visit（root） ）; BT_InOrder（root-> right）;}} / ** // * ================================ ========================================= *功能名称: BT_InOrderNoRec *参数: root: 指向树的根节点的指针*前提: 无*描述: 中级遍历，非递归算法*返回值: void *作者: 刘琦，[1/1/2006] ===== ====== ============================================ == = / = BT_InOrderNoRec（pTreeT根）{stack s; while（（（NULL！= root）||！s.empty（））{if（NULL！= Root）{s.push（root）; root = root-> left;}否则{root = s.top（）;访问（根）； s.pop（）; root = root-> right;}}} / ** // * ================================= ======================================= *功能名称: BT_PostOrder *参数: root : 树根节点指针*前提: 无*描述: 后遍历*返回值: void *作者: 刘琦，[12/30/2005] ================ ================================================== ======== * / void BT_PostOrder（pTreeT根）{if（NULL！=根）（BT_PostOrder（根->左）； BT_PostOrder（根->右）；访问（根）；}} / ** // * =============================================== ================================ * *函数名称: BT_PostOrderNoRec *参数: root: 树根节点指针*前提条件: 无*描述: 后遍历，非递归算法*返回值: void *作者: 刘琦，// [1/1/2006] ================ ================================================== = ======= = * /无效BT_PostOrderNoRec（pTreeT根目录）{//正在研究中，尚未理解} / ** // * ================= = ============ ========================================= *功能名称: BT_LevelOrder *参数: root: 树根节点指针*前提: NULL！ =根*说明: 序列遍历*返回值: 空*作者: 刘琦，[1/1/2006] ========================= ================================================== * / void BT_LevelOrder（pTreeT根）（队列 q; treeT * treePtr;断言（NULL！=根）; q.push（根）; while（！q.empty（））（treePtr = q.front （）; q.pop（）;访问（treePtr）; if（NULL！= treePtr-> left）（q.push（treePtr-> left）;} if（NULL！= treePtr-> right）{q.push （treePtr->正确）；}}} #endif测试代码#include #include #include #include“ tree.h” #define MAX_CNT 5 #define BASE 100 int main（int argc，char * argv []）{int i; pTreeT root = NULL; srand（（unsigned）time（NULL））; for（i = 0; i 递归 2次调用，分层（包括递归和非递归实现） 2006-01-03 23:09 PIGWORLD编写了一个非递归的后遍历实现，直接编写，未经验证，估计没有大问题. 让我们看一下这个想法: 首先找到最左边的叶子并按顺序推入堆栈上遇到的节点，然后将元素弹出堆栈顶部（该元素是最左边的叶子），并确定（1）它是否具有右节点； （2）是否访问过正确的节点.

如果（1）有一个右节点，但尚未访问（2），请首先按一下刚刚弹出的元素，然后按其右子树. 否则，请访问该节点并设置pre来更改该节点. void BT_PostOrderNoRec（pTreeT根）{stack s; s.push（root）; while（root！= 0 ||！s.isEmpty（））{//找到最左边的叶子while（（root = root-> left）！= 0）{s.push（root）;} pTree pre; //记录先前访问的节点root = s.pop（）; //弹出堆栈的顶部元素//如果右边的子树不为空，并且右边的子树未被访问，//然后（在内部while循环中）如果（root-> right！= 0 && pre！= Root-> right）{//放置最后一句话s.push（根）中的弹出元素； root = root-> right; s.push（root）;} //否则否则{弹出栈顶节点，访问它，并将pre设置为该节点root = pre = s.pop（）;访问（根）； //将root设为0，以避免进入内部循环root = 0;}}回复更多评论#re: 遍历二叉树: 前置，中阶，后置，层包含递归和非递归实现的序列2006-09-08 17:22 247 * * * *###回复更多评论#re: 遍历二叉树: 前序，中序，后序，包括递归和非递归实现的序列2006-09-12 1 4 : 54 Passerby void BT_PostOrderNoRec（pTreeT root）{stack s; pTreeT pre = NULL; while（（（NULL！= Root）||！S.empty（））{if（NULL！= Root）{s.push（root）; root = root-> left;}否则{root = s.top（）; if（root-> right！= NULL && pre！= root-> right）{root = root-> right;} else {root = pre = s.top（）;访问（根）； s.pop（）; root = NULL;}}}}回复更多评论#re: 遍历二叉树: 前置，中阶，后置，包含递归和非递归实现的序列2006-09-12 14:57基于在成功调试之后，lz和先前人员的代码现在如下所示: void BT_PostOrderNoRec（pTreeT根）{stack s; pTreeT pre = NULL; while（（（NULL！= root）||！s.empty（））{if（NULL！= root）{s.push（root）; root = root-> left;}否则{root = s.top（）; if（root-> right！= NULL && pre！= root-> right）{root = root-> right;} else {root = pre = s.top（）;访问（根）； s.pop（）; root = NULL;}}}}回复更多评论#re: 遍历二叉树: 前置，中阶，后置，包括递归和非递归实现的序列2007-09-12 12:11 Passerby B is像POP一样对前面的人失去了两个答复一个评论#re: 遍历二叉树: 前置，中阶，后阶，层次结构，包括递归和非递归实现2008-01-09 21 : 33 ^^也许更好: void BT_PostOrderNoRec（pTreeT root）{stack s; pTreeT pre = NULL; pTreeT top = NULL; while（（（NULL！= root）||！s.empty（））{if（NULL！= root）{s.push（root）; root = root-> right;}否则{top = s.top（）;如果（top-> left！= NULL && top-> left！= pre）root = top-> left;其他{访问（顶部）； s.pop（）; pre = top;}}}}回复更多评论#re: 遍历二叉树: 前，中，后，包括递归和非递归实现的层次结构2008-01-09 21:46 ^ ^抱歉，它是: void BT_PostOrderNoRec（pTreeT root）{stack s; pTreeT pre = NULL; pTreeT top = NULL; while（（（NULL！= root）||！s.empty（））{if（NULL！= root）{s.push（root）; root = root-> left;} e lse {top = s.top（）;如果（top-> right！= NULL && top-> right！= pre）root = top-> right;其他{访问（顶部）； pre =顶部； s.pop（）;}}}}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-167527-1.html