二叉树的非递归先序，中序，后序遍历

心已赠人 2022-09-16 11:27 203阅读 0赞

二叉树的非递归遍历：

先序遍历，中序遍历，后序遍历

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    typedef struct node
    {
        char data;
        struct node *lchild;
        struct node *rchild;
    } BiNode, *BiTree;
    
    //先序递归创建树，这里注意参数的类型，T的类型是 "*&" ,如果是 "**" 代码稍加改动就OK...
    void createTree(BiTree &T) 
    {
    	char ch;
    	cin.get(ch).get(); 
    	//过滤输入流中每次回车产生的回车符 
    	if (ch==' ')
    		T = NULL; //这里首先判断是不是空格，如果是，则为该节点赋NULL 
    	else 
    	{
    		T = (BiTree)malloc(sizeof(BiNode)); 
    		T->data = ch; 
    		createTree(T->lchild); 
    		createTree(T->rchild); 
    	}
    }
    
    void preOrderNoRe(BiTree T) // 前序遍历
    {
    	if( T == NULL) 
    	{ 
    		return ; 
    	} 
    	stack<BiTree> s; 
    	BiTree p = NULL;
    	p = T; 
    	while( p != NULL || !s.empty()) 
    	{
    		while (p != NULL) 
    		{
    			cout<< p->data <<" "; 
    			s.push(p); 
    			p = p->lchild; 
    		} 
    		
    		if(!s.empty()) 
    		{ 
    			p = s.top(); 
    			s.pop(); 
    			p = p->rchild; 
    		} 
    	}
    }
    
    void inOrderNoRe(BiTree T) //中序遍历
    { 
    	if( T == NULL)
    	{
    		return ; 
    	}
    	stack<BiTree> s; 
    	BiTree p = NULL;
    	p = T; 
    	while(p != NULL || !s.empty()) 
    	{
    		while (p != NULL)
    		{
    			s.push(p); 
    			p = p->lchild; 
    		}
    		if (!s.empty()) 
    		{
    			p = s.top();
    			s.pop(); 
    			cout << p->data <<" "; p = p->rchild; 
    		} 
    	}
    }
    
    void postOrderNoRe(BiTree T) //后序遍历
    {
    	if( T == NULL) 
    	{
    		return ; 
    	} 
    	
    	BiTree p = NULL;
    	stack<BiTree> s;
    	p = T; 
    	int Tag[200]; // 栈，用于标识从左（0）或右（1）返回 
    	int top = -1; 
    	while ( p != NULL || !s.empty())
    	{
    		while( p != NULL) 
    		{
    			s.push(p); 
    			Tag[++top] = 0; 
    			p = p->lchild; 
    		} 
    		
    		while ( !s.empty() && Tag[top] == 1) 
    		{
    			p = s.top(); 
    			s.pop(); 
    			cout<< p->data << " "; --top; // 出栈 
    		} 
    		if (!s.empty()) 
    		{ 
    			Tag[top] = 1; //设置标记右子树已经访问 
    			p = s.top(); 
    			p = p->rchild; 
    		} 
    		else
    		{
    			break; 
    		} 
    	}
    }
    
    int main()
    {
    	cout<<"Enter char one by one"<<endl;
    	BiNode *T; 
    	createTree(T); 
    	cout<<endl; 
    	
    	cout<<"preOrderNoRe: ";
    	preOrderNoRe(T);
    	cout<<endl; 
    	cout<<"inOrderNoRe: ";
    	inOrderNoRe(T);
    	cout<<endl; 
    	
    	cout<<"postOrderNoRe: ";
    	postOrderNoRe(T);
    	cout<<endl;
    	
    	system("pause"); 
    	return 0;
    }

By Andy @2013-09-08