数据结构：二叉树及相关操作

文章目录

  • 前言
  • 一、树的概念及结构
    • 1.什么是树
    • 2. 树的相关概念
    • 3.树的表示
  • 二、二叉树概念及结构
    • 1.二叉树概念
    • 2.特殊的二叉树
    • 3.二叉树的性质
    • 4.二叉树的存储结构
  • 三、平衡二叉树实现
    • 1.创建树和树的前中后遍历
      • 1.前中后遍历
      • 2.创建树且打印前中后遍历
    • 2.转换为平衡二叉树和相关操作
      • 1.转换为平衡二叉树
      • 2.二叉树的层序遍历
      • 3.判断是否为完全二叉树
      • 4.平衡二叉树的节点删除
    • 3.二叉树其他操作
  • 总结

前言

在实现二叉树前，我们要先对树产生一些基本的认识，才可以去实现它。树的用途非常广泛，向文件系统的目录树结构等。

一、树的概念及结构

1.什么是树

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。有一个特殊的结点，称为根结点，根节点没有前驱结点。除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。
如图所示：
在这里插入图片描述
注意：树形结构中，子树之间不能有交集，否则就不是树形结构
如图所示：
在这里插入图片描述
这个就不可以在称为树，这个构成了环形结构，这个是一个图。

2. 树的相关概念

在这里插入图片描述

节点的度：一个节点含有的子树的个数称为该节点的度。如上图：A的度为3
树的深度：树中节点的最大层次。如上图：树的深度为4
叶子节点：度为0的节点称为叶节点。如上图：K为叶子节点
孩子节点：一个节点含有的子树的根节点称为该节点的子节点。如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点。 如上图：B、C是兄弟节点
堂兄弟节点：双亲在同一层的节点互为堂兄弟。如上图：F、G是堂兄弟节点

3.树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一个孩子结点struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
};

上面树的表示形式如下：
在这里插入图片描述

二、二叉树概念及结构

1.二叉树概念

二叉树不存在度大于2的结点
如图所示：
在这里插入图片描述

2.特殊的二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。
完全二叉树：对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
在这里插入图片描述

3.二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2的(i-1)次方个结点。
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2的h次方减1个。
3. 对任何一棵二叉树，如果度为0其叶结点个数为X个 , 度为2的分支结点个数为Y个,则有X＝Y＋1
4.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对
于序号为i的结点有：
1.若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

4.二叉树的存储结构

1. 顺序存储顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
2. 链式存储二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
在这里插入图片描述
如上图所示：上面二叉树的储存形式如下：
在这里插入图片描述
链式存储的结构体如下：

typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

三、平衡二叉树实现

1.创建树和树的前中后遍历

1.前中后遍历

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。
前序遍历：根，左子树，右子树
中序遍历：左子树，根，右子树
后序遍历：左子树，右子树根，
在这里插入图片描述
在这里插入图片描述
中序和后续的遍历同理。

2.创建树且打印前中后遍历

要实现的函数：

//创建二叉树
void TreeCreate(BTDataType* a, int n);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

实现代码如下：

//创建二叉树
void TreeCreate(BTNode** root ,BTDataType num)
{if (*root == NULL)//如果节点为空证明该位置为要插入的位置{BTNode* pos = (BTNode*)malloc(sizeof(BTNode));//开辟节点if (pos == NULL)//判断节点是否开辟成功{perror("malloc");exit(-1);}pos->data = num;pos->left = NULL;pos->right = NULL;*root = pos;//把该节点连接到树上return;}if (num < (*root)->data)//比根节点小则在左边插入{TreeCreate(&(*root)->left, num);}else//比根节点大则在右边插入{TreeCreate(&(*root)->right, num);}
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){return;}BinaryTreeInOrder(root->left);printf("%d ", root->data);BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){return;}BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%d ", root->data);
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&(*root)->left);BinaryTreeDestory(&(*root)->right);free(*root);
}

测试函数：

