二叉树的遍历-中序遍历非递归算法

r囧r小猫 2022-05-26 11:00 195阅读 0赞

![70][]

中序 遍历的几种情况

分析1：什么时候访问根、什么时候访问左子树、什么访问右子树

当左子树为空或者左子树已经访问完毕以后，再访问根

访问完毕根以后，再访问右子树。

分析2：为什么是栈，而不是其他队列。

先走到的后访问、后走到的先访问，显然是栈结构

分析3：结点所有路径情况

步骤1：结点的所有路径情况

如果结点有左子树，该结点入栈；

如果结点没有左子树，访问该结点；

分析3：路径所有情况

如果结点有右子树，重复步骤1；

如果结点没有右子树（结点访问完毕），回退，让栈顶元素出栈，访问栈顶元素，并访问右子树，重复步骤1

如果栈为空，表示遍历结束。

注意：入栈的结点表示，本身没有被访问过，同时右子树也没有被访问过。

分析4：有一个一直往左走入栈的操作

**我的理解：先遍历到结点B，发现B没有左子树，故访问B,打印B;接着遍历看B的右子树，发现结点C，有左子树D，故C入栈，继续遍历D,发现结点D没有左子树，故访问D,打印D,接着发现结点D没有右子树，回退，让栈顶元素出栈，此时栈中有C，出栈，打印出来C,回退遍历到结点A,A有右子树，遍历结点E,E结点没有左子树，访问E,打印出来，E有右子树，遍历到F结点，F结点有左子树G,故F入栈，接着遍历到G结点，发现G有左子树H结点，故G入栈，遍历到H结点，H没有左子树，故访问H,打印出来H,H没有有右子树，回退，让栈顶元素出栈，也就是G。遍历I结点，因为I没有左子树，故访问I,打印出来I结点，I没有右子树，回退，让栈顶元素出栈，也就是F,栈中为NULL,表示遍历结束**

#include <iostream>
    using namespace std;
    #include "stack"
    
    
    
    //二叉链表示法
    typedef struct BiTNode
    {
    	char data;//数据域
    	struct BiTNode *lchild;//指针域,存放指向左孩子的指针
    	struct BiTNode *rchild;//指针域,存放指向右孩子的指针
    }BiTNode, *BiTree;
    
    
    /*
    步骤1：
    如果结点有左子树，该结点入栈；
    如果结点没有左子树，访问该结点；
    步骤2：
    如果结点有右子树，重复步骤1；
    如果结点没有右子树（结点访问完毕），根据栈顶指示回退，访问栈顶元素，并访问右子树，重复步骤1
    如果栈为空，表示遍历结束。
    
    */
    //一直往左边走,找到中序遍历的起点
    BiTNode *goLeft(BiTNode *T, stack<BiTNode *> &s)
    {
    	if (NULL == T)
    	{
    		return NULL;
    	}
    
    	//判断T有没有左孩子,没有把T 返回
    	//有,T入栈
    	while (T->lchild !=NULL)
    	{
    		s.push(T);
    		T = T->lchild;
    	}
    
    	return T;
    }
    
    void Inorder2(BiTNode *T)
    {
    	BiTNode *t = NULL;
    	stack<BiTNode *> s;
    
    	t = goLeft(T,s);
    
    	while (t)
    	{
    		//如果结点没有左子树，访问该结点；打印该结点数据
    		printf("%c ", t->data); 
    
    		//如果t 有右子树 重复步骤1
    		if (t->rchild !=NULL)
    		{
    			t = goLeft(t->rchild,s);//右子树中中序遍历的起点
    		}
    		else if (!s.empty())//如果t没有右子树 根据栈顶指示 回退
    		{
    			t = s.top();//获得栈顶元素
    			s.pop();//将其弹出
    		}
    		else//如果t没有右子树 并且栈为空 
    		{
    			t = NULL;
    		}
    	}
    }
    
    
    
    void inOrder(BiTNode *root)
    {
    	if (root == NULL)
    	{
    		return;
    	}
    	//遍历左子树
    	inOrder(root->lchild);
    	printf("%c ", root->data);
    	//遍历右子树
    	inOrder(root->rchild);
    }
    
    void main()
    {
    	BiTNode A, B, C, D, E, F, G, H, I;
    	memset(&A, 0, sizeof(BiTNode));
    	memset(&B, 0, sizeof(BiTNode));
    	memset(&C, 0, sizeof(BiTNode));
    	memset(&D, 0, sizeof(BiTNode));
    	memset(&E, 0, sizeof(BiTNode));
    	memset(&F, 0, sizeof(BiTNode));
    	memset(&G, 0, sizeof(BiTNode));
    	memset(&H, 0, sizeof(BiTNode));
    	memset(&I, 0, sizeof(BiTNode));
    
    	A.data = 'A';
    	B.data = 'B';
    	C.data = 'C';
    	D.data = 'D';
    	E.data = 'E';
    	F.data = 'F';
    	G.data = 'G';
    	H.data = 'H';
    	I.data = 'I';
    
    
    	//建立关系
    	A.lchild = &B;
    	A.rchild = &E;
    	E.rchild = &F;
    	F.lchild = &G;
    	G.lchild = &H;
    	G.rchild = &I;
    	B.rchild = &C;
    	C.lchild = &D;
    
    
    	printf("\nolder inorder\n");
    	inOrder(&A);
    
    
    	printf("\n 非递归遍历\n");
    	Inorder2(&A);
    	printf("hello...\n");
    	system("pause");
    	return;
    }

[70]: /images/20220526/89b7d35edb5d49e4804be2ad163a877d.png