[C++知识库]二叉树非递归的前序遍历和中序遍历（C++）

考研党，一直不知道怎么把二叉树以及图的操作与栈和队列联系起来，后来发现用指针传地址是一个很好的解决办法。同样非递归层序遍历，以及图的BFS，DFS也可以用代码实现，加深记忆。?

#include<iostream>
using namespace std;

//定义树结点 
struct tree{
	int data;
	struct tree *lchild,*rchild;
};

//定义栈 
struct stack{
	struct tree* t;        //存放进栈的树结点的地址
	struct stack *next;
};

//二叉树结点构造
tree* insert(tree* &T){    //以先序遍历输入，00代表空结点 
	int x;
	cout<<"输入结点"<<endl; 
	cin>>x;                //输入第一个结点 1 -> 创建一个新的结点 ->递归创建 
	if(x==00) {
		return 0; 
	}
	else{
		T=new tree;
		T->data=x;
		T->lchild=insert(T->lchild);
		T->rchild=insert(T->rchild);
	}
	return T;
}

//栈（带头节点）的建立
void initstack(stack* &S,tree* &T){     //形参tree* 指针可以不用
	S=new stack;
	S->next=NULL;
} 

//入栈
void push(stack* &S,tree* &T){
	stack* P;
	if(S->next==NULL){
		P=new stack;
		P->t=T;       //指向T的地址 
		S->next=P;
		P->next=NULL;
	}
	else{
		P=new stack;
		P->t=T;
		P->next=S->next;
		S->next=P;
	}
} 

//出栈
void pop(stack* &S,tree* &T){ //T返回栈顶元素 
	stack* P;
	if(S->next==NULL){
		cout<<"报警"<<endl;
	}
	else{
		P=S->next;
		T=P->t;               //此时P的树节点的地址就是要返回的地址
		S->next=P->next;
	} 
} 

//栈判空
bool isempty(stack* S){
	if(S->next==NULL){
		return true;
	}
	else{
		return false;
	}
} 

//非递归中序遍历
void midbianli2(tree* T){
	stack* S;
	initstack(S,T);
	tree* P=T;           //P是工作指针 
	while(P||!isempty(S)){ 
		if(P){
		push(S,P);
		P=P->lchild;
	}
	else{
		pop(S,P);
		cout<<P->data<<endl;
		P=P->rchild;
		}
	}	
} 

//非递归前序遍历
void PreOrder2(tree* T){
	stack* S;
	initstack(S,T);
	tree* P=T;
	while(P||!isempty(S)){
		if(P){
			cout<<P->data<<endl;      //这个仅仅位置不同
			push(S,P);
			P=P->lchild;
		}
		else{
			pop(S,P);
			P=P->rchild;
		}
	}
} 



int main(){
	tree* T;
	insert(T);
	cout<<"非递归中序遍历是："<<endl;
	midbianli2(T);
	cout<<"非递归前序遍历是："<<endl;
	PreOrder2(T);
	return 0;
}

?