void test()
{int arr[] = { 2,1,3,7,6,5,9,8,4 };int size = sizeof(arr) / sizeof(arr[0]);BTNode* root = NULL;int i = 0;for (i = 0; i < size; i++){TreeCreate(&root, arr[i]);//创建二叉树}BinaryTreePrevOrder(root);//前printf("\n");BinaryTreeInOrder(root);//中printf("\n");BinaryTreePostOrder(root);//后printf("\n");BinaryTreeDestory(&root);//销毁
}
int main()
{test();return 0;
}

构建的二叉树如下：
在这里插入图片描述
前序递归部分过程如下：
在这里插入图片描述
前序要先打印根节点的值在进行递归，中序要先进行左递归，在打印值，最后进行右递归，而后续则是先进行左右递归在打印相应的值。
注意：销毁二叉树要进行后续遍历，只有把根的左右子树都进行释放，才可以释放根节点。根节点先于左右子树释放会找不到相应左右节点，造成内存泄漏。

2.转换为平衡二叉树和相关操作

我们刚才构建的树明显一边节点多，一边节点少，所以我们把上面的树转化为左右子树的节点相差在1以内，进行左右平衡

1.转换为平衡二叉树

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return BinaryTreeSize(root->left) + 1 + BinaryTreeSize(root->right);
}
//左旋
BTNode* get_min(BTNode* root)
{if (root->left == NULL){return root;}return get_min(root->left);//返回最左边的节点
}
void turn_left(BTNode** root)
{BTNode* pos = *root;(*root) = pos->right;//更换头节点pos->right = NULL;//避免出现野指针get_min(*root)->left = pos;//把最左边的节点链接此接点
}
//右旋
BTNode* get_max(BTNode* root)
{if (root->right == NULL){return root;}return get_max(root->right);//返回最右边的节点
}
void turn_right(BTNode** root)
{BTNode* pos = *root;(*root) = pos->left;pos->left = NULL;get_max(*root)->right = pos;//把最右边的节点链接此接点
}
//转换为平衡二叉树
void BalanceTree(BTNode** root)
{if (*root == NULL){return;}while(1){int a = BinaryTreeSize((*root)->left);int b = BinaryTreeSize((*root)->right);int num = BinaryTreeSize((*root)->left) - BinaryTreeSize((*root)->right);if (num < -1)//右边多{//&（*root）中&和*抵消了，所以传一个root就可以了，但接收要用二级指针turn_left(root);//进行左旋}else if (num > 1)//左边多{turn_right(root);//进行右旋}else{break;}}BalanceTree(&(*root)->left);//开始平衡左子树BalanceTree(&(*root)->right);//开始平衡右子树
}

我们需要对树进行判断是否平衡，就需要求出左右节点的个数，我们还要对左边节点数量大于右边节点数量和右边大于左边的情况分别进行左右旋转。
在这里插入图片描述
这是进行一次循环，当当前根节点的左右平衡时，开始进行左右子树的平衡。
在这里插入图片描述
这样我们的平衡树就构建好了。
注意：我们进行左右旋转要连接在最后一个节点上，这样可以保障我们旋转后依然有序，左子树的结果比根节点小，右子树节点比根节点大。

2.二叉树的层序遍历

层序遍历就是按照层来访问二叉树的节点

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue qu;//创建队列QueueInit(&qu);//初始化队列QueuePush(&qu, root);//把根节点带入while (!QueueEmpty(&qu))//如果不为空则一直进行循环{BTNode*pos =  QueueFront(&qu);// 获取队列头部元素 printf("%d ", pos->data);QueuePop(&qu);//头部元素出队列if(pos->left != NULL)//如果左孩子不为空则进队列QueuePush(&qu, pos->left);if (pos->right != NULL)//如果右孩子不为空则进队列QueuePush(&qu, pos->right);}QueueDestroy(&qu);
}

层序遍历需要我们用队列进行辅助操作
在这里插入图片描述
层序遍历需要我们用队列进行辅助操作，由父节点来带动子节点，当子节点不为空就进入队列。
测试代码：

void test()
{int arr[] = { 2,1,3,7,6,5,9,8,4 };int size = sizeof(arr) / sizeof(arr[0]);BTNode* root = NULL;int i = 0;for (i = 0; i < size; i++){TreeCreate(&root, arr[i]);//创建二叉树}BalanceTree(&root);//构建BinaryTreeLevelOrder(root);//层BinaryTreeDestory(&root);//销毁
}
int main()
{test();return 0;
}

在这里插入图片描述

3.判断是否为完全二叉树

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue qu;//创建队列QueueInit(&qu);//初始化队列QueuePush(&qu, root);//把根节点带入while (!QueueEmpty(&qu))//如果不为空则一直进行循环{BTNode* pos = QueueFront(&qu);// 获取队列头部元素 QueuePop(&qu);//头部元素出队列if (pos != NULL){QueuePush(&qu, pos->left);QueuePush(&qu, pos->right);}else{while (!QueueEmpty(&qu))//一直出队列，直到队列为空停止循环{pos = QueueFront(&qu);// 获取队列头部元素 if (pos != NULL)//如果头部不为空，则证明不为完全二叉树{QueueDestroy(&qu);//销毁队列return false;}QueuePop(&qu);//头部元素出队列}}}QueueDestroy(&qu);return true;
}

