C语言中序遍历二叉树--非递归算法

àì夳堔傛蜴生んèń 2022-12-17 07:28 82阅读 0赞

完整代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct BiTNode//二叉树的结构体 
    { 
    	char ch;//二叉树的数据域 
    	struct BiTNode *lchild,*rchild;//二叉树的指针域 
    }BiTNode ,*BiTree;
    
    typedef struct StackNode //栈的结构体 
    { 
    	BiTree data;//栈的数据域，（数据域为二叉树的一个结点） 
    	struct StackNode *next; //栈的指针域 
    }SqStack,*LinkStack;
    
    void InitStack(LinkStack &S)//栈的初始化，只有创建一个栈顶结点这一步 
    { 
    	S = (SqStack*)malloc(sizeof(SqStack));//创建一个野结点，使其为NULL，便成为栈顶结点。 
    	S = NULL;
    }
    
    int Push(LinkStack &S,BiTree T)//进栈 
    { 
    	SqStack* p;//定义一个野结点 
    	p = (SqStack*)malloc(sizeof(SqStack));
    	p->data = T;//使该结点装上数据元素T，并使其next等于S,类似于链表的头插法 
    	p->next = S;
    	S = p;//栈顶结点S，一直在栈的最前方 
    	return 0; 
    }
    
    void Pop(LinkStack &S,BiTree &T)//使栈顶元素出栈，并返回栈顶元素 
    { 
    	if(S==NULL)//判断栈是否为空 
    	{ 
    		printf("栈空！");
    	}
    	else
    	{ 
    		SqStack* p;//这里定义一个结点，方便后面对栈顶结点的释放 
    		T = S->data; // 
    		p = S;
    		S = S->next;//使栈顶结点指向下一个结点，类似于栈减一 
    		free(p);//释放栈顶元素 
    	}	
    }
    
    void CreateTree(BiTree &T)//创建二叉树，这里是先序遍历的顺序建立的二叉链表 递归形式 
    { 
    	char ch,trmp;
    	scanf("%c",&ch);//输入链表数据 
    	if(ch == '#')//如果出现输入的是#,终止递归。终止递归条件 
    		T = NULL;
    	else
    	{ 
    		T = (BiTNode*)malloc(sizeof(BiTNode));//申请一个根结点 
    		T->ch = ch;//对根结点进行赋值 
    		CreateTree(T->lchild);//递归创建左子树 
    		CreateTree(T->rchild);//递归创建右子树 
    	}
    }
    
    void InOrderTraverse(BiTree T)//中序遍历二叉树T的非递归算法 
    { 
    	LinkStack S;
    	InitStack(S);//创建一个栈，并初始化 
    	BiTree p = T;
    	BiTree q = (BiTNode*)malloc(sizeof(BiTNode));//创建结点q，并为其申请空间 
    	while(p || S!=NULL)//循环终止条件是p为NULL与S等于NULL，两个条件同时满足的情况下，循环终止 
    	{ 
    		if(p)//p非空 
    		{ 
    			Push(S,p);//根指针进栈 
    			p = p->lchild;//遍历左子树 
    		}
    		else
    		{ 
    			Pop(S,q);//出栈 
    			printf("%c ",q->ch);//访问根结点 
    			p = q->rchild;//遍历右子树 
    		}
    	}
    }
    
    int main()
    { 
    	BiTree T;
    	CreateTree(T);//创建一个二叉树 
    	InOrderTraverse(T);//非递归中序遍历二叉树 
    	printf("\n");
    	return 0;
    }

结果演示：  
![在这里插入图片描述][20201022205114677.png_pic_center]  
（完）

[20201022205114677.png_pic_center]: /images/20221123/c078743a6b1f4398aeaa64bdee84643b.png