数据结构【链试结构二叉树】

27 阅读 0 评论 0 点赞

摘要：设⼆叉树的根结点所在层数为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2 层上的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历。根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的，因此⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。回顾⼆叉树的概念，⼆叉树分为空树和⾮空⼆叉树，⾮空⼆叉树由根结点、根结点的左⼦树、根结点的右⼦树组成的。根结点、左⼦树、右⼦树。

个人主页：落叶

实现链式结构⼆叉树

⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址，其结构如下：

创建二叉树数据：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int data;
typedef struct Tree
{
	int arr;    //数值
	struct Tree* zuo;//左孩子
	struct Tree* you;//右孩子
}BT;

⼆叉树的创建⽅式⽐较复杂，为了更好的步⼊到⼆叉树内容中，我们先⼿动创建⼀棵链式⼆叉树

我们进行连接后就成下面这个二叉树

当然我们也可以这样看

//申请空间
BT* koj(data x)
{
	//申请节点
	BT* tab = (BT*)malloc(sizeof(BT));
	if (tab == NULL)
	{
		perror("malloic");
		exit(1);
	}
	tab->arr = x;
	tab->zuo= tab->you = NULL;

	return tab;
}
void p()
{
	//创建节点
	BT* n1 = koj(1);
	BT* n2 = koj(2);
	BT* n3 = koj(3);
	BT* n4 = koj(4);
	//进行连接
	n1->zuo = n2;
	n1->you = n3;
	n2->zuo = n4;

}



int main()
{
	p();
	return 0;
}

回顾⼆叉树的概念，⼆叉树分为空树和⾮空⼆叉树，⾮空⼆叉树由根结点、根结点的左⼦树、根结点的右⼦树组成的

根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的，因此⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。

前中后序遍历：

⼆叉树的操作离不开树的遍历，我们先来看看⼆叉树的遍历有哪些⽅式

遍历规则

按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：

