精华内容
下载资源
问答
  • 二叉树的非递归前、中、后序遍历算法详解及代码实现(C语言) 1. 前序遍历和中序遍历非递归算法思路 前序和中序非递归遍历的C代码 2. 后序遍历非递归算法思路 后序非递归遍历的C代码 1. 前序遍历和中序遍历...

    二叉树的非递归前、中、后序遍历算法详解及代码实现(C语言)

    1. 前序遍历和中序遍历非递归算法思路

    前序和中序非递归遍历的C代码

    2. 后序遍历非递归算法思路

    后序非递归遍历的C代码


    1. 前序遍历和中序遍历非递归算法思路

    遍历过程:(如图所示)

    图1 前序遍历和中序遍历流程图

     

    从当前节点开始遍历:(当入栈时访问节点内容,则为前序遍历;出栈时访问,则为中序遍历)

    1. 若当前节点存在,就存入栈中,并访问左子树;

    2. 直到当前节点不存在,就出栈,并通过栈顶节点访问右子树;

    3. 不断重复12,直到当前节点不存在且栈空。

     

    Tips:我们很容易发现,在理解并写好该非递归遍历代码后,只需要在入栈、出栈的时候,分别进行节点访问输出,即可分别得到前序、中序的非递归遍历代码!!!

     

    便于理解的伪代码:

    
     
    1. void preOrder(TreeNode *T){

    2.     p = T

    3.     while(p不空||栈不空){

    4.         if(p不空){      //两种情况:1.栈不空;2.栈空

    5.             p入栈;

    6.             (前序遍历,访问)

    7.             入p左子节点;

    8.         }else{            //一种情况:当前节点为空,但栈不空

    9.             p=出栈;

    10.             (中序遍历,访问)

    11.             入p右子节点;

    12.         }

    13.     }

    14. }

    前序和中序非递归遍历的C代码

    二叉树节点结构体:

    
     
    1. typedef struct TreeNode{

    2. int data;

    3. struct TreeNode *lChild;

    4. struct TreeNode *rChild;

    5. }TreeNode;

    前序遍历非递归:

    
     
    1. void preOrder(TreeNode *T){

    2. TreeNode *stack[15];

    3. int top = -1;

    4. TreeNode *p = T;

    5. while(p!=NULL||top!=-1){

    6. if(p!=NULL){

    7. stack[++ top] = p;

    8. printf("%d\t",p->data); //入栈时,访问输出

    9. p = p->lChild;

    10. }else{

    11. p = stack[top --];

    12. p = p->rChild;

    13. }

    14. }

    15. }

    中序遍历非递归:

    
     
    1. void inOrder(TreeNode *T){

    2. TreeNode *stack[15];

    3. int top = -1;

    4. TreeNode *p = T;

    5. while(p!=NULL||top!=-1){

    6. if(p!=NULL){

    7. stack[++ top] = p;

    8. p = p->lChild;

    9. }else{

    10. p = stack[top --];

    11. printf("%d\t",p->data); //出栈时,访问输出

    12. p = p->rChild;

    13. }

    14. }

    15. }

    2. 后序遍历非递归算法思路

    后序遍历整体与前中序遍历过程相似。但要注意,这时对于父节点的访问输出,需要在其右子树遍历完成的前提下进行。所以不能像前中序遍历一样,在遍历完左子树后,就直接出栈。我们需要利用这个未出栈的栈顶元素去获取右子树,在遍历完右子树后,就可以出栈,并对此节点进行访问输出。

    这里我们需要使用一个标记,以区分是从左子树取栈还是从右子树出栈:(如图所示)

    图2 后序遍历流程图

     

    从当前节点开始遍历:

    1. 若当前节点存在,就存入栈中,并且置节点flag为1(第一次访问),然后访问其左子树;

    2. 直到当前节点不存在,需要回退,这里有两种情况:

           1)当栈顶节点flag为1时,则表明是从左子树回退,这时需置栈顶节点flag为2(第二次访问),然后通过栈顶节点访问其右子树(取栈顶节点用,但不出栈)

           2)当栈顶节点flag为2时,则表明是从右子树回退,这时需出栈,并取出栈节点做访问输出。(需要注意的是,输出完毕需要置当前节点为空,以便继续回退。具体可参考代码中的p = NULL)

    3. 不断重复12,直到当前节点不存在且栈空。

     

    Tips:我们很容易发现,当理解并写好后序遍历非递归代码后,只需要在入栈、取栈、出栈的时候,分别进行节点访问输出,即可分别得到前序、中序、后序的非递归遍历代码,是不是非常简单!!!

     

    后序非递归遍历的C代码

    节点结构体:

    
     
    1. typedef struct TreeNode{

    2. int data;

    3. struct TreeNode *lChild;

    4. struct TreeNode *rChild;

    5. }TreeNode;

    后序遍历非递归:

    
     
    1. void postOrder(TreeNode *T){

    2. TreeNode *stack[15];

    3. int top = -1;

    4. int flagStack[15]; //记录每个节点访问次数栈

    5. TreeNode *p = T;

    6. while(p!=NULL||top!=-1){

    7. if(p!=NULL){ //第一次访问,flag置1,入栈

    8. stack[++ top] = p;

    9. flagStack[top] = 1;

    10. p = p->lChild;

    11. }else{//(p == NULL)

    12. if(flagStack[top] == 1){ //第二次访问,flag置2,取栈顶元素但不出栈

    13. p = stack[top];

    14. flagStack[top] = 2;

    15. p = p->rChild;

    16. }else{ //第三次访问,出栈

    17. p = stack[top --];

    18. printf("%d\t",p->data); //出栈时,访问输出

    19. p = NULL; //p置空,以便继续退栈

    20. }

    21. }

    22. }

    23. }

     

    展开全文
  • 二叉树后序遍历(非递归)算法实现--C语言

    万次阅读 多人点赞 2018-12-18 16:14:37
      一直说要写二叉树后序非递归遍历算法,但是前两天各种事情,今天终于有时间好好写一写二叉树的后序遍历算法。   二叉树的后序遍历算法比先序和中序遍历算法要复杂一些。其出栈条件有两种情况: 栈顶元素...

      一直说要写二叉树的后序非递归遍历算法,但是前两天各种事情,今天终于有时间好好写一写二叉树的后序遍历算法。
      二叉树的后序遍历算法比先序和中序的遍历算法要复杂一些。其出栈条件有两种情况:

    1. 栈顶元素所指向的节点的左子树和右子树均为空;
    2. 栈顶元素所指向的节点的左子树和右子树均被访问过。

      第一种情况比较好判断,但是对于第二种情况就比较麻烦一点。要先判断其左子树和右子树是否分别被访问过。
      对于第二种情况,多加一个指针指向上一次循环访问过的节点(如果栈顶元素指向节点的左子树或右子树的值与该指针的值相等,则说明该栈顶元素可以出栈),并且进栈顺序是先进右子树,再进左子树,这样当右子树被访问过时,其左子树一定已经被访问过了。

    代码如下:

    #include "stdafx.h"
    #include <stdlib.h>
    #include <stdio.h>
    #define STACKINITSIZE 20//栈初始空间大小
    #define INCREASEMENT 10//栈空间大小的增量
    
    typedef struct BiTNode
    {
    	char data;//二叉树节点数据
    	BiTNode *lchild,*rchild;//指向二叉树左子树和右子树的指针
    }BiTNode,*BiTree;//定义二叉树节点结构
    
    typedef struct SqStack
    {
    	BiTNode *base;//栈底指针
    	BiTNode *top;//栈顶指针
    	int stacksize;//顺序栈空间大小
    }SqStack;//定义顺序栈结构
    
    //建立一个空栈,建立成功,返回1,失败,返回0
    int InitStack(SqStack &S)
    {
    	S.base = (BiTNode*)malloc(STACKINITSIZE * sizeof(BiTNode));//20为栈的大小,可以更改
    	if(!S.base)
    		return 0;
    	S.top = S.base;
    	S.stacksize = STACKINITSIZE;
    	return 1;
    }
    
    //进栈操作
    int Push(SqStack &S,BiTNode e)
    {
    	if(S.top - S.base >= S.stacksize)
    	{
    		S.base = (BiTNode*)realloc(S.base,(STACKINITSIZE + INCREASEMENT) * sizeof(BiTNode));
    		if(!S.base)
    			return 0;
    		S.stacksize = 30;
    	}
    	*S.top = e;
    	S.top ++;
    	return 1;
    }
    
    //获取栈顶元素
    int GetTop(SqStack S,BiTNode &e)
    {
    	if(S.base == S.top)
    		return 0;
    	e = *(S.top - 1);
    	return 1;
    }
    
    //出栈操作,若栈为空,则返回0;栈不为空,则返回1
    int Pop(SqStack &S,BiTNode &e)
    {
    	if(S.base == S.top)
    		return 0;
    	S.top --;
    	e = *S.top;
    	return 1;
    }
    
    //判断栈是否为空,若栈为空,则返回true,栈不为空,则返回false
    bool StackEmpty(SqStack S)
    {
    	if(S.base == S.top)
    		return true;
    	else
    		return false;
    }
    
    //建立二叉树
    void CreateBiTree(BiTree &T)
    {
    	char ch;
    	scanf("%c",&ch);
    	if(ch == '#')
    		T = NULL;
    	else
    	{
    		T = (BiTNode *)malloc(sizeof(BiTNode));
    		T->data = ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }
    //比较两个节点的值是否相等
    bool Equal(BiTNode *e1,BiTNode *e2)
    {
    	if(NULL == e1 || NULL == e2)
    		return false;
    	if(e1->data == e2->data && e1->lchild == e2->lchild && e1->rchild == e2->rchild)
    		return true;
    	else
    		return false;
    }
    //后序遍历二叉树
    int PostOrderTraverse(BiTree T)
    {
    	if(!T)
    		return 0;
    	SqStack S;
    	int n = InitStack(S);//建立空栈
    	if(!n)
    		return 0;
    	BiTree p = T;
    	BiTree pre = NULL;
    	BiTNode e,cur;//二叉树节点,用于存放从栈中取出的节点
    	Push(S,*p);
    	while(!StackEmpty(S))
    	{
    		GetTop(S,e);//
    		if((NULL == e.lchild && NULL == e.rchild) || (NULL != pre && (Equal(pre,e.lchild) || Equal(pre,e.rchild))))
    		{
    			/*这里之前出现过错误,造成死循环。当时写的是
    			Pop(S,e);
    			printf("%c ",e.data);
    			pre = &e;
    			由于pre = 对e取地址,则当前面GetTop(S,e)时,pre的值也改变了,之前保存的内容没有了,if条件永远不会为真
    			*/
    			Pop(S,cur);
    			printf("%c ",cur.data);
    			pre = &cur;
    		}
    		else
    		{
    			if(NULL != e.rchild)
    			{
    				Push(S,*e.rchild);
    			}
    			if(NULL != e.lchild)
    			{
    				Push(S,*e.lchild);
    			}
    		}
    	}
    	printf("\n");
    	return 1;
    }
    
    int main(int argc, char* argv[])
    {
    	BiTree T = NULL;
    	printf("请输入二叉树-按照先序序列建立二叉树\n");
    	CreateBiTree(T);
    	printf("后序遍历二叉树结果为:\n");
    	PostOrderTraverse(T);
    	return 0;
    }
    
    
    
    

    建立的二叉树的形状为:
    在这里插入图片描述

    测试结果如下图所示:
    在这里插入图片描述

    写完这个后序遍历,我发现自己的坏习惯还真的是很难改正,依然很粗心,这一点代码占用了自己将近一天的时间,就是卡在了中间的那个循环那里,导致出现死循环。总是审题不严,急躁,这一点我会慢慢改正,及时时间不够,但是写出来的要保证是对的,否则还不如不写。

    展开全文
  • 首先非常感谢‘hicjiajia’博文:二叉树后序遍历(非递归) 这篇随笔开启我博客进程,成为万千程序员中一员,坚持走到更远! 折磨了我一下午的后序遍历中午得到解决,关键在于标记右子树是否被访问过,考虑过...

    首先非常感谢‘hicjiajia’的博文:二叉树后序遍历(非递归)

    这篇随笔开启我的博客进程,成为万千程序员中的一员,坚持走到更远!

    折磨了我一下午的后序遍历中午得到解决,关键在于标记右子树是否被访问过,考虑过修改二叉树结点的数据结构,增加一个visit域,或者建一个栈存储已访问的结点。都比较麻烦没有调试成功。若将右子树也入栈,如果没有访问标记的话,会改变访问的次序,甚至出现死循环,这是比较危险的情况。从借鉴的博文里,摘录并改写为C的代码,基本上没有改动。后续问题努力写出自己的原创代码。

    二叉树存储的数据类型为int型,用数字0表示子树为空

    输入:1 2 3 0 8 0 0 4 0 0 5 6 0 0 7 0 0

    得到后序遍历结果:83426751

     

     

     1 #include <stdio.h>
     2 #include <stdlib.h>
     3 
     4 #define OK              1
     5 #define ERROR           0
     6 #define MaxSize         100 
     7 
     8 typedef int ElemType;
     9 typedef int Status;
    10 
    11 typedef struct BTNode{
    12     ElemType    data; 
    13     struct BTNode *lchild,*rchild; 
    14 }BTree;
    15 
    16 typedef struct St{
    17     struct BTNode*    data[MaxSize];
    18     int               top;
    19 }Stack; 
    20 //1.按先序次序生成二叉树
    21 BTree* CreateT(){
    22     BTree *BT;
    23     ElemType ch;
    24     scanf("%d",&ch);
    25     if(ch==0)
    26         BT=NULL;
    27     else{
    28         BT=(BTree*)malloc(sizeof(BTree));
    29         if(!BT){exit(OVERFLOW);}        
    30         BT->data=ch;
    31         BT->lchild=CreateT();
    32         BT->rchild=CreateT();
    33     }
    34     return BT;
    35 } 
    36 
    37 //4.后序遍历
    38 Status PostOrder(BTree *BT) {
    39     if(BT){
    40         PostOrder(BT->lchild);
    41         PostOrder(BT->rchild);
    42         printf("%3d",BT->data);
    43         return OK;
    44     }
    45     else return ERROR;
    46 }
    47 //4.后序遍历-非递归 
    48 Status PostOrder2(BTree *BT) {
    49     Stack s,s2;
    50     BTree *T;
    51     int flag[MaxSize]; 
    52     s.top=0;
    53     T=BT;
    54     while(s.top!=0||T){
    55         while(T)
    56         {
    57             s.data[s.top++]=T;
    58             flag[s.top-1]=0;
    59             T=T->lchild;
    60          } 
    61          while(s.top!=0&&flag[s.top-1]==1){
    62              T=s.data[--s.top];
    63              printf("%3d",T->data);
    64          }
    65          if(s.top!=0){
    66              flag[s.top-1]=1;
    67              T=s.data[s.top-1];
    68              T=T->rchild;
    69          }
    70          else   break;
    71     }
    72     return OK;
    73 }
    74 int main(){
    75     BTree *BT;
    76     BT=CreateT();
    77     if(PostOrder(BT)){
    78         printf("\n后序遍历完成!\n");
    79     }    
    80     if(PostOrder2(BT)){
    81         printf("\n非递归后序遍历完成!\n");
    82     }
    83 }

     //-------------------------华丽的分割线-------------------------------------

    下面是我自己写的后序遍历程序

     1 //非递归后序遍历-test
     2 void PostOrder3(BTree *T){
     3     BTree *p=T;Stack s;s.top=-1;
     4     int tag[MaxSize];
     5     while(p||s.top!=-1){
     6         
     7         if(p){
     8             s.data[++s.top]=p;
     9             tag[s.top]=0;
    10             p=p->lchild;
    11         }        
    12         else{
    13             while(tag[s.top]==1){
    14             p=s.data[s.top--];
    15             printf("%d",p->data); 
    16             }
    17             p=s.data[s.top];
    18             p=p->rchild;
    19             tag[s.top]=1;
    20         }
    21         if(s.top==-1) break;
    22     }
    23 } 

     

    转载于:https://www.cnblogs.com/geolike/p/4721799.html

    展开全文
  • 二叉树先序遍历的实现思想是:访问根节点;访问当前节点的左子树;若当前节点无左子树,则访问当前节点的右子树;图 1 二叉树以图 1 为例,采用先序遍历的思想遍历该二叉树的过程为:访问该二叉树的根节点,找到 1;...

    二叉树先序遍历的实现思想是:

    访问根节点;

    访问当前节点的左子树;

    若当前节点无左子树,则访问当前节点的右子树;

    图 1 二叉树

    以图  1 为例,采用先序遍历的思想遍历该二叉树的过程为:

    访问该二叉树的根节点,找到 1;

    访问节点 1 的左子树,找到节点 2;

    访问节点 2 的左子树,找到节点 4;

    由于访问节点 4 左子树失败,且也没有右子树,因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树,因此现在开始遍历,即访问节点 5;

    由于节点 5 无左右子树,因此节点 5 遍历完成,并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 ,并开始遍历该节点的右子树,即访问节点 3;

    访问节点 3 左子树,找到节点 6;

    由于节点 6 无左右子树,因此节点 6 遍历完成,回到节点 3 并遍历其右子树,找到节点 7;

    节点 7 无左右子树,因此以节点 3 为根节点的子树遍历完成,同时回归节点 1。由于节点 1 的左右子树全部遍历完成,因此整个二叉树遍历完成;

    因此,图 1 中二叉树采用先序遍历得到的序列为:

    1 2 4 5 3 6 7

    递归实现

    二叉树的先序遍历采用的是递归的思想,因此可以递归实现,其 C 语言实现代码为:

    #include

    #include

    #define TElemType int

    //构造结点的结构体

    typedef struct BiTNode{

    TElemType data;//数据域

    struct BiTNode *lchild,*rchild;//左右孩子指针

    }BiTNode,*BiTree;

    //初始化树的函数

    void CreateBiTree(BiTree *T){

    *T=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->data=1;

    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->lchild->data=2;

    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->lchild->rchild->data=5;

    (*T)->lchild->rchild->lchild=NULL;

    (*T)->lchild->rchild->rchild=NULL;

    (*T)->rchild->data=3;

    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->rchild->lchild->data=6;

    (*T)->rchild->lchild->lchild=NULL;

    (*T)->rchild->lchild->rchild=NULL;

    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->rchild->rchild->data=7;

    (*T)->rchild->rchild->lchild=NULL;

    (*T)->rchild->rchild->rchild=NULL;

    (*T)->lchild->lchild->data=4;

    (*T)->lchild->lchild->lchild=NULL;

    (*T)->lchild->lchild->rchild=NULL;

    }

    //模拟操作结点元素的函数,输出结点本身的数值

    void displayElem(BiTNode* elem){

    printf("%d ",elem->data);

    }

    //先序遍历

    void PreOrderTraverse(BiTree T){

    if (T) {

    displayElem(T);//调用操作结点数据的函数方法

    PreOrderTraverse(T->lchild);//访问该结点的左孩子

    PreOrderTraverse(T->rchild);//访问该结点的右孩子

    }

    //如果结点为空,返回上一层

    return;

    }

    int main() {

    BiTree Tree;

    CreateBiTree(&Tree);

    printf("先序遍历: \n");

    PreOrderTraverse(Tree);

    }

    运行结果:

    先序遍历:

    1 2 4 5 3 6 7

    非递归实现

    而递归的底层实现依靠的是栈存储结构,因此,二叉树的先序遍历既可以直接采用递归思想实现,也可以使用栈的存储结构模拟递归的思想实现,其 C 语言实现代码为:

    #include

    #include

    #define TElemType int

    int top=-1;//top变量时刻表示栈顶元素所在位置

    //构造结点的结构体

    typedef struct BiTNode{

    TElemType data;//数据域

    struct BiTNode *lchild,*rchild;//左右孩子指针

    }BiTNode,*BiTree;

    //初始化树的函数

    void CreateBiTree(BiTree *T){

    *T=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->data=1;

    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->lchild->data=2;

    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->lchild->rchild->data=5;

    (*T)->lchild->rchild->lchild=NULL;

    (*T)->lchild->rchild->rchild=NULL;

    (*T)->rchild->data=3;

    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->rchild->lchild->data=6;

    (*T)->rchild->lchild->lchild=NULL;

    (*T)->rchild->lchild->rchild=NULL;

    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));

    (*T)->rchild->rchild->data=7;

    (*T)->rchild->rchild->lchild=NULL;

    (*T)->rchild->rchild->rchild=NULL;

    (*T)->lchild->lchild->data=4;

    (*T)->lchild->lchild->lchild=NULL;

    (*T)->lchild->lchild->rchild=NULL;

    }

    //前序遍历使用的进栈函数

    void push(BiTNode** a,BiTNode* elem){

    a[++top]=elem;

    }

    //弹栈函数

    void pop( ){

    if (top==-1) {

    return ;

    }

    top--;

    }

    //模拟操作结点元素的函数,输出结点本身的数值

    void displayElem(BiTNode* elem){

    printf("%d ",elem->data);

    }

    //拿到栈顶元素

    BiTNode* getTop(BiTNode**a){

    return a[top];

    }

    //先序遍历非递归算法

    void PreOrderTraverse(BiTree Tree){

    BiTNode* a[20];//定义一个顺序栈

    BiTNode * p;//临时指针

    push(a, Tree);//根结点进栈

    while (top!=-1) {

    p=getTop(a);//取栈顶元素

    pop();//弹栈

    while (p) {

    displayElem(p);//调用结点的操作函数

    //如果该结点有右孩子,右孩子进栈

    if (p->rchild) {

    push(a,p->rchild);

    }

    p=p->lchild;//一直指向根结点最后一个左孩子

    }

    }

    }

    int main(){

    BiTree Tree;

    CreateBiTree(&Tree);

    printf("先序遍历: \n");

    PreOrderTraverse(Tree);

    }

    运行结果

    先序遍历:

    1 2 4 5 3 6 7

    展开全文
  • 广义表创建二叉树 关于用广义表形式表示二叉树形式如下 ①广义表中一个字母代表一个结点数据信息。...下面先用自然语言描述算法如下。 依次从广义表中取得-个元素,并对取得元素做如下相应处理...
  • 145. 二叉树的后序遍历非递归)1. 题目描述2.代码如下3.细节 1. 题目描述 给定一个二叉树,返回它 后序 遍历。 示例: 输入: [1,null,2,3] 1 2 / 3 输出: [3,2,1] 进阶: 递归算法很简单,你可以通过迭代算法完成...
  • 二叉树遍历算法C语言实现)递归实现非递归实现 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; 递归实现 先序遍历 void PreOrder(BiTree T){ if(T!=NULL){ ...
  • 二叉树的非递归前、中、后序遍历算法详解及代码实现(C语言) 1. 前序遍历和中序遍历非递归算法思路 前序和中序非递归遍历的C代码 2. 后序遍历非递归算法思路 后序非递归遍历的C代码 1. 前序遍历和中序遍历...
  • 二叉树的非递归前、中、后序遍历算法详解及代码实现(C语言) 1. 前序遍历和中序遍历非递归算法思路 前序和中序非递归遍历的C代码 2. 后序遍历非递归算法思路 后序非递归遍历的C代码 1. 前序遍历和中序遍历非递归...
  • 二叉树非递归后序遍历算法(C语言) 二叉树后序遍历的规律:左右根 后序非递归遍历中,访问根(子根)结点有两种情况 ①:遍历完左子树,需要遍历右子树,需要从栈中访问最顶上的根(子根)结点从而得到右子树的指针。...
  • 1.实验目的 熟练掌握二叉树的二叉链表存储结构的C语言实现。...(2)二叉树的前、中、后序遍历的递归算法和非递归算法的实现 (3)求二叉树中叶子结点数目的递归算法。 (4)编写求二叉树深度的递归算法。 ...
  • 主要介绍了C语言数据结构之二叉树的非递归后序遍历算法的相关资料,希望通过本文能帮助到大家,让大家实现这样的功能,需要的朋友可以参考下
  • 二叉树的非递归前、中、后序遍历算法详解及代码实现(C语言) [1. 前序遍历和中序遍历非递归算法思路](https://blog.csdn.net/Benja_K/article/details/88389039#1. 前序遍历和中序遍历非递归算法思路:) 前序和中序...
  • 1.输入前序和中序遍历结果,建立二叉树 2.实现二叉树三种递归遍历算方法 3.实现二叉树三种非递归遍历算法 4.实现二叉树旋转90°后打印,直观树形结构
  • 实验7-二叉树应用 1)实验目的 ...注意:在非递归算法中用到栈和队列时,不要调用系统栈和队列,需要自己实现栈和队列操作。 3)验收/测试用例 创建 输入 :ABC$$DE$G$$F$$$ ($表示空格)
  • **完整程序,C语言,辅助为记录就近访问过节点的非递归后序遍历算法!** #include <stdio.h> #include <stdlib.h> #define MaxSize 100 typedef struct BiTNode{ char data; struct BiTNode *lchild,...
  • 以下是原递归算法(二叉树的先序、中序、后序遍历的递归实现算法): // 1.先序递归实现算法 void PreOrder(BiTree T) { if (T != NULL) { visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } } ...
  • 中序、后序遍历的非递归算法 各位再接再厉 #include <stdio.h> #include <stdlib.h> struct BinTree; void menu(); void preorder(struct BinTree * p); void inorder(struct BinTree * T); void ...
  • 本文现实了对二叉树的递归遍历和非递归遍历(后序遍历的非递归算法暂缺),当然还括包了一些栈操纵。 二叉树的遍历本质上其实就是入栈出栈的问题,递归算法单简且轻易解理,但是效率始终是个问题。非递归算法可以...
  • 二叉树的非递归遍历(前序中序后序非递归C语言

    万次阅读 多人点赞 2018-10-24 14:11:00
    经过两天搜索,看到网上很多种解法,很多解法都是用C++来写算法,一直找不到用C语言算法,所以就总结了一下,用C写出了一个遍历二叉树三种非递归算法。 前序遍历 前序遍历按照“根结点-左孩子-右孩子”...
  • 二叉树的非递归遍历 中序遍历:1,沿着根结点,向左依次入栈,直到左孩子为空 2,栈顶元素出栈并访问,若有孩子为空,继续执行。 3,若右孩子不为空,则将有孩子转执行1。 先序遍历:与中序遍历是一样的,只是把访问...
  • 因为后序遍历是先访问左子树,再访问右子树,最后访问根节点。当用栈实现遍历时,必须分清返回根节点时,是从左子树返回还是从右子树返回。所以使用辅助指针r指向最近已访问结点。当然也可以在节点中增加一个...
  • 文章中生动形象列出了前、中、后序遍历二叉树过程,和算法思路。恰逢我又失眠,然后想看下Java实现。发现大多人实现并没有书中实现那么直观,甚至有些晦涩,于是我整理了下书中提供的算法,供大家参考。 话...
  • 看了大量网络相关的理论和程序,... 最值得研究的还是后序遍历的非递归算法, 当时想了使用flag, 想到了多用一个栈, 想到了很多种方式,最后都以失败告终,经过网络查找, 感谢 https://www.cnblogs.com/rain-lei/p/3...
  • 二叉树遍历分为三种: 先序遍历:先访问根结点,其次...三种遍历的递归算法实现形式类似,仅仅是访问顺序不同,非常简洁。如下: //节点定义 typedef struct node { int val; struct node *left; struct no...
  • 二叉树的遍历有三种方式,如下: (1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根-左-右。 ... 二叉树遍历算法有递归算法和非递归算法,其中递归算法实现简
  • C语言实现二叉树遍历的递归和非递归算法

    万次阅读 多人点赞 2019-04-06 21:27:42
    本文主要介绍二叉树各种遍历方法。 二叉树遍历 所谓二叉树遍历,是指按某条搜索路径访问树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。 由二叉树的递归定义可知,...后序遍历:(L R L) 这...

空空如也

空空如也

1 2 3 4
收藏数 71
精华内容 28
关键字:

后序遍历的非递归算法c语言

c语言 订阅