在这里插入图片描述
判断是否为完全二叉树也需要用到队列，当为完全二叉树时，队列不会出现数据和空交替出队列的情况，而非完全二叉树会出现数据和空交替出队列的情况
测试代码如下：

void test()
{int arr[] = { 2,1,3,7,6,5,9,8,4 };int size = sizeof(arr) / sizeof(arr[0]);BTNode* root = NULL;int i = 0;for (i = 0; i < size; i++){TreeCreate(&root, arr[i]);//创建二叉树}BalanceTree(&root);//构建if (BinaryTreeComplete(root))//完全{printf("YES\n");}else{printf("NO\n");}BinaryTreeDestory(&root);//销毁
}
int main()
{test();return 0;
}

在这里插入图片描述

4.平衡二叉树的节点删除

//删除头节点,可以改为按查找节点删除
void DelTree(BTNode** root)//进行左旋
{BTNode* del = *root;//保存要删除的元素节点*root = del->left;//更换头节点get_max(*root)->right = del->right;free(del);BalanceTree(root);//从新构建平衡树
}

我们选择的是删除头根节点，然后进行左旋，从新构建成树，在进行平衡树的构建。我们也可以选择删除指定的节点，树的节点删除一般没有意义。
过程如下：
在这里插入图片描述

3.二叉树其他操作

// 二叉树最深节点
int DeepTree(BTNode* root)
{if (root == NULL){return 0;}//三目表达式，返回左子树和右子树最大的那个return DeepTree(root->left) > DeepTree(root->right) ? DeepTree(root->left) + 1 : DeepTree(root->right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)//当该节点为空时返回上一级，证明上一级左子树或右子树有一个不为空{return 0;}if (root->left == NULL && root->right == NULL)//当左右子树都为空时这个节点为叶子节点{return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);//返回左右子树的总和}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (k == 1)//从第一层开始，所以递减到1就可以了{return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);//返回左右子树的总和
}
// 二叉树查找值为x的节点
//BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
//{
//	if (root == NULL)//如果没找到则返回空
//	{
//		return NULL;
//	}
//	if (root->data == x)
//	{
//		return root;
//	}
//	BTNode* left = BinaryTreeFind(root->left, x);
//	BTNode* right = BinaryTreeFind(root->right, x);
//	if (left == NULL)//如果左子树没找到该值，则返回右子树的值，右子树树中也没找到返回的空，找到则返回相应的节点
//	{
//		return right;
//	}
//	return left;//要找的节点在左子树上
//}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{BTNode* pos = root;while (pos != NULL){if (pos->data < x)//该节点的值小于查找的值则在树的右边{pos = pos->right;}else if(pos->data > x)//该节点的值大于查找的值则在树的左边{pos = pos->left;}else{break;}}return pos;
}

二叉树节点的查找可以用正常方式的查找，也可以针对我们所构建的平衡二叉树设计一个函数，我们所设计的平衡二叉树的节点都满足左孩子的值小于父节点的值，右孩子的值都大于父节点的值，这样设计便于我们进行查找。
测试函数：