（1）前序遍历(PreorderTraversal亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前

访问顺序为：根结点、左⼦树、右⼦树

（2）中序遍历(InorderTraversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）

访问顺序为：左⼦树、根结点、右⼦树

（3）后序遍历(PostorderTraversal)：访问根结点的操作发⽣在遍历其左右⼦树之后

访问顺序为：左⼦树、右⼦树、根结点

代码实现

前序遍历：

访问顺序为：根结点、左⼦树、右⼦树

//前序遍历-（根-左-右）
void qian(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->arr);
	//左子树
	qian(root->zuo);
	//右子树
	qian(root->you);
}

结果：

//申请空间
BT* koj(data x)
{
	//申请节点
	BT* tab = (BT*)malloc(sizeof(BT));
	if (tab == NULL)
	{
		perror("malloic");
		exit(1);
	}
	tab->arr = x;
	tab->zuo= tab->you = NULL;

	return tab;
}
void p()
{
	//创建节点
	BT* n1 = koj(1);
	BT* n2 = koj(2);
	BT* n3 = koj(3);
	BT* n4 = koj(4);

	//进行连接
	n1->zuo = n2;
	n1->you = n3;
	n2->zuo = n4;
	
	qian(n1);
	printf("\n");




}



int main()
{
	p();
	return 0;
}

中序遍历：

访问顺序为：左⼦树、根结点、右⼦树

//中序遍历-（左-根-右）
void zho(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	//左子树
	zho(root->zuo);
	printf("%d ", root->arr);
	//右子树
	zho(root->you);
}

结果：

//申请空间
BT* koj(data x)
{
	//申请节点
	BT* tab = (BT*)malloc(sizeof(BT));
	if (tab == NULL)
	{
		perror("malloic");
		exit(1);
	}
	tab->arr = x;
	tab->zuo= tab->you = NULL;

	return tab;
}
void p()
{
	//创建节点
	BT* n1 = koj(1);
	BT* n2 = koj(2);
	BT* n3 = koj(3);
	BT* n4 = koj(4);
	//进行连接
	n1->zuo = n2;
	n1->you = n3;
	n2->zuo = n4;

	/*qian(n1);
	printf("\n");*/

	zho(n1);
	printf("\n");

}



int main()
{
	p();
	return 0;
}

后序遍历：

访问顺序为：左⼦树、右⼦树、根结点

//后序遍历
void ho(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	//左子树
	ho(root->zuo);
	//右子树
	ho(root->you);
	printf("%d ", root->arr);
}

结果：

//申请空间
BT* koj(data x)
{
	//申请节点
	BT* tab = (BT*)malloc(sizeof(BT));
	if (tab == NULL)
	{
		perror("malloic");
		exit(1);
	}
	tab->arr = x;
	tab->zuo= tab->you = NULL;

	return tab;
}
void p()
{
	//创建节点
	BT* n1 = koj(1);
	BT* n2 = koj(2);
	BT* n3 = koj(3);
	BT* n4 = koj(4);

	//进行连接
	n1->zuo = n2;
	n1->you = n3;
	n2->zuo = n4;
	
	/*qian(n1);
	printf("\n");*/

	/*zho(n1);
	printf("\n");*/

	ho(n1);

}



int main()
{
	p();
	return 0;
}

图解遍历：

以前序遍历为例：

函数递归栈帧图：

前序遍历结果：123456

中序遍历结果：321546

后序遍历结果：315641

结点个数以及高度等

【⼆叉树】结点个数

// ⼆叉树结点个数 
int BinaryTreeSize(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//                左子树                     右子树
	return 1+ BinaryTreeSize(root->zuo)+ BinaryTreeSize(root->you);
}

结果：

//申请空间
BT* koj(data x)
{
	//申请节点
	BT* tab = (BT*)malloc(sizeof(BT));
	if (tab == NULL)
	{
		perror("malloic");
		exit(1);
	}
	tab->arr = x;
	tab->zuo= tab->you = NULL;

	return tab;
}
void p()
{
	//创建节点
	BT* n1 = koj(1);
	BT* n2 = koj(2);
	BT* n3 = koj(3);
	BT* n4 = koj(4);

	//进行连接
	n1->zuo = n2;
	n1->you = n3;
	n2->zuo = n4;

	/*qian(n1);
	printf("\n");*/

	/*zho(n1);
	printf("\n");*/

	//ho(n1);
	// ⼆叉树结点个数 
	printf("size:%d \n", BinaryTreeSize(n1));


}



int main()
{
	p();
	return 0;
}

【二叉树】叶子节点个数

// ⼆叉树叶⼦结点个数 
int BinaryTreeLeafSize(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//左子树和右子树都等于空，就是叶子节点
	if (BinaryTreeLeafSize(root->zuo) == NULL && BinaryTreeLeafSize(root->you) == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->zuo) + BinaryTreeLeafSize(root->you);
}

结果：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{
	//申请节点
	BT* tab = (BT*)malloc(sizeof(BT));
	if (tab == NULL)
	{
		perror("malloic");
		exit(1);
	}
	tab->arr = x;
	tab->zuo= tab->you = NULL;

	return tab;
}
void p()
{
	//创建节点
	BT* n1 = koj(1);
	BT* n2 = koj(2);
	BT* n3 = koj(3);
	BT* n4 = koj(4);


	//进行连接
	n1->zuo = n2;
	n1->you = n3;
	n2->zuo = n4;

	
	/*qian(n1);
	printf("\n");*/

	/*zho(n1);
	printf("\n");*/

	//ho(n1);
	// ⼆叉树结点个数 
	//printf("size:%d \n", BinaryTreeSize(n1));

	//叶子节点个数
	printf("叶子节点：%d\n", BinaryTreeLeafSize(n1));



}



int main()
{
	p();
	return 0;
}

【二叉树】第k层节点个数

// ⼆叉树第k层结点个数 
int BinaryTreeLevelKSize(BT* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	//k等于1了就返回1
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->zuo, k - 1) + BinaryTreeLevelKSize(root->you, k - 1);
}

结果：

