二叉树中序遍历，非递归，用栈

LiQiyaoo

于 2016-01-14 22:14:39 发布

阅读量1k

点赞数 1

分类专栏：数据结构文章标签：数据结构二叉树中序遍历栈非递归

本文链接：https://blog.csdn.net/L_BestCoder/article/details/50520587

版权

数据结构专栏收录该内容

16 篇文章

订阅专栏

本文介绍了一种使用栈实现的二叉树非递归中序遍历算法，并提供了完整的C++代码实现。该算法首先通过递归方式创建二叉树，然后利用栈来辅助完成中序遍历过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

<pre name="code" class="cpp">这个是用非递归形式即栈的形式中序遍历二叉树

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<stack>
using namespace std;
typedef struct BiTreeNode{
	int data;
	struct BiTreeNode *lchild;
	struct BiTreeNode *rchild;
}*Bitree,BiTreeNode;
stack <Bitree> BiTstack;
void CreateBitree(Bitree &T){//递归方式先序建立二叉树 
	int data2;
	cin>>data2;
	if(data2==0){//到叶子结点时，输入两个0，代表叶子下面无左孩子，无右孩子 
		T=NULL;
		return ;
	}
	else{
		T=(Bitree)malloc(sizeof(BiTreeNode));
		T->data=data2;
		CreateBitree(T->lchild);
		CreateBitree(T->rchild);
	}
	
}

void InOrderTraverse(Bitree &T){ 
	Bitree p=T;
	while(p||!BiTstack.empty()){
		if(p){
			BiTstack.push(p);
			p=p->lchild;
		}
		else {
			cout<<(BiTstack.top())->data;//访问根节点 
			p=BiTstack.top();
			p=p->rchild;//在根节点处向右一步 
			BiTstack.pop();//使根节点出栈 
		}
	}
}

int main(){
	Bitree T;
	CreateBitree(T);
	InOrderTraverse(T);
	return 0;
}