二叉树遍历

二叉树遍历

二叉树结构

struct BiTree{
	int	data;
	BiTree* lchild;
	BiTree* rchild;
};

先序遍历

void PreOrder(BiTree* root){
	if(root == NULL)
		return;
	cout<< root->data <<endl;
	PreOrder(root -> lchild);
	PreOrder(root -> right);
}

/* 
二叉树的非递归前序遍历，前序遍历思想：先让根进栈，只要栈不为空，就可以做弹出操作， 
每次弹出一个结点，记得把它的左右结点都进栈，记得右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面。 
*/ 
void PreOrder_Nonrecursive(BiTree* root){
	if(!root)
		return ;
	stack<BiTree> s;
	s.push(root);
	while(!s.empty()){
		BiTree* temp = s.top();
		cout << temp->data <<" ";
		s.pop();
		if(temp->rchild)
			s.push(temp->rchild);
		if(temp->lchild)
			s.push(temp->lchild);
	}
}

中序遍历

void InOrder(BiTree* root){
	if(root == NULL)
		return ;
	InOrder(root->lchild);
	cout<<root->data<<endl;
	InOrder(root->rchild);
}

void InOrder_Nonrecursive(BiTree* root){
	if(!root)
		return;
	BiTree* curr = root;
	stack<BrTree*> s;
	while(curr != NULL || !s.empty()){
		while(curr != NULL){//到最左下
			s.push(curr);
			curr=curr->lchild;
		}
		if(!s.empty()){
			curr = s.top();
			s.pop();//栈顶出栈
			cout << curr->data <<" ";
			curr=curr->rchild;	
		}
	}
}

后序遍历

void PostOrder(Bitree* root){
	if(root == NULL)
		return;
	PostOrder(root -> lchild);
	PostOrder(root -> rchild);
	cout << root->data <<" ";
}

void PostOrder_Nonrecursive(BiTree* root){
	stack<BiTree*> s;
	BiTree *p = root,*r = NULL, temp;//辅助指针r:指向最近访问过的结点
	while(p || !s.empty()){
		if(p){
			s.push(p)//走到最左边
			p=p->lchild;
		}
		else{//向右
			p=s.top();//取栈顶结点
			if(p->rchild&&p->rchild!=r){//如果右子树存在且未被访问过
				p=p->rchild;//转向右
				s.push(p);//压栈
				p=p->lchild;//再走到最左
			}
			else{//否则，弹出结点并访问
				p=s.top();
				s.pop();
				cout<<p->data;
				r=p;//记录最近访问过的结点
				p=NULL;
			}
		}	
	}
}

//双栈法
void PostOrder_DoubleStack(BiTree* root){
	stack<BiTree*> s1,s2;
	BiTree curr;
	s1.push(root）;
	while(!s1.empty()){
		curr = s1.top();
		s1.pop();
		s2.push(curr);
		if(curr->lchild)
			s1.push(curr->lchild);
		if(curr->rchild)
			s1.push(curr->rchild);
	}

	while(!s2.empty()){
		cout<<s2.top()->data<<" ";
		s2.top();
	}
}