这里加了2个节点5和6，就和上面那张图一样了。

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{
	//申请节点
	BT* tab = (BT*)malloc(sizeof(BT));
	if (tab == NULL)
	{
		perror("malloic");
		exit(1);
	}
	tab->arr = x;
	tab->zuo= tab->you = NULL;

	return tab;
}
void p()
{
	//创建节点
	BT* n1 = koj(1);
	BT* n2 = koj(2);
	BT* n3 = koj(3);
	BT* n4 = koj(4);

	//进行连接
	n1->zuo = n2;
	n1->you = n3;
	n2->zuo = n4;
	
	/*qian(n1);
	printf("\n");*/

	/*zho(n1);
	printf("\n");*/

	//ho(n1);
	// ⼆叉树结点个数 
	//printf("size:%d \n", BinaryTreeSize(n1));

	// 
	叶子节点个数
	//printf("叶子节点：%d\n", BinaryTreeLeafSize(n1));
	//k层节点个数
	printf("k: %d \n", BinaryTreeLevelKSize(n1, 3));


}



int main()
{
	p();
	return 0;
}

【二叉树】的深度/⾼度

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//遍历左子树，把值给zuo
	int zuo = BinaryTreeDepth(root->zuo);
	//遍历右子树,把值给you
	int you = BinaryTreeDepth(root->you);
	//进行判断
	return zuo > you ? zuo + 1:you + 1;
}

结果：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{
	//申请节点
	BT* tab = (BT*)malloc(sizeof(BT));
	if (tab == NULL)
	{
		perror("malloic");
		exit(1);
	}
	tab->arr = x;
	tab->zuo= tab->you = NULL;

	return tab;
}
void p()
{
	//创建节点
	BT* n1 = koj(1);
	BT* n2 = koj(2);
	BT* n3 = koj(3);
	BT* n4 = koj(4);

	//进行连接
	n1->zuo = n2;
	n1->you = n3;
	n2->zuo = n4;

	
	/*qian(n1);
	printf("\n");*/

	/*zho(n1);
	printf("\n");*/

	//ho(n1);
	// ⼆叉树结点个数 
	//printf("size:%d \n", BinaryTreeSize(n1));

	// 
	叶子节点个数
	//printf("叶子节点：%d\n", BinaryTreeLeafSize(n1));
	k层节点个数
	//printf("k: %d \n", BinaryTreeLevelKSize(n1, 3));

	//⼆叉树的深度/⾼度
	printf("高度:%d \n", BinaryTreeDepth(n1));

}



int main()
{
	p();
	return 0;
}

【二叉树】查找值为x的结点

// ⼆叉树查找值为x的结点 
BT* BinaryTreeFind(BT* root, data x)
{
	if (root == NULL)
	{
		return NULL;
	}
	//等于x，返回当前节点
	if (root->arr == x)
	{
		return root;
	}
	//zuo接收节点
	BT* zuo = BinaryTreeFind(root->zuo, x);
	if (zuo)
	{
		//返回节点
		return zuo;
	}
	//you接收节点
	BT* you = BinaryTreeFind(root->you, x);
	if (you)
	{
		//返回节点
		return you;
	}
}

左子树找不到，就找右子树

结果：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
//申请空间
BT* koj(data x)
{
	//申请节点
	BT* tab = (BT*)malloc(sizeof(BT));
	if (tab == NULL)
	{
		perror("malloic");
		exit(1);
	}
	tab->arr = x;
	tab->zuo= tab->you = NULL;

	return tab;
}
void p()
{
	//创建节点
	BT* n1 = koj(1);
	BT* n2 = koj(2);
	BT* n3 = koj(3);
	BT* n4 = koj(4);

	//BT* n5 = koj(5);
	//BT* n6 = koj(6);
	//进行连接
	n1->zuo = n2;
	n1->you = n3;
	n2->zuo = n4;

	//n2->you = n5;
	//n3->zuo = n6;
	
	/*qian(n1);
	printf("\n");*/

	/*zho(n1);
	printf("\n");*/

	//ho(n1);
	// ⼆叉树结点个数 
	//printf("size:%d \n", BinaryTreeSize(n1));

	// 
	叶子节点个数
	//printf("叶子节点：%d\n", BinaryTreeLeafSize(n1));
	k层节点个数
	//printf("k: %d \n", BinaryTreeLevelKSize(n1, 3));

	⼆叉树的深度/⾼度
	//printf("高度:%d \n", BinaryTreeDepth(n1));

	// ⼆叉树查找值为x的结点 
	BT* tab = BinaryTreeFind(n1, 4);
	printf("%s\n", tab == NULL ? "没找到" : "找到了");


}



