欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树 遍历

程序员文章站 2022-05-19 19:53:17
...
//二叉树深度优先遍历
//先序中序后序
//根据访问时机:第一次到先序,第二次到中序,第三次到后序
//先序:根节点-左子树-右子树
//中序:中序左子树-根节点-中序右子树
//后序:后序左子树-后序右子树-根节点

//树的深度优先遍历
//根据访问时机:首次访问先序,最后一次访问后序
//先序:根节点,先序所有子树
//后序:后序所有子树,根节点

//树转换成二叉树,先序相同,二叉树中序等效于树的后序
//森林转换二叉树相同


//二叉树遍历
//二叉树深度优先遍历
//递归实现,系统栈保护现场、恢复现场
void traversal(BTNode* p)
{
	if(p != NULL)
	{
		visit(p);//先序
		r(p->lChild);
		//中序
		r(p->rChild);
		//后序
	}
}

//二叉树深度优先遍历,非递归实现,自定义栈
//先序非递归遍历
void preorderNonrecursion(BTNode *bt)
{
	if (bt != NULL)
	{
		BTNode *Stack[Maxsize];
		int top = -1;//自定义栈
		BTNode *p = NULL;//定义指针p
		Stack[++top] = bt;//根节点入栈
		while(top != -1)
		{
			p = Stack[top--];
			visit(p);
			if(p->rChild != NULL)
				Stack[++top] = p->rChild;//右孩子先入栈
			if(p->rChild != NULL)
				Stack[++top] = p->lChild;
		}
	}
}
//先序序列:根-左子树-右子树
//逆后序:根-右子树-左子树
//后序非递归遍历代码
void postorderNonrecursion(BTNode *bt)
{
	if (bt != NULL)
	{
		BTNode *Stack1[Maxsize];int top1 = -1;//辅助遍历的栈
		BTNode *Stack2[Maxsize];int top2 = -1;//辅助逆后序求逆的栈
		BTNode *p = NULL;//定义指针p
		Stack1[++top] = bt;//根节点入栈
		while(top != -1)
		{
			p = Stack[top--];
			visit(p);
			if(p->rChild != NULL)
				Stack[++top] = p->lChild;//左孩子先入栈
			if(p->rChild != NULL)
				Stack[++top] = p->rChild;
		}
		while(top2 != -1)
		{
			p = Stack2[top2--];
			visit(p);
		}
	}
}
//中序非递归遍历
//算法描述:
//1、根节点入栈
//2、一直入栈左孩子,直到左孩子为空,出栈一个结点,并访问
//3、该结点右孩子存在,重复步骤2,右孩子为空,继续出栈一个结点,并访问,重复步骤2 
void inorderNonrecursion(BTNode *bt)
{
	if (bt != NULL)
	{
		BTNode *Stack[Maxsize]; int top =-1;//定义辅助栈
		BTNode *p = NULL;//定义指针p
		p = bt;
		while(top != -1 || p != NULL)//栈不为空,或者指向树的指针p不为空
		{
			while(p != NULL)
			{
				Stack[++top] = p;
				p = p->lChild;
			}//一直入栈左孩子
			if(top != -1)
			{
				p = Stack[top--];
				visit(p);
				p = p->rChild;
			}
		}
	}
}
//二叉树广度优先,层次遍历
//算法描述:
//1、根节点入队
//2、出队一个结点,检测出队结点的左右孩子,按左右顺序入队
//3、重复步骤2
void level(BTNode *bt)
{
	if (bt != NULL)
	{
		int front = rear = 0;
		BTNode *que[Maxsize];//顺序队列
		BTNode *p;

		rear = (rear + 1) % Maxsize;
		que[rear] = bt;//入队
		while(front != rear)//判断队列不为空
		{
			front = (front + 1) % Maxsize;
			p = que[front];//出队
			visit(p);
			//检测左右孩子不为空,入队
			if (p->lChild != NULL)
			{
				rear = (rear + 1) % Maxsize;
				que[rear] = p->lChild;
			}
			if (p->rChild != NULL)
			{
				rear = (rear + 1) % Maxsize;
				que[rear] = p->rChild;
			}
		}
	}
}


//树的遍历(考的不多)
//先序遍历
void r(BTNode *p)//伪代码用于理解
{
	if (p != NULL)
	{
		visit(p);
		//树的所有孩子
		r(p->child1);
		r(p->child2);
		r(p->child3);
		r(p->child4);
		......
		r(p->childn);		
	}
}
//树的孩子存储结构,链式存储,邻接表
typedef struct Branch
{
	int cIdx;
	Branch* next;
}Branch;
typedef struct 
{
	int data;
	Branch* first;
}TNode;
//取值
TNode tree[6];//数组长度为6
Branch* q = tree[0]->first;//指向第一个分支
tree[q->cIdx];//找到索引是cIdx的结点

//正确代码
//先序遍历
void preOrder(TNode *p, TNode tree[])
{
	if (p != NULL)
	{
		Branch *q = p->first;
		visit(p);
		while (q != NULL)
		{
			preOrder(&tree[q->cIdx], tree);
			q = q->next;
		}
	}
}
//后序遍历
void postOrder(TNode *p, TNode tree[])
{
	if (p != NULL)
	{
		Branch *q = p->first;
		while (q != NULL)
		{
			postOrder(&tree[q->cIdx], tree);
			q = q->next;
		}
		visit(p);
	}
}
//层次遍历
void level(TNode *tn, TNode tree[])
{
	int front = rear = 0;
	TNode *que[Maxsize];//辅助队列
	TNode *p;

	if (tn != NULL)
	{
		rear = (rear + 1) % Maxsize;
		que[rear] = tn;//入队根结点

		while(front != rear)
		{
			front = (front + 1) % Maxsize;
			p = que[front];//出队
			visit(p);
			Branch *q = p->first;//找到指向孩子链表的分支

			while(q != NULL)
			{
				rear = (rear + 1) % Maxsize;
				que[rear] = &tree[q->cIdx];//入队孩子
				q = q->next;
			}
		}
	}
}

 

相关标签: 数据结构