迭代的方式来遍历树（前序中序后序）百度一面

秒速五厘米 2022-11-29 05:52 148阅读 0赞

递归的方式来进行遍历树很简单。  
但是通过迭代的方式遍历树。  
首先  
**中序遍历**  
中序遍历就主要在于先走到最左节点，然后从这个节点进行左中右的顺序。因为到了最左的节点也要往回走，而为了支持这个回溯类似的方式，用**栈**来保存数据，进入一个下一个节点的就通过换一个节点继续从开头（所有左部分节点压入）

code：

void PreOrderWithoutRecursion1(BTNode* root)
    { 
    	if (root == NULL)
    		return;
    	node* p = root;
    	stack<node*> s;
    	while (!s.empty() || p)
    	{ 
    		//
    		while (p)
    		{ 		//如果是前序遍历，就是在这里进行操作。
    			s.push(p);
    			p = p->lchild;
    		}
    		//当p为空时，说明根和左子树都遍历完了，该进入右子树了
    		if (!s.empty())
    		{ 
    			p = s.top();
    			s.pop();
    			cout<<p->data;	//如果是中序；在这里输出
    			p = p->rchild;
    		}
    	}
    	cout << endl;
    }

不同的是**后序遍历**  
用一个保存上一个节点 ，  
先完全进入左节点，然后判断当前节点的右边节点是不是空 || 当前节点是不是上一个节点，就是已经访问过了

//后序遍历
    void PostOrderWithoutRecursion(BTNode* root)
    { 
    	if (root == NULL)
    		return;
    	stack<BTNode*> s;
    
    	BTNode* pCur, *pLastVisit;
    
    	pCur = root;
    	pLastVisit = NULL;
    	//先把pCur移动到左子树最下边
    	while (pCur)
    	{ 
    		s.push(pCur);
    		pCur = pCur->lchild;
    	}
    	while (!s.empty())
    	{ 
    		//走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
    		pCur = s.top();
    		s.pop();
    		//一个根节点被访问的前提是：无右子树或右子树已被访问过
    		if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
    		{ 
    			cout << pCur->data;
    			//修改最近被访问的节点
    			pLastVisit = pCur;
    		}
    		else
    		{ 
    
    			s.push(pCur);
    			//进入右子树，且可肯定右子树一定不为空
    			pCur = pCur->rchild;
    			while (pCur)
    			{ 
    				s.push(pCur);
    				pCur = pCur->lchild;
    			}
    		}
    	}
    	cout << endl;
    }