• 【数据结构】链式二叉树知识点超全整理（内含完整代码解析

    目录

    1.二叉树链式结构的实现

    1.1回顾一下二叉树的概念

    1.2链式二叉树的构建和销毁

    1.2.1链式二叉树的构建：

    1.2.2链式二叉树的销毁

    1.3二叉树的遍历

    1.3.1 前序、中序以及后序遍历

    1.3.2层序遍历

    1.4. 节点个数以及高度等

    1.4.1.求二叉树节点个数

    1.4.2.二叉树叶子节点个数

    1.4.3.二叉树第k层节点个数

    1.4.4.二叉树查找值为x的节点

    1.5判断树是否为完全二叉树

    1.二叉树链式结构的实现

    1.1回顾一下二叉树的概念

    一棵二叉树是结点的一个有限集合，该集合:

    1. 或者为空

    2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

     具体细节可以移步我的这篇博文：

    (17条消息) 【数据结构】二叉树、堆_vpurple__的博客-CSDN博客https://blog.csdn.net/vpurple_/article/details/126202240?spm=1001.2014.3001.5501从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

    1.2链式二叉树的构建和销毁

    总体使用以下结构作为链式二叉树中的节点定义：

    1. typedef char BTDataType;
    2.  
    3. typedef struct BinaryTreeNode
    4. {
    5. 	BTDataType data;
    6. 	struct BinaryTreeNode* left;
    7. 	struct BinaryTreeNode* right;
    8. }BTNode;

    1.2.1链式二叉树的构建：

    BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);

    参数介绍：

    a 为指向"ABD##E#H##CF##G##"这个数组的指针

    n 为数组的长度

    pi 作为指向数组下标的指针

    请注意：

    在a指向的这个字符型数组中以'#'代表NULL，作为递归的返回条件。

    在这个函数中通过读数组下标的方式来得到其中的数据，由于每递归一次就会重新建立一个新的函数栈帧，在其中的局部变量是独立的，如果传递的是数组下标而不是数组下标的地址的话，会导致完成一整套递归，返回上一层时的数组下标并没有随之++，而是重复访问 

     采用如下代码可成功构建链式二叉树：

    1. // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
    2. BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
    3. {
    4. 	BTNode* tree = (BTNode*)malloc(sizeof(BTNode));
    5. 	if (tree == NULL)
    6. 	{
    7. 		perror("malloc fail\n");
    8. 		exit(-1);
    9. 	}
    10. 	if (*pi >= n || a[*pi] == '#')
    11. 	{
    12. 		return NULL;
    13. 	}
    14. 	tree->data = a[*pi];
    15. 	(* pi)++;
    16. 	tree->left = BinaryTreeCreate(a, n,pi );
    17. 	(* pi)++;
    18. 	tree->right = BinaryTreeCreate(a, n, pi);
    19. 	return tree;
    20. }

    1.2.2链式二叉树的销毁

    要采用后续遍历的方法销毁，不然会造成前面的结点销毁后面链接的节点找不到的情况，从而造成内存泄漏。

    1. void BinaryTreeDestory(BTNode* root)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		return;
    6. 	}
    7.  
    8. 	BinaryTreeDestory(root->left);
    9. 	BinaryTreeDestory(root->right);
    10. 	free(root);
    11. 	root = NULL;
    12. 	return;
    13. }

    1.3二叉树的遍历

    1.3.1 前序、中序以及后序遍历

    学习二叉树结构，最简单的方式就是遍历。  

    所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 

    遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。 按照规则，二叉树的遍历有：

    1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

    1. // 二叉树前序遍历 
    2. void BinaryTreePrevOrder(BTNode* root)
    3. {
    4. 	if (root == NULL)
    5. 	{
    6. 		printf("NULL ");
    7. 		return;
    8. 	}
    9. 	printf("%c ", root->data);
    10. 	BinaryTreePrevOrder(root->left);
    11. 	BinaryTreePrevOrder(root->right);
    12. 	return;
    13. }

    2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

    1. // 二叉树中序遍历
    2. void BinaryTreeInOrder(BTNode* root)
    3. {
    4. 	if (root == NULL)
    5. 	{
    6. 		printf("NULL ");
    7. 		return;
    8. 	}
    9. 	BinaryTreeInOrder(root->left);
    10. 	printf("%c ", root->data);
    11. 	BinaryTreeInOrder(root->right);
    12. 	return;
    13. }

    3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

    1. // 二叉树后序遍历
    2. void BinaryTreePostOrder(BTNode* root)
    3. {
    4. 	if (root == NULL)
    5. 	{
    6. 		printf("NULL ");
    7. 		return;
    8. 	}
    9. 	BinaryTreePostOrder(root->left);
    10. 	BinaryTreePostOrder(root->right);
    11. 	printf("%c ", root->data);
    12. 	return;
    13. }

    1.3.2层序遍历

    层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。

    设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

    在这里我们借助之前写的队列来实现层序遍历：

    先回顾一下之前写的队列：

    这里主要会使用到

    QueueInit 创建队列函数

    QueueDestroy 销毁队列函数

    QueuePush 数据队尾入队列函数

    QueuePop 数据队头出队列函数

    QueueFront 获取队头元素函数

    (6条消息) 【数据结构】队列、环形队列_vpurple__的博客-CSDN博客https://blog.csdn.net/vpurple_/article/details/126200057?spm=1001.2014.3001.5501

    解析如下，用电脑端打开观看更佳：

    完整代码如下：

    1.  层序遍历
    2. // 通过队列实现层序遍历
    3.  
    4. void BinaryTreeLevelOrder(BTNode* root)
    5. {
    6. 	if (root == NULL)
    7. 	{
    8. 		return;
    9. 	}
    10. 	Queue list;
    11. 	QueueInit(&list);
    12. 	QueuePush(&list, root);
    13.  
    14. 	//当队列不是空的时候
    15. 	while (!QueueEmpty(&list))
    16. 	{
    17. 		//打印front的值，注意front的类型是BTNode*
    18. 		BTNode* front=QueueFront(&list);
    19. 		printf("%c ", front->data);
    20. 		QueuePop(&list);
    21.  
    22. 		//front的左右入队列
    23. 		if (front->left != NULL)
    24. 		{
    25. 			QueuePush(&list, front->left);
    26. 		}
    27. 		if (front->right != NULL)
    28. 		{
    29. 			QueuePush(&list, front->right);
    30. 		}
    31. 	}
    32. 	printf("\n");
    33. 	QueueDestroy(&list);
    34. }

    1.4. 节点个数以及高度等

    1.4.1.求二叉树节点个数

    1. // 二叉树节点个数
    2. int BinaryTreeSize(BTNode* root)
    3. {
    4. 	
    5. 	if (root == NULL)
    6. 	{
    7. 		return 0;
    8. 	}
    9. 	int left = BinaryTreeSize((*root).left);
    10. 	int right = BinaryTreeSize((*root).right);
    11. 	return left + right + 1;
    12. }

    1.4.2.二叉树叶子节点个数

    1. // 二叉树叶子节点个数
    2. int BinaryTreeLeafSize(BTNode* root)
    3. {
    4. 	if (root == NULL)
    5. 	{
    6. 		return 0;
    7. 	}
    8. 	if (root->left == NULL&&root->right==NULL)
    9. 	{
    10. 		return 1;
    11. 	}
    12.  
    13. 	int leaf=BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
    14. 	return leaf;
    15. }

    1.4.3.二叉树第k层节点个数

    1. // 二叉树第k层节点个数
    2. int BinaryTreeLevelKSize(BTNode* root, int k)
    3. {
    4. 	if (k == 1)
    5. 	{
    6. 		if (root != NULL)
    7. 		{
    8. 			return 1;
    9. 		}
    10. 		else
    11. 		{
    12. 			return 0;
    13. 		}
    14. 	}
    15. 	k--;
    16. 	int k_leaves = 0;
    17. 	if (root != NULL)
    18. 	{
    19. 	  k_leaves = BinaryTreeLevelKSize(root->left, k) + BinaryTreeLevelKSize(root->right, k);
    20.  
    21. 	}
    22. 	return k_leaves;
    23.  
    24. }

    1.4.4.二叉树查找值为x的节点

    1. // 二叉树查找值为x的节点
    2. BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
    3. {
    4. 	if (root == NULL)
    5. 	{
    6. 		return NULL;
    7. 	}
    8. 	if (root->data == x)
    9. 	{
    10. 		return root;
    11. 	}
    12. 	BTNode* left=BinaryTreeFind(root->left, x);
    13. 	if (left != NULL)
    14. 	{
    15. 		return left;
    16. 	}
    17. 	BTNode* right=BinaryTreeFind(root->right, x);
    18. 	if (right != NULL)
    19. 	{
    20. 		return right;
    21. 	}
    22. 	return NULL;
    23. }

    1.5判断树是否为完全二叉树

    解析如下，用电脑端打开观看更佳：

    1. // 判断二叉树是否是完全二叉树
    2. int BinaryTreeComplete(BTNode* root)
    3. {
    4. 	if (root == NULL)
    5. 	{
    6. 		return -1;
    7. 	}
    8. 	Queue list;
    9. 	QueueInit(&list);
    10. 	QueuePush(&list, root);
    11.  
    12. 	//当队列不是空的时候
    13. 	while (!QueueEmpty(&list))
    14. 	{
    15. 		//注意front的类型是BTNode*
    16. 		BTNode* front = QueueFront(&list);
    17. 		QueuePop(&list);
    18. 		if (front == NULL)
    19. 		{
    20. 			break;
    21. 		}
    22.  
    23. 		//front的左右入队列
    24. 		
    25. 		QueuePush(&list, front->left);
    26. 		QueuePush(&list, front->right);
    27. 	}
    28. 	while (!QueueEmpty(&list))
    29. 	{
    30. 		BTNode* front = QueueFront(&list);
    31. 		QueuePop(&list);
    32. 		if (front != NULL)
    33. 		{
    34. 			break;
    35. 		}
    36. 	}
    37.  
    38. 	if (!QueueEmpty(&list))
    39. 	{
    40. 		return -1;//不完全
    41. 	}
    42. 	else
    43. 	{
    44. 		return 0;
    45. 	}
    46. }

    普天同庆终于写完啦！！这篇博客真的墨迹了好久呜呜呜你好，这里是媛仔！很开心你可以看到这里，希望这篇博客能够对你有所帮助，我们下期再见~

  • 相关阅读:
    Linux——手把手教你解决sudo指令无法使用的问题
    私有仓库Harbor安装
    Docker（二）：Windows系统安装Docker
    从RabbitMQ平滑迁移到RocketMQ技术实战
    华为交换机S5735S-L24T4S-QA2无法telnet远程访问
    【开源三方库】Fuse.js：强大、轻巧、零依赖的模糊搜索库
    靶场上新：PigCMS任意文件上传漏洞
    .net技术----类和对象
    Git简介和安装
    什么是.NET的极限优化数值库?
  • 原文地址：https://blog.csdn.net/vpurple_/article/details/126411983