侧边栏壁纸
博主头像
996worker

祇園精舎の鐘の聲, 諸行無常の響き有り。

  • 累计撰写 186 篇文章
  • 累计创建 46 个标签
  • 累计收到 8 条评论

目 录CONTENT

文章目录

二叉树非递归遍历

996worker
2022-07-21 / 0 评论 / 0 点赞 / 31 阅读 / 1,519 字
温馨提示:
本文最后更新于 2022-07-21,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

介绍

非递归需要用到栈数据结构。

  • 前序遍历:根节点-》左孩子-》右孩子。 将二叉树的根结点赋值给遍历的指针,由该指针进行遍历;若当前节点非空,则访问该节点并将该节点压栈(将该节点的地址压栈),继而遍历其左子树;循环执行,直到当前节点为空时,取栈顶元素并访问其右子树,再重复如上操作,直至遍历节点的指针为空且栈也为空;
  • 中序遍历:左孩子-》根节点-》右孩子。将二叉树的根结点赋值给遍历的指针,由该指针进行遍历;若当前节点非空,则将该节点压栈并访问其左子树,循环执行,直至当前节点为空时,取栈顶元素访问并弹栈,然后访问其右子树,再重复如上操作,直至遍历节点的指针为空在且栈也为空。(中序遍历和前序遍历的不同在于:前序遍历是入栈的同时访问结点,而中序遍历是出栈的同时访问结点)
  • 后序遍历:左孩子-》右孩子-》根节点。将二叉树的根结点赋值给遍历的指针,由该指针进行遍历;若当前节点非空,则将该节点压栈并访问其左子树,循环执行,直至当前节点为空时,取栈顶元素,判断其右子树是否为空且是否已遍历,如果非空且为遍历则访问其右子树,再将其压栈遍历其左子树;如果右子树为空或已遍历则访问该结点并弹栈,同时设置标记指针记录遍历过的点(用于判断右子树是否已遍历),再将遍历指针置空(下次遍历直接取栈顶元素),直至遍历节点的指针为空且栈也为空。

代码

前序遍历

void preorder(BiTree T){
//二叉树的非递归前序遍历 
	stack<BiTree> s;
	while(T||!s.empty()){
	//当前结点或栈不为空时执行该循环 
		if(T!=NULL){//当前结点不为空时 
			cout<<T->data;//访问当前结点信息 
			s.push(T);//将该节点的地址压栈 
			T=T->lchild;//遍历左孩子 
		}
		else{//当前结点为空时 
			T=s.top();//取栈顶的元素 
			s.pop();//弹栈 
			T=T->rchild;//遍历右孩子 
		}
	}
}

中序遍历

void inorder(BiTree T){
//二叉树的非递归中序遍历 
	stack<BiTree> s;
	while(T||!s.empty()){
	//当前结点或栈不为空时执行该循环 
		if(T!=NULL){//当前结点不为空时
			s.push(T);//将该节点的地址压栈
			T=T->lchild;//遍历左孩子
		}
		else
		{
			T=s.top();//取栈顶的元素
			s.pop();//弹栈
			cout<<T->data;//访问当前结点信息
			T=T->rchild;//遍历右孩子			
		}
	}
}

后序遍历

void postorder(BiTree T){
//二叉树的非递归后序遍历 
	BiTree r=NULL;
	stack<BiTree> s;
	while(T||!s.empty()){
		if(T!=NULL){//当结点不为空时,该结点压栈并遍历其左子树 
			s.push(T);
			T=T->lchild;
		}
		else{//当左子树结点为空时,取栈顶元素进行右子树的遍历, 
			T=s.top();
			if(T->rchild!=NULL&&T->rchild!=r){
			//右子树不为空且右子树没有被遍历过 
				T=T->rchild;
				s.push(T);//将该结点压栈,遍历其左子树 
				T=T->lchild;
			}
			else{//右子树为空或已遍历则取栈顶元素访问该结点的信息 
				s.pop();
				cout<<T->data;
				r=T;//标记遍历过的点,用于判断右子树是否已遍历 
				T=NULL;//遍历结点的指针置空,下次遍历直接取栈中的值 
			}
		}
	}
}

0

评论区