int main()
{
	p();
	return 0;
}

【二叉树】销毁

// ⼆叉树销毁
void BinaryTreeDestory(BT** root)
{
	if (*root == NULL)
	{
		return;
	}
	//二级指针，需要传一级指针地址
	BinaryTreeDestory(&(*root)->zuo);
	BinaryTreeDestory(&(*root)->you);
	//释放空间
	free(*root);
	*root = NULL;
}

图解析：

结果：

我们可以看到全部销毁了。

层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进⾏层序遍历。设⼆叉树的根结点所在层数为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2 层上的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历

实现层序遍历需要额外借助数据结构：队列

创建队列，初始化，把根节点入队列

循环队列不为空，取队头打印，出队头。

然后判断左子树和右子树，是不是空，不是空就入队列。

销毁队列。

//层序遍历
//借助数据结构--队列
void LevelOrder(BT* root)
{
	Queue add;
	//初始化
	Queuecsh(&add);
	//入数据
	Queue_ruwei(&add, root);

	while (!buer(&add))
	{
		//取队头-打印
		BT* tab = qto(&add);
		printf("%d ", tab->arr);
		//出队
		Queue_chu(&add);
		//判断是不是空， 队头节点的左右孩子入，队列
		if (tab->zuo)
		{
			Queue_ruwei(&add, tab->zuo);
		}
		if (tab->you)
		{
			Queue_ruwei(&add, tab->you);
		}
	}

	//队列销毁
	Queuexiaoh(&add);
}

结果：

判断是否为完全二叉树

注意：
如果是完全二叉树，跳出循环之后队列里都是NULL。

如果不是完全二叉树，跳出循环之后队列里，还有非空节点。

思路：

创建一个队列，把根节点入队列，循环队列里不为空。

取队头节点，然后出队，判断这个节点是不是空，是空跳出循环。

不是空，左子树和右子树入队列。

是完全二叉树的话剩下的都是空，

循环取出队头数据，出队，进行判断，不等于空的话还有非空节点，那就是不完全二叉树了，返回false。

最后循环都为空，是完全二叉树，返回true。

bool pdercs(BT* root)
{
	Queue add;
	//队列初始化
	Queuecsh(&add);
	//入队列
	Queue_ruwei(&add, root);
	while (!buer(&add))
	{
		//取队头数据
		BT* tab =  qto(&add);
		//出队
		Queue_chu(&add);
		if (tab == NULL)
		{
			//等于空结束循环
			break;
		}//不为空让左右子树入队列

		//左子树_入队列
		Queue_ruwei(&add, tab->zuo);
		//右子树_入队列
		Queue_ruwei(&add, tab->you);
	}
	//循环判断队列，有一个数值不是完全二叉树，都是NULL就是完全二叉树
	while (!buer(&add))
	{
		//取队头
		BT* app = qto(&add);
		//出队
		Queue_chu(&add);
		//判断如果还有非空节点，返回false
		if (app != NULL)
		{
			Queuexiaoh(&add);
			return false;
		}
	}//循环完，说明队列里都是NULL,是完全二叉树，返回true

	//队列销毁
	Queuexiaoh(&add);
	return true;
}

结果：

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处：免费源码网-免费的源码资源网站 » 数据结构【链试结构二叉树】

点赞(0) 打赏

本文分类：文章资讯
本文标签：数据结构【链试结构二叉树】
浏览次数：27 次浏览
本文链接：https://freeymw.com/article/24281.html

上一篇 > Java项目中的分库分表实践指南
下一篇 > 【Electron】桌面应用开发启动直接打开一个网址或者浏览器打开一个网址

评论列表共有 0 条评论

暂无评论

数据结构【链试结构二叉树】

实现链式结构⼆叉树

前中后序遍历：

遍历规则

代码实现

前序遍历：

中序遍历：

后序遍历：

图解遍历：

函数递归栈帧图：

结点个数以及高度等

【⼆叉树】结点个数

【二叉树】叶子节点个数

【二叉树】第k层节点个数

【二叉树】的深度/⾼度

【二叉树】查找值为x的结点

【二叉树】销毁

层序遍历

判断是否为完全二叉树

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复