你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

数据结构代码题Day08---对应<Day48>

2021-11-9 15:28:39

树结构代码题

假设二叉树采用二叉链表结构存储,设计一个算法,求二叉树中值为x的层号。

题目分析

  • 题目实现的第一条件便是查找二叉树中数值为X的节点;
  • 其次对访问过程进行层次记录;
  • 最后返回当前所在的层数。

下面给出题目所对应的二叉树的例子图:
在这里插入图片描述
同时根据上述的二叉树的例子图,这里采用二叉树的前序遍历操作进行设计。

前序遍历二叉树模板

	//结构体
	typedef struct BiTree{
		int data;
		struct BiTree *lchild,*rchild;
	}*BiTree;
	//二叉树遍历模板,前序
	void preTraverse(BiTree * root) {
		if(root == null) {
			return;
		}
		visit(root->data);
		preTraverse(root->lchild);
		preTraverse(root->rchild);
	}

改进模板–找到目标节点

  • 对模板的改进,我们引入了x的目标值,
  • 并对visit函数进行改进,使得递归直接了当的找到了当前的节点数值
	void preTraverse(BiTree * root,int x) {
		if(root == null) {
			return;
		}
		if(root->data == x){
			printf("%d",root->data);//找到了x的数据
		}
		//visit(root->data);
		preTraverse(root->lchild,x);//改进递归
		preTraverse(root->rchild,x);//改进递归
	}

重点!!!!(如何对层次进行增减)

对于该问题,我们现有的知识便是,在遍历过程中,向下走便是+1,向上走便是减一,因此对于上述的二叉树的模板,我们要对其执行步骤进行更深层次的模拟。看下图:

在这里插入图片描述
根据上述对题目的遍历对其进行操作设计分析,得到下图的代码执行过程图。
在这里插入图片描述

  • 结合执行图的操作,对其进行分析
  • 首次访问到该节点代表1位置,这是是代表向下一层递归
  • 在访问到该节点后,是第二个位置,这是中序遍历的访问节点位置
  • 在离开该节点,代表访问完毕后对其进行层次-1操作(第三个位置),代表离开了该层次。

结合上述的操作,对上述的第二代模板进行改进如下:

模板再改进

	int level = 1;//初始化为1层次
	void preTraverse(BiTree * root,int x) {
		if(root == null) {//二叉树为null,返回0
			return 0;
		}
		if(root != null) {
			//找到目标节点
			if(root->data == x){
				printf("%d",level);//找到了x的数据
			}
			
			//@1,初次访问该节点,对应位置1,层次+1
			++level;
			preTraverse(root->lchild,x);//改进递归
			
			//@2 ,位置二、节点已经访问完
			
			preTraverse(root->rchild,x);//改进递归
			
			//@3, 位置三、 离开当前节点,层次-1
			--level;
		}
	}

上述便是题目的解答代码,关键在于明白二叉树的遍历的节点的访问的三次次序,并实现根据次序对其进行模板改进的算法实现!!

	printf("考研加油!!");

在这里插入图片描述