void test()
{int arr[] = { 2,1,3,7,6,5,9,8,4 };int size = sizeof(arr) / sizeof(arr[0]);BTNode* root = NULL;int i = 0;for (i = 0; i < size; i++){TreeCreate(&root, arr[i]);//创建二叉树}BalanceTree(&root);//构建printf("%d\n", DeepTree(root));//深度printf("%d\n", BinaryTreeLeafSize(root));//节点个数printf("%d\n", BinaryTreeLevelKSize(root,3));//k层printf("%d\n", BinaryTreeFind(root,3)->data);//查找节点BinaryTreeDestory(&root);//销毁
}
int main()
{test();return 0;
}

在这里插入图片描述

总结

树的更加高阶的内容我们会在进一步的学习中逐步的解锁
下面是本次的全部代码：
main.c:

#include"main.h"
void test()
{int arr[] = { 2,1,3,7,6,5,9,8,4 };int size = sizeof(arr) / sizeof(arr[0]);BTNode* root = NULL;int i = 0;for (i = 0; i < size; i++){TreeCreate(&root, arr[i]);//创建二叉树}BinaryTreePrevOrder(root);//前printf("\n");BinaryTreeInOrder(root);//中printf("\n");BinaryTreePostOrder(root);//后printf("\n");printf("%d", BinaryTreeSize(root));//节点个数printf("\n");BalanceTree(&root);//构建BinaryTreeLevelOrder(root);//层printf("\n");if (BinaryTreeComplete(root))//完全{printf("YES\n");}else{printf("NO\n");}printf("%d\n", DeepTree(root));//深度printf("%d\n", BinaryTreeLeafSize(root));//节点个数printf("%d\n", BinaryTreeLevelKSize(root,3));//k层printf("%d\n", BinaryTreeFind(root,3)->data);//查找节点DelTree(&root);BinaryTreeLevelOrder(root);//层BinaryTreeDestory(&root);//销毁
}
int main()
{test();return 0;
}

main.h:

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
// 链式结构：表示队列 
typedef BTNode* QDataType;
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;
// 队列的结构 
typedef struct Queue
{QNode* front;QNode* rear;
}Queue;
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType* QueueFront(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
//创建二叉树
void TreeCreate(BTDataType* a, int n);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
//转换为平衡二叉树
void BalanceTree(BTNode** root);
//删除头节点
void DelTree(BTNode** root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
// 二叉树最深节点
int DeepTree(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

test.c:

#include"main.h"// 初始化队列 
void QueueInit(Queue* q)
{assert(q);q->front = q->rear = NULL;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* pos = (QNode*)malloc(sizeof(QNode));if (pos == NULL){perror("malloc");exit(-1);}pos->data = data;pos->next = NULL;if (q->rear == NULL){q->front = q->rear = pos;}else{q->rear->next = pos;q->rear = pos;}
}
// 队头出队列 
void QueuePop(Queue* q)
{assert(q);assert(q->front);if (q->front->next == NULL){free(q->front);q->front = q->rear = NULL;}else{QNode* next = q->front->next;free(q->front);q->front = next;}
}
// 获取队列头部元素 
QDataType* QueueFront(Queue* q)
{assert(q);assert(q->front);return q->front->data;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{assert(q);return q->front == NULL;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);QNode* pos = q->front;while (pos){QNode* next = pos->next;free(pos);pos = next;}q->front = q->rear = NULL;
}
//创建二叉树
void TreeCreate(BTNode** root ,BTDataType num)
{if (*root == NULL)//如果节点为空证明该位置为要插入的位置{BTNode* pos = (BTNode*)malloc(sizeof(BTNode));//开辟节点if (pos == NULL)//判断节点是否开辟成功{perror("malloc");exit(-1);}pos->data = num;pos->left = NULL;pos->right = NULL;*root = pos;//把该节点连接到树上return;}if (num < (*root)->data)//比根节点小则在左边插入{TreeCreate(&(*root)->left, num);}else//比根节点大则在右边插入{TreeCreate(&(*root)->right, num);}
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){return;}BinaryTreeInOrder(root->left);printf("%d ", root->data);BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){return;}BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%d ", root->data);
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&(*root)->left);BinaryTreeDestory(&(*root)->right);free(*root);
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return BinaryTreeSize(root->left) + 1 + BinaryTreeSize(root->right);
}
//左旋
BTNode* get_min(BTNode* root)
{if (root->left == NULL){return root;}return get_min(root->left);//返回最左边的节点
}
void turn_left(BTNode** root)
{BTNode* pos = *root;(*root) = pos->right;//更换头节点pos->right = NULL;//避免出现野指针get_min(*root)->left = pos;//把最左边的节点链接此接点
}
//右旋
BTNode* get_max(BTNode* root)
{if (root->right == NULL){return root;}return get_max(root->right);//返回最右边的节点
}
void turn_right(BTNode** root)
{BTNode* pos = *root;(*root) = pos->left;pos->left = NULL;get_max(*root)->right = pos;//把最右边的节点链接此接点
}
//转换为平衡二叉树
void BalanceTree(BTNode** root)
{if (*root == NULL){return;}while(1){int a = BinaryTreeSize((*root)->left);int b = BinaryTreeSize((*root)->right);int num = BinaryTreeSize((*root)->left) - BinaryTreeSize((*root)->right);if (num < -1)//右边多{//&（*root）中&和*抵消了，所以传一个root就可以了，但接收要用二级指针turn_left(root);//进行左旋}else if (num > 1)//左边多{turn_right(root);//进行右旋}else{break;}}BalanceTree(&(*root)->left);//开始平衡左子树BalanceTree(&(*root)->right);//开始平衡右子树
}
//删除头节点,可以改为按查找节点删除
void DelTree(BTNode** root)//进行左旋
{BTNode* del = *root;//保存要删除的元素节点*root = del->left;//更换头节点get_max(*root)->right = del->right;free(del);BalanceTree(root);//从新构建平衡树
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue qu;//创建队列QueueInit(&qu);//初始化队列QueuePush(&qu, root);//把根节点带入while (!QueueEmpty(&qu))//如果不为空则一直进行循环{BTNode*pos =  QueueFront(&qu);// 获取队列头部元素 printf("%d ", pos->data);QueuePop(&qu);//头部元素出队列if(pos->left != NULL)//如果左孩子不为空则进队列QueuePush(&qu, pos->left);if (pos->right != NULL)//如果右孩子不为空则进队列QueuePush(&qu, pos->right);}QueueDestroy(&qu);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue qu;//创建队列QueueInit(&qu);//初始化队列QueuePush(&qu, root);//把根节点带入while (!QueueEmpty(&qu))//如果不为空则一直进行循环{BTNode* pos = QueueFront(&qu);// 获取队列头部元素 QueuePop(&qu);//头部元素出队列if (pos != NULL){QueuePush(&qu, pos->left);QueuePush(&qu, pos->right);}else{while (!QueueEmpty(&qu))//一直出队列，直到队列为空停止循环{pos = QueueFront(&qu);// 获取队列头部元素 if (pos != NULL)//如果头部不为空，则证明不为完全二叉树{QueueDestroy(&qu);//销毁队列return false;}QueuePop(&qu);//头部元素出队列}}}QueueDestroy(&qu);return true;
}
// 二叉树最深节点
int DeepTree(BTNode* root)
{if (root == NULL){return 0;}//三目表达式，返回左子树和右子树最大的那个return DeepTree(root->left) > DeepTree(root->right) ? DeepTree(root->left) + 1 : DeepTree(root->right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)//当该节点为空时返回上一级，证明上一级左子树或右子树有一个不为空{return 0;}if (root->left == NULL && root->right == NULL)//当左右子树都为空时这个节点为叶子节点{return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);//返回左右子树的总和}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (k == 1)//从第一层开始，所以递减到1就可以了{return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);//返回左右子树的总和
}
// 二叉树查找值为x的节点
//BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
//{
//	if (root == NULL)//如果没找到则返回空
//	{
//		return NULL;
//	}
//	if (root->data == x)
//	{
//		return root;
//	}
//	BTNode* left = BinaryTreeFind(root->left, x);
//	BTNode* right = BinaryTreeFind(root->right, x);
//	if (left == NULL)//如果左子树没找到该值，则返回右子树的值，右子树树中也没找到返回的空，找到则返回相应的节点
//	{
//		return right;
//	}
//	return left;//要找的节点在左子树上
//}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{BTNode* pos = root;while (pos != NULL){if (pos->data < x)//该节点的值小于查找的值则在树的右边{pos = pos->right;}else if(pos->data > x)//该节点的值大于查找的值则在树的左边{pos = pos->left;}else{break;}}return pos;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/104124.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Anaconda安装教程以及深度学习环境搭建

Anaconda安装教程以及深度学习环境搭建

目录 前言 下载Anaconda 虚拟环境的搭建 在pycharm中配置现有的conda环境 CUDA简介 下载安装pytorch包 前言 最近换新笔记本了&#xff0c;要重新安装软件&#xff0c;以前本来是想要写这个教程的&#xff0c;但当时由于截图不全还要懒得再下载重装&#xff0c;就放弃了&…
阅读更多...
高效多用的群集-Haproxy搭建Web集群

高效多用的群集-Haproxy搭建Web集群

Haproxy搭建 Web 群集 一、Haproxy前言 HAProxy是一个使用c语言编写的自由及开放源代码软件&#xff0c;其提供高可用性、负载均衡&#xff0c;以及基于TcP和HrrP的应用程序代理。HAProxy特别适用于那些负载特大的web站点&#xff0c;这些站点通常又需要会话保持或七层处理。…
阅读更多...
jmeter模拟多用户并发

jmeter模拟多用户并发

一、100个真实的用户 1、一个账号模拟100虚拟用户同时登录和100账号同时登录 区别 &#xff08;1&#xff09;1个账号100个人用&#xff0c;同时登录&#xff1b; &#xff08;2&#xff09;100个人100个账号&#xff0c;同时登录。 相同 &#xff08;1&#xff09;两个都…
阅读更多...
【ES6】—数组的扩展

【ES6】—数组的扩展

一、类数组/ 伪数组 1. 类/伪数组: 并不是真正意义的数组&#xff0c;有长度的属性&#xff0c;但无法使用Array原型上的方法 let divs document.getElementsByTagName(div) console.log(divs) // HTMLCollection []let divs2 document.getElementsByClassName("xxx&q…
阅读更多...
【业务功能篇73】分布式ID解决方案

【业务功能篇73】分布式ID解决方案

业界实现方案 1. 基于UUID2. 基于DB数据库多种模式(自增主键、segment)3. 基于Redis4. 基于ZK、ETCD5. 基于SnowFlake6. 美团Leaf(DB-Segment、zkSnowFlake)7. 百度uid-generator() 1.基于UUID生成唯一ID UUID:UUID长度128bit&#xff0c;32个16进制字符&#xff0c;占用存储空…
阅读更多...
Kdab QML (part9)自由缩放时钟

Kdab QML (part9)自由缩放时钟

文章目录 Kdab QML (part9)自由缩放时钟代码详细解释运行截图 Kdab QML (part9)自由缩放时钟 代码 import QtQuick 2.15 import QtQuick.Window 2.15Window {id: rootwidth: 500height: 500visible: truecolor: "lightgrey"title: qsTr("Hello World")It…
阅读更多...
springboot2+redis 订阅发布,解决接收消息累计线程到内存溢出，使用自定义线程池接收消息

springboot2+redis 订阅发布,解决接收消息累计线程到内存溢出，使用自定义线程池接收消息

pom 添加redis <!-- redis 缓存操作 --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency> 发布消息 import lombok.extern.slf4j.Slf4j; import o…
阅读更多...
【一】ubuntu20.04上搭建containerd版（ 1.2.4 以上）k8s及kuboard V3

【一】ubuntu20.04上搭建containerd版（ 1.2.4 以上）k8s及kuboard V3

k8s 部署全程在超级用户下进行 sudo su本文请根据大纲顺序阅读&#xff01; 一、配置基础环境&#xff08;在全部节点执行&#xff09; 1、安装docker 使用apt安装containerd 新版k8s已经弃用docker转为containerd&#xff0c;如果要将docker改为containerd详见&#xff1a…
阅读更多...
21.1 CSS 文字样式

21.1 CSS 文字样式

1. 字体倾斜 font-style属性: 为文本设置字体样式.常用取值: normal: 正常显示文本. 快捷键: fstab. italic: 显示斜体文本. 快捷键: fsntab.<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>fo…
阅读更多...
MySQL高级篇——MySQL架构篇3（用户与权限管理）

MySQL高级篇——MySQL架构篇3（用户与权限管理）

目录 1 用户管理1.1 登录MySQL服务器1.2 创建用户1.3 修改用户1.4 删除用户1.5 设置当前用户密码1.6 修改其它用户密码1.7 MySQL8密码管理(了解) 2 权限管理2.1 权限列表2.2 授予权限的原则2.3 授予权限2.4 查看权限2.5 收回权限 3 权限表3.1 user表3.2 db表3.3 tables_priv表和…
阅读更多...
实现外网访问本地服务

实现外网访问本地服务

最近开发需要其他项目组的人访问我本地服务测试,但又不在同一个地方,不能使用内网访问,所以需要外网访问本地服务功能. 条件: 1.需要一台具备公网IP的服务器 我用的服务器是windows,电脑也是Windows系统 2.下载frp 软件,只需要下载一份就可以了,分别放到服务器上和本地目录既…
阅读更多...
Python - 面向对象的属性，类方法，静态方法，实例方法的区别及用法详解

Python - 面向对象的属性，类方法，静态方法，实例方法的区别及用法详解

一. 前言 在Python的面向对象编程中&#xff0c;类属性和实例属性是两个不同的概念&#xff0c;它们在作用域和使用方式上有所区别。在Python中的面向对象编程中有三种方法&#xff1a;实例方法、类方法和静态方法&#xff0c;它们之间的差异主要体现在参数传递和调用方式上。…
阅读更多...
BDA初级分析——可视化基础

BDA初级分析——可视化基础

一、可视化的作用 数据可视化——利用各种图形方式更加直观地呈现数据的过程 可视化的作用 1、更快地理解数据&#xff0c;找出数据的规律和异常 2、讲出数据背后的故事&#xff0c;辅助做出业务决策 3、给非专业人士提供数据探索的能力 数据分析问题如何通过可视化呈现&am…
阅读更多...
基于前端技术原生HTML、JS、CSS 电子病历编辑器源码

基于前端技术原生HTML、JS、CSS 电子病历编辑器源码

电子病历系统采取结构化与自由式录入的新模式&#xff0c;自由书写&#xff0c;轻松录入。实现病人医疗记录&#xff08;包含有首页、病程记录、检查检验结果、医嘱、手术记录、护理记录等等。&#xff09;的保存、管理、传输和重现&#xff0c;取代手写纸张病历。不仅实现了纸…
阅读更多...
混币器——隐私交易的天堂，还是洗钱犯罪的聚集地？

混币器——隐私交易的天堂，还是洗钱犯罪的聚集地？

据美国财政部官网&#xff0c;Tornado Cash 联创 Roman Storm 已被 FBI 和国税局逮捕&#xff0c;罪名是串谋洗钱、串谋经营未经许可的资金传输业务以及串谋违反制裁规定&#xff0c;另一创始人 Roman Semenov仍然在逃。 FBI局长Christopher A. Wray说&#xff1a;“今天的公告…
阅读更多...
音视频FAQ（二）视频直播延时高

音视频FAQ（二）视频直播延时高

摘要 延时高是实时互动技术中常见的问题之一&#xff0c;解决延时高问题需要综合考虑网络、设备、编解码算法等多个因素。解决方案包括优化设备端延时、优化网络传输延时和使用UDP进行音视频传输等。在选择音视频传输协议时&#xff0c;需要综合考虑实际需求和网络条件&#x…
阅读更多...
MyBatis进阶：告别SQL注入！MyBatis分页与特殊字符的正确使用方式

MyBatis进阶：告别SQL注入！MyBatis分页与特殊字符的正确使用方式

目录 引言 一、使用正确的方式实现分页 1.1.什么是分页 1.2.MyBatis中的分页实现方式 1.3.避免SQL注入的技巧 二、特殊字符的正确使用方式 2.1.什么是特殊字符 2.2.特殊字符在SQL查询中的作用 2.3.如何避免特殊字符引起的问题 2.3.1.使用CDATA区段 2.3.2.使用实体引…
阅读更多...
Docker容器与虚拟化技术：Dockerfile部署LNMP

Docker容器与虚拟化技术：Dockerfile部署LNMP

目录 一、理论 1.LNMP架构 2.背景 3.Dockerfile部署LNMP 3.构建Nginx镜像 4.构建MySQL容器 5.构建PHP镜像 6.启动 wordpress 服务 二、实验 1.环境准备 2.构建Nginx镜像 3.构建MySQL容器 4.构建PHP镜像 5.启动 wordpress 服务 三、问题 1.构建nginx镜像报错 …
阅读更多...
“解放 Arweave“优惠：4EVERLAND的无缝上传教程

“解放 Arweave“优惠：4EVERLAND的无缝上传教程

为了进一步展示 Arweave 的能力&#xff0c;4EVERLAND 骄傲地推出了“解放 Arweave”活动。我们认识到 Arweave 在数据完整性、抗审查性以及长期保存方面的无与伦比的优势&#xff0c;因此我们与这个去中心化的存储巨头建立了强大的集成。 克服了过去与加密货币支付逻辑相关的…
阅读更多...
常见的数据库备份方法，常用的数据库备份方法有哪三种

常见的数据库备份方法，常用的数据库备份方法有哪三种

数据库作为存储和管理这些信息的核心&#xff0c;其安全性和稳定性尤为重要。因此&#xff0c;定期进行数据库备份是保护数据完整性的重要途径。下面我们就详细介绍几种常见的数据库备份方法。 1.全量备份 全备份是指备份数据库中的所有数据和元数据。这种方法通常用于开发或测…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023