二叉树前序、中序、后续遍历的非递归算法

今天药忘吃喽~ 2021-11-05 09:40 270阅读 0赞

题目描述：二叉树前序、中序、后序遍历的非递归算法

思想： 二叉树前序、中序、后续非递归遍历需要栈来完成。

前序遍历非递归遍历：由于前序遍历二叉树顺序是根-左-右，所以在非递归遍历时，先让根结点入栈，然后出栈一个结点p并访问,然后判断p结点的右孩子结点是否存在，若存在则右孩子结点入栈，然后判断p结点的左孩子结点是否存在，如存在p的左孩子结点入栈。如上循环，直到栈为空为止。

中序遍历非递归遍历：由于中序遍历二叉树顺序是左-根-右，所以在非递归遍历时先扫描(不是访问)将根结点的所有左结点入栈，  然后出栈一个结点p(显然p结点无左孩子或左孩子结点已经被访问过)并访问p结点，然后访问扫描p结点的右孩子结点，若存在将其进栈，在扫描p结点右孩子结点的所有左节点并一一进栈，若不存在继续出栈一个结点，如上循环直到栈空为止。

后续遍历非递归遍历：由于后续遍历二叉树顺序是左-右-根，所以用栈来存储结点必须分清返回根结点时是从左子树返回还是从右子树返回。所以要使用辅助指针pre，让其指向最近访问过的结点。 在非递归遍历时先扫描将根结点的所有左结点入栈，然后取栈顶结点p，判断p结点的右孩子结点是否等于pre(之前访问过的结点，这样做的目的就是分清是从左子树返回的还是从右子树返回)，若不等于则p结点的右孩子结点入栈然后将其结点的所有左结点一一入栈，若等于则出栈当前结点p，用pre指向p,然后继续去栈顶结点。如上循环，直到栈为空为止。

算法代码：

void preorder(BiTree T){   //二叉树非递归前序遍历
    	stack s;
    	BiTree p ;
    	if (T == NULL){
    		cout << "二叉树为空";
    		exit(0);
    	}
    	s.data[++s.top] = T;//根结点先入栈
    	while (s.top>=0)
    	{
    		p = s.data[s.top--]; //出栈
    		cout << p->data << "\t";
    		if (p->rchild != NULL){
    			s.data[++s.top] = p->rchild;
    		}
    		if (p->lchild != NULL){
    			s.data[++s.top] = p->lchild;
    
    		}
    	}
    }
    void inorder(BiTree T){    //二叉树非递归中序遍历
    	stack s;
    	BiTree p=T;
    	if (T == NULL){
    		cout << "二叉树为空";
    		exit(0);
    	}
    	while (p!=NULL || s.top>=0)
    	{
    		if (p != NULL){
    			s.data[++s.top] = p;
    			p = p->lchild;
    		}
    		else{
    			p = s.data[s.top--];   //出栈
    			cout << p->data << "\t";
    			p = p->rchild;
    		}
    	}
    }
    void postorder(BiTree T){  //二叉树非递归后序遍历
    	stack s;
    	BiTree p = T, pre=NULL;
    	if (T == NULL){
    		cout << "二叉树为空";
    		exit(0);
    	}
    	while (p!=NULL || s.top>=0)
    	{
    		if (p != NULL){
    			s.data[++s.top] = p; //进栈
    			p = p->lchild;
    		}
    		else{
    			p = s.data[s.top];  //取栈顶结点
    			if (p->rchild != pre &&p->rchild != NULL){
    				p = p->rchild;
    			}
    			else
    			{
    				p = s.data[s.top--];  //出栈
    				cout << p->data << "\t";
    				pre = p;
    				p = NULL;
    			}
    		}
    	}
    }

样本：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70][]

二叉树先序序列：ABDEHCFIG

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    using namespace std;
    typedef char ElemType;
    #define Maxsize 30
    typedef struct BiTNode{
    	ElemType data;
    	struct BiTNode *lchild, *rchild;
    }BiTNode,*BiTree;
    typedef struct stack{  //辅助栈
    	BiTree data[Maxsize];
    	int top = -1;
    }stack;
    void preorder(BiTree T){   //二叉树非递归前序遍历
    	stack s;
    	BiTree p ;
    	if (T == NULL){
    		cout << "二叉树为空";
    		exit(0);
    	}
    	s.data[++s.top] = T;//根结点先入栈
    	while (s.top>=0)
    	{
    		p = s.data[s.top--]; //出栈
    		cout << p->data << "\t";
    		if (p->rchild != NULL){
    			s.data[++s.top] = p->rchild;
    		}
    		if (p->lchild != NULL){
    			s.data[++s.top] = p->lchild;
    
    		}
    	}
    }
    void inorder(BiTree T){    //二叉树非递归中序遍历
    	stack s;
    	BiTree p=T;
    	if (T == NULL){
    		cout << "二叉树为空";
    		exit(0);
    	}
    	while (p!=NULL || s.top>=0)
    	{
    		if (p != NULL){
    			s.data[++s.top] = p;
    			p = p->lchild;
    		}
    		else{
    			p = s.data[s.top--];   //出栈
    			cout << p->data << "\t";
    			p = p->rchild;
    		}
    	}
    }
    void postorder(BiTree T){  //二叉树非递归后序遍历
    	stack s;
    	BiTree p = T, pre=NULL;
    	if (T == NULL){
    		cout << "二叉树为空";
    		exit(0);
    	}
    	while (p!=NULL || s.top>=0)
    	{
    		if (p != NULL){
    			s.data[++s.top] = p; //进栈
    			p = p->lchild;
    		}
    		else{
    			p = s.data[s.top];  //取栈顶结点
    			if (p->rchild != pre &&p->rchild != NULL){
    				p = p->rchild;
    			}
    			else
    			{
    				p = s.data[s.top--];  //出栈
    				cout << p->data << "\t";
    				pre = p;
    				p = NULL;
    			}
    		}
    	}
    }
    void createBiTree(BiTree &T){
    	T = (BiTree)malloc(sizeof(BiTree));
    	cin >> T->data;
    	if (T->data == '#'){
    		T = NULL;
    		return;
    	}
    	createBiTree(T->lchild);
    	createBiTree(T->rchild);
    }
    int main(){
    	BiTree T;
    	cout << "输入二叉树的前序序列以#代表空(创建二叉树)：";
    	createBiTree(T);
    	cout << "\n"<<"二叉树的前序非递归遍历序列：";
    	preorder(T);
    	cout <<"\n"<< "二叉树的中序非递归遍历序列：";
    	inorder(T);
    	cout << "\n" << "二叉树的后序非递归遍历序列：";
    	postorder(T);
    	system("pause");
    	return 0;
    }

二叉树中序序列：DBHEAFICG

二叉树后序序列：DHEBIFGCA

完整代码：

结果显示：

![20190809005910137.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70]: /images/20211104/62c9e54674d44448890106c6a5419bf3.png
[20190809005910137.png]: /images/20211104/dc190d1f79d344ceabeab4a237f5239a.png