当前位置:   article > 正文

数据结构 二叉树遍历专题_先序中可以用bitnode *p作为遍历指针吗

先序中可以用bitnode *p作为遍历指针吗
// 二叉树的数据结构
typedef struct BiTNode{            //二叉链表
    char data;                     //默认char型,可替换
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
  • 1
  • 2
  • 3
  • 4
  • 5

1. 二叉树先序,中序,后续遍历递归算法。

//先序
void postorder(BiTree T)
{
	if(T!=NULL) 
	{
		visit(T);
		postorder(T->lchild);
		postorder(T->rchild);
	}
}
//中序
void inorder(BiTree T)
{
	if(T!=NULL) 
	{
		inorder(T->lchild);
		visit(T);
		inorder(T->rchild);
	}
}
//后序
void backorder(BiTree T)
{
	if(T!=NULL) 
	{
		backorder(T->lchild);
		backorder(T->rchild);
		visit(T);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

2. 二叉树先序,中序,后续遍历非递归算法

非递归算法要用到栈来保存节点的信息。

//先序
void postorder(BiTree T)
{
	BiTNode *p=T; //遍历指针
	InitStack(s);   //初始化栈
	while(p!=NULL||!IsEmpty(s))
	{
		if(p!=NULL)          //p不空,遍历到最左边的位置
		{
			visit(p);
			push(s,p);
			p=p->lchild;
		}
		else                 //p的左子树为空,弹出p,让p等于其右子树(如果有)重新进入到while循环
		{
			pop(s,p);
			p=p->rchild;
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
//中序
void inorder(BiTree T)
{
	BiTNode *p=T; //遍历指针
	InitStack(s);   //初始化栈
	while(p!=NULL||!IsEmpty(s))
	{
		if(p!=NULL)          //p不空,遍历到最左边的位置
		{			
			push(s,p);
			p=p->lchild;
		}
		else                 //p无左子树,说明p在最左边,访问一次节点
		{
			pop(s,p);
			visit(p);
			p=p->rchild;
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

分析:后续遍历的非递归较为特殊,对于一个节点,要做三个判断:①如果左子树存在,则入栈;②节点已经无左子树,有右子树,右子树入栈,转到①;③节点左子树,右子树都不存在,将栈顶元素弹出并访问,此时需要判断,如果是从某个节点p的右子树弹出,则弹出后栈顶元素变为p,此时对p判断,p存在右子树,但是右子树已经访问过,所以要用一个指针记录弹出的元素是否为其右子树。

//后序
void backorder(BiTree T)
{
	BiTNode *p=T; //遍历指针
	BiTNode *r=NULL; //辅助指针
	InitStack(s);   //初始化栈
	while(p!=NULL||!IsEmpty(s))
	{
		if(p!=NULL)          //左子树不空,遍历到最左边的位置
		{			
			push(s,p);
			p=p->lchild;
		}
		else                 //左子树空,进一步判断
		{
			GetTop(S,p);
			if(p->rchild!=NULL&&p->rchild!=r)   //左子树空,且右子树未被访问
			{
				p=p->rchild;
				push(s,p);       				//右子树入栈
				p=p->lchild;     				//继续向左遍历(如果有左子树)
			}
			else                 				//p的左右子树都空               
			{
				pop(s,p);						//p出栈
				visit(p);						//访问p
				r=p;							//记录p的位置
				p=NULL;							//将p置空,继续访问下一个栈顶元素
			}
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

3. 二叉树层序遍历算法。

//先序
void levelorder(BiTree T)
{
	InitQueue(Q);
	BiTNode *p=T; //遍历指针
	EnQueue(Q,p);
	while(!IsEmpty(Q))
	{
		DeQueue(Q,p);
		visit(p);
		if(p->lchild!=NULL)
		EnQueue(Q,p->lchild);
		if(p->lchild!=NULL)
		EnQueue(Q,p->lchild);		
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

4. 中序线索二叉树的构造

void Inthread(BiThrNode &p,BiThrNode &pre)
{
	if(p!=NULL)
	{	
		Inthread(p->lchild,pre);   //递归到最左边
		if(p->lchild==NULL)        //节点已无左子树,令其rtag=1,rchild节点指向其前驱。
		{
			p->ltag=1;
			p->lchild=pre;
		}
		if(pre!=NULL&&pre->child==NULL)//若pre的右子树为空,说明该节点无后继,令其指向其后继,修改rtag=1;
		{
			pre->rchild=p;
			pre->rtag=1;
		}
		pre=p;                     /
		Inthread(p->rchild,pre);
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

5. 前序线索二叉树的构造

void postThrTree(BiThrNode &p,BiThrNode &pre)
{
	if(P!=NULL)
	{
		if(p->lchild==NULL)   //前序遍历,先对该节点操作;
		{
			p->ltag=1;
			p->lchild=pre;
		}
		if(pre!=NULL&&pre->rchild==NULL)  //右子树空,右子树节点指向后继
		{
			pre->rtag=1;
			pre->rchild=p;
		}
		pre=p;                           //更新前驱节点,准备遍历下一个节点。
		postThree(p->lchild,pre);
		postThree(p->rchild,pre);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

由此可见,前序,中序后序整体上只是线索的操作变了位置,可据此写出后续线索化的代码,这里不在赘述。

4. 中序线索二叉树的相关操作

//求第一个节点
BiThrNode *findfirst(BiThrNode *p)
{
	while(p->ltag=0) p=p->lchild;
	return p;
}
//求p节点后继
BiThrNode *nextnode(BiThrNode *p)
{
	if(p->rtag==1) return p;
	else return *findfirst(p->rchild);//若右孩子存在,,由中序遍历的特点可知,则该节点后继必为右孩子中最左边的节点。
}
//中序线索树遍历
void inthroredr(BiThrNode *p)
{
	BiThrNode *first =findfirst(p);
	while(p!=NULL)
	{
		visit(p);
		p= nextnode(p);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/725292
推荐阅读
相关标签
  

闽ICP备14008679号