网站优化seo网站架构优化,怎样用电脑做网站,简述网站设计流程,wordpress增加模板转载于 二叉树是一种非常重要的数据结构#xff0c;很多其他数据机构都是基于二叉树的基础演变过来的。二叉树有前、中、后三种遍历方式#xff0c;因为树的本身就是用递归定义的#xff0c;因此采用递归的方法实现三种遍历#xff0c;不仅代码简洁…转载于 二叉树是一种非常重要的数据结构很多其他数据机构都是基于二叉树的基础演变过来的。二叉树有前、中、后三种遍历方式因为树的本身就是用递归定义的因此采用递归的方法实现三种遍历不仅代码简洁且容易理解但其开销也比较大而若采用非递归方法实现三种遍历则要用栈来模拟实现递归也是用栈实现的。下面先简要介绍三种遍历方式的递归实现再详细介绍三种遍历方式的非递归实现。 一、三种遍历方式的递归实现比较简单这里不详细讲解 1、先序遍历——按照“根节点-左孩子-右孩子”的顺序进行访问。 1 void pre_traverse(BTree pTree)2 {3 if(pTree)4 {5 printf(%c ,pTree-data);6 if(pTree-pLchild)7 pre_traverse(pTree-pLchild);8 if(pTree-pRchild)9 pre_traverse(pTree-pRchild);
10 }
11 } 2、中序遍历——按照“左孩子-根节点-右孩子”的顺序进行访问。 1 void in_traverse(BTree pTree)2 {3 if(pTree)4 {5 if(pTree-pLchild)6 in_traverse(pTree-pLchild);7 printf(%c ,pTree-data);8 if(pTree-pRchild)9 in_traverse(pTree-pRchild);
10 }
11 } 3、后序遍历——按照“左孩子-右孩子-根节点”的顺序进行访问。 1 void beh_traverse(BTree pTree)2 {3 if(pTree)4 {5 if(pTree-pLchild)6 beh_traverse(pTree-pLchild);7 if(pTree-pRchild)8 beh_traverse(pTree-pRchild); 9 printf(%c ,pTree-data);
10 } 二、三种遍历方式的非递归实现 为了便于理解这里以下图的二叉树为例分析二叉树的三种遍历方式的实现过程。 1、前序遍历的非递归实现 根据先序遍历的顺序先访问根节点再访问左子树后访问右子树而对于每个子树来说又按照同样的访问顺序进行遍历上图的先序遍历顺序为ABDECF。非递归的实现思路如下 对于任一节点P 1输出节点P然后将其入栈再看P的左孩子是否为空 2若P的左孩子不为空则置P的左孩子为当前节点重复1的操作 3若P的左孩子为空则将栈顶节点出栈但不输出并将出栈节点的右孩子置为当前节点看其是否为空 4若不为空则循环至1操作 5如果为空则继续出栈但不输出同时将出栈节点的右孩子置为当前节点看其是否为空重复4和5操作 6直到当前节点P为NULL并且栈空遍历结束。 下面以上图为例详细分析其先序遍历的非递归实现过程 首先从根节点A开始根据操作1输出A并将其入栈由于A的左孩子不为空根据操作2将B置为当前节点再根据操作1将B输出并将其入栈由于B的左孩子也不为空根据操作2将D置为当前节点再根据操作1输出D并将其入栈此时输出序列为ABD 由于D的左孩子为空根据操作3将栈顶节点D出栈但不输出并将其右孩子置为当前节点 由于D的右孩子为空根据操作5继续将栈顶节点B出栈但不输出并将其右孩子置为当前节点 由于B的右孩子E不为空根据操作1输出E并将其入栈此时输出序列为ABDE 由于E的左孩子为空根据操作3将栈顶节点E出栈但不输出并将其右孩子置为当前节点 由于E的右孩子为空根据操作5继续将栈顶节点A出栈但不输出并将其右孩子置为当前节点 由于A的右孩子C不为空根据操作1输出C并将其入栈此时输出序列为ABDEC 由于A的左孩子F不为空根据操作2则将F置为当前节点再根据操作1输出F并将其入栈此时输出序列为ABDECF 由于F的左孩子为空根据操作3将栈顶节点F出栈但不输出并将其右孩子置为当前节点 由于F的右孩子为空根据操作5继续将栈顶元素C出栈但不输出并将其右孩子置为当前节点 此时栈空且C的右孩子为NULL因此遍历结束。 根据以上思路前序遍历的非递归实现代码如下 1 void pre_traverse(BTree pTree)2 {3 PSTACK stack create_stack(); //创建一个空栈4 BTree node_pop; //用来保存出栈节点5 BTree pCur pTree; //定义用来指向当前访问的节点的指针6 7 //直到当前节点pCur为NULL且栈空时循环结束8 while(pCur || !is_empty(stack))9 {
10 //从根节点开始输出当前节点并将其入栈
11 //同时置其左孩子为当前节点直至其没有左孩子及当前节点为NULL
12 printf(%c , pCur-data);
13 push_stack(stack,pCur);
14 pCur pCur-pLchild;
15 //如果当前节点pCur为NULL且栈不空则将栈顶节点出栈
16 //同时置其右孩子为当前节点,循环判断直至pCur不为空
17 while(!pCur !is_empty(stack))
18 {
19 pCur getTop(stack);
20 pop_stack(stack,node_pop);
21 pCur pCur-pRchild;
22 }
23 }
24 } 2、中序遍历的非递归实现 根据中序遍历的顺序先访问左子树再访问根节点后访问右子树而对于每个子树来说又按照同样的访问顺序进行遍历上图的中序遍历顺序为DBEAFC。非递归的实现思路如下 对于任一节点P 1若P的左孩子不为空则将P入栈并将P的左孩子置为当前节点然后再对当前节点进行相同的处理 2若P的左孩子为空则输出P节点而后将P的右孩子置为当前节点看其是否为空 3若不为空则重复1和2的操作 4若为空则执行出栈操作输出栈顶节点并将出栈的节点的右孩子置为当前节点看起是否为空重复3和4的操作 5直到当前节点P为NULL并且栈为空则遍历结束。 下面以上图为例详细分析其中序遍历的非递归实现过程 首先从根节点A开始A的左孩子不为空根据操作1将A入栈接着将B置为当前节点B的左孩子也不为空根据操作1将B也入栈接着将D置为当前节点由于D的左子树为空根据操作2输出D 由于D的右孩子也为空根据操作4执行出栈操作将栈顶结点B出栈并将B置为当前节点此时输出序列为DB 由于B的右孩子不为空根据操作3将其右孩子E置为当前节点由于E的左孩子为空根据操作1输出E此时输出序列为DBE 由于E的右孩子为空根据操作4执行出栈操作将栈顶节点A出栈并将节点A置为当前节点此时输出序列为DBEA 此时栈为空但当前节点A的右孩子并不为NULL继续执行由于A的右孩子不为空根据操作3将其右孩子C置为当前节点由于C的左孩子不为空根据操作1将C入栈将其左孩子F置为当前节点由于F的左孩子为空根据操作2输出F此时输出序列为DBEAF 由于F的右孩子也为空根据操作4执行出栈操作将栈顶元素C出栈并将其置为当前节点此时的输出序列为DBEAFC 由于C的右孩子为NULL且此时栈空根据操作5遍历结束。 根据以上思路中序遍历的非递归实现代码如下 1 void in_traverse(BTree pTree)2 {3 PSTACK stack create_stack(); //创建一个空栈4 BTree node_pop; //用来保存出栈节点5 BTree pCur pTree; //定义指向当前访问的节点的指针6 7 //直到当前节点pCur为NULL且栈空时循环结束8 while(pCur || !is_empty(stack))9 {
10 if(pCur-pLchild)
11 {
12 //如果pCur的左孩子不为空则将其入栈并置其左孩子为当前节点
13 push_stack(stack,pCur);
14 pCur pCur-pLchild;
15 }
16 else
17 {
18 //如果pCur的左孩子为空则输出pCur节点并将其右孩子设为当前节点看其是否为空
19 printf(%c , pCur-data);
20 pCur pCur-pRchild;
21 //如果为空且栈不空则将栈顶节点出栈并输出该节点
22 //同时将它的右孩子设为当前节点继续判断直到当前节点不为空
23 while(!pCur !is_empty(stack))
24 {
25 pCur getTop(stack);
26 printf(%c ,pCur-data);
27 pop_stack(stack,node_pop);
28 pCur pCur-pRchild;
29 }
30 }
31 }
32 } 3、后序遍历的非递归实现 根据后序遍历的顺序先访问左子树再访问右子树后访问根节点而对于每个子树来说又按照同样的访问顺序进行遍历上图的后序遍历顺序为DEBFCA。后序遍历的非递归的实现相对来说要难一些要保证根节点在左子树和右子树被访问后才能访问思路如下 对于任一节点P 1先将节点P入栈 2若P不存在左孩子和右孩子或者P存在左孩子或右孩子但左右孩子已经被输出则可以直接输出节点P并将其出栈将出栈节点P标记为上一个输出的节点再将此时的栈顶结点设为当前节点 3若不满足2中的条件则将P的右孩子和左孩子依次入栈当前节点重新置为栈顶结点之后重复操作2 4直到栈空遍历结束。 下面以上图为例详细分析其后序遍历的非递归实现过程 首先设置两个指针Cur指针指向当前访问的节点它一直指向栈顶节点每次出栈一个节点后将其重新置为栈顶结点Pre节点指向上一个访问的节点 Cur首先指向根节点APre先设为NULL由于A存在左孩子和右孩子根据操作3先将右孩子C入栈再将左孩子B入栈Cur改为指向栈顶结点B 由于B的也有左孩子和右孩子根据操作3将E、D依次入栈Cur改为指向栈顶结点D 由于D没有左孩子也没有右孩子根据操作2直接输出D并将其出栈将Pre指向DCur指向栈顶结点E此时输出序列为D 由于E也没有左右孩子根据操作2输出E并将其出栈将Pre指向ECur指向栈顶结点B此时输出序列为DE 由于B的左右孩子已经被输出即满足条件PreCur-lchild或PreCur-rchild根据操作2输出B并将其出栈将Pre指向BCur指向栈顶结点C此时输出序列为DEB 由于C有左孩子根据操作3将其入栈Cur指向栈顶节点F 由于F没有左右孩子根据操作2输出F并将其出栈将Pre指向FCur指向栈顶结点C此时输出序列为DEBF 由于C的左孩子已经被输出即满足PreCur-lchild根据操作2输出C并将其出栈将Pre指向CCur指向栈顶结点A此时输出序列为DEBFC 由于A的左右孩子已经被输出根据操作2输出A并将其出栈此时输出序列为DEBFCA 此时栈空遍历结束。 根据以上思路后序遍历的非递归实现代码如下 1 void beh_traverse(BTree pTree)2 {3 PSTACK stack create_stack(); //创建一个空栈4 BTree node_pop; //用来保存出栈的节点5 BTree pCur; //定义指针指向当前节点6 BTree pPre NULL; //定义指针指向上一各访问的节点7 8 //先将树的根节点入栈9 push_stack(stack,pTree);
10 //直到栈空时结束循环
11 while(!is_empty(stack))
12 {
13 pCur getTop(stack); //当前节点置为栈顶节点
14 if((pCur-pLchildNULL pCur-pRchildNULL) ||
15 (pPre!NULL (pCur-pLchildpPre || pCur-pRchildpPre)))
16 {
17 //如果当前节点没有左右孩子或者有左孩子或有孩子但已经被访问输出
18 //则直接输出该节点将其出栈将其设为上一个访问的节点
19 printf(%c , pCur-data);
20 pop_stack(stack,node_pop);
21 pPre pCur;
22 }
23 else
24 {
25 //如果不满足上面两种情况,则将其右孩子左孩子依次入栈
26 if(pCur-pRchild ! NULL)
27 push_stack(stack,pCur-pRchild);
28 if(pCur-pLchild ! NULL)
29 push_stack(stack,pCur-pLchild);
30 }
31 }
32 } 以上遍历算法在VC上实现的输出结果如下 二叉树的层序遍历 二叉树的层序遍历的实现还是比较简单的由于其层级的关系很明显要用到队列来辅助实现主要是从左向右自上而下依次将二叉树的各节点入队这样便可以保证输出的顺序是层序排列的。下面是算法的实现思想 先将树的根节点入队 如果队列不空则进入循环 { 将队首元素出队并输出它 如果该队首元素有左孩子则将其左孩子入队 如果该队首元素有右孩子则将其右孩子入队 } C语言代码如下 1 void LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType))2 {3 //Visit是对节点操作的应用函数,4 //在这里对每个数据元素调用函数Visit,也即是遍历了该节点 5 SqQueue q;6 QElemType p;7 if(T)8 {9 InitQueue(q);
10 EnQueue(q,T);
11 while(!QueueEmpty(q))
12 {
13 DeQueue(q,p);
14 Visit(p-data);
15 if(p-lchild!NULL) EnQueue(q,p-lchild);
16 if(p-rchild!NULL) EnQueue(q,p-rchild);
17 }
18 printf(/n);
19 }
20 } 转载于:https://www.cnblogs.com/00isok/p/9871574.html
