数据结构——二叉树（顺序结构与链式结构）

2023-12-29 20:00:40

最近在学习数据结构，我真的是长了知识，因为以前的数据结构就没学懂过，现在终于打开了知识的大门，在学的过程中每一个知识都是新奇玩意儿，直呼好家伙！话不多说，直接上内容。

1.二叉树的概念及结构

1.1 概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

二叉树的特点：

每个结点最多有两棵子树，即二叉树不存在度大于2的结点。

二叉树的子树有左右之分，其子树的次序不能颠倒。

1.2 特殊的二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

1.3 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，而现实中使用中只有堆才会使用数组来存储。

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系

1.4 二叉树的性质(选择填空较多)

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.
对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1
若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1). (ps：Log2(n+1)是log以2为底，n+1为对数)
对于具有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否则无右孩子

2. 二叉树的顺序结构

2.1 堆的概念及结构

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。

堆的性质：

1.堆中某个节点的值总是不大于或不小于其父节点的值；
2.堆总是一棵完全二叉树。

2.2 堆的实现

2.2.1 堆向下调整算法

通过从根节点开始的向下调整算法可以把它调整为一个小堆(大堆)。向下调整算法前提：左右子树必须是一个堆，才能调整。

算法思想：（假设是小根堆的调整）

1.从左右孩子中选择一个最小值
2.当前需要调整的数据与最小值进行比较：大于最小值，和最小值交换，从交换完的位置，继续执行第1步；小于等于最小值，结束调整。

int a[] = {27,15,19,18,28,34,65,49,25,37};

代码如下：

void shiftDown(int* arr, int  n, int pos)
{
    //n为结点个数，pos为需要调整的位置
	int child = 2 * pos + 1;//左孩子
	while (child < n)
	{
		//找出左右孩子最小值
		if (child + 1 < n && arr[child] > arr[child + 1])
			++child;
		if (arr[child] < arr[pos])
		{
			swap(&arr[child], &arr[pos]);//交换
			pos = child;
			child = 2 * pos + 1;
		}
		else
			break;
	}
}

2.2.2 堆的创建

算法思想:

从倒数的第一个非叶子节点开始向下调整，一直调整到根节点，就可以调整成堆。
倒数第一个非叶子结点：(n-2) / 2

代码如下：

void createHeap(int* arr, int n)
{
	//从第一个非叶子结点开始
	int i = 0;
	for (i = (n - 2) / 2; i >= 0; i--)
	{
		shiftDown(arr, n, i);
	}
}

2.2.3 向上调整算法

算法思想：

大堆调整：首先和父节点进行比较，如果：大于父节点，交换，更新位置，从父节点位置继续向上看；小于等于父节点，结束调整。

小堆调整：首先和父节点进行比较，如果：小于父节点，交换，更新位置，从父节点位置继续向上看；大于等于父节点，结束调整。

代码如下：

//向上调整(小堆)
void shiftUp(int* arr, int n, int pos)
{
	int parent = (pos - 1) / 2;
	while (pos > 0)
	{
		if (arr[pos] < arr[parent])
		{
			swap(&arr[pos], &arr[parent]);
			pos = parent;
			parent = (pos - 1) / 2;
		}
		else
			break;
	}
}

2.2.4 堆的插入

算法思想：

尾插一个数据，再从尾插的数据进行向上调整，直到满足堆

代码如下：

void heapPush(Heap* hp, HDataType val)
{
	//检查容量
	checkCapacity(hp);
	//尾插
	hp->data[hp->size++] = val;
	//向上调整
	shiftUp(hp->data, hp->size, hp->size-1);
}

2.2.5 堆的删除：删除最值

算法思想：

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

代码如下：

void heapPop(Heap* hp)
{
	//判空
	if (heapEmpty(hp))
		return;
	//最大(最小)和最后一个元素交换
	swap(&hp->data[0], &hp->data[hp->size - 1]);
	//尾删
	hp->size--;
	//向下调整
	shiftDown(hp->data, hp->size, 0);
}

2.2.6 堆的全部代码实现

typedef int HDataType;
typedef struct Heap
{
	HDataType* data;
	int size;
	int capacity;
}Heap;

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//向下调整：logn（小堆）
void shiftDown(int* arr, int  n, int pos)
{
	int child = 2 * pos + 1;//左孩子
	while (child < n)
	{
		//找出左右孩子最小值
		if (child + 1 < n && arr[child] > arr[child + 1])
			++child;
		if (arr[child] < arr[pos])
		{
			swap(&arr[child], &arr[pos]);
			pos = child;
			child = 2 * pos + 1;
		}
		else
			break;
	}
}

//堆的创建
void createHeap(int* arr, int n)
{
	//从第一个非叶子结点开始
	int i = 0;
	for (i = (n - 2) / 2; i >= 0; i--)
	{
		shiftDown(arr, n, i);
	}
}


//向上调整(小堆)
void shiftUp(int* arr, int n, int pos)
{
	int parent = (pos - 1) / 2;
	while (pos > 0)
	{
		if (arr[pos] < arr[parent])
		{
			swap(&arr[pos], &arr[parent]);
			pos = parent;
			parent = (pos - 1) / 2;
		}
		else
			break;
	}
}

//初始化
void InitHeap(Heap* hp)
{
	if (hp == NULL)
		return;
	hp->capacity = hp->size = 0;
	hp->data = NULL;
}

//检查容量
void checkCapacity(Heap* hp)
{
	if (hp->size == hp->capacity)
	{
		hp->capacity = hp->capacity == 0 ? 1 : 2 * hp->capacity;
		hp->data = (HDataType*)realloc(hp->data, sizeof(HDataType)*hp->capacity);
	}
}

//堆的插入
void heapPush(Heap* hp, HDataType val)
{
	//检查容量
	checkCapacity(hp);
	//尾插
	hp->data[hp->size++] = val;
	//向上调整
	shiftUp(hp->data, hp->size, hp->size-1);
}


//堆的判空
int heapEmpty(Heap* hp)
{
	if (hp == NULL || hp->size == 0)
		return 1;
	return 0;
}

//堆的删除
void heapPop(Heap* hp)
{
	//判空
	if (heapEmpty(hp))
		return;
	//最大(最小)和最后一个元素交换
	swap(&hp->data[0], &hp->data[hp->size - 1]);
	//尾删
	hp->size--;
	//向下调整
	shiftDown(hp->data, hp->size, 0);
}

//取栈顶元素
HDataType heapTop(Heap* hp)
{
	return hp->data[0];
}

//堆的数据个数
int heapSize(Heap* hp)
{
	return hp->size;
}


//堆的销毁
void HeapDestory(Heap* hp)
{
	free(hp->data);
	hp->data = NULL; 
}

void printHeap(Heap* hp)
{
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->data[i]);
	}
	printf("\n");
}

3. 二叉树链式结构

3.1 二叉树链式结构的遍历

1.前序遍历：先访问根结点->然后是左子树->最后是右子树
2.中序遍历：先访问左子树->然后是根节点->最后是右子树
2.后序遍历：先访问左子树->然后是右子树->最后是根节点
3.层序遍历：首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

3.2 二叉树的全部实现代码

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

1.二叉树的创建，index需要传指针，这样可以真正的改变index，否则index只是局部变量，index起不到遍历数组的作用

2.二叉树节点个数：左子树+右子树+13.

3.二叉树高度：左右子树高度的最大值 + 1

4.层序遍历：用队列当容器

typedef char DataType;

//二叉树的结点
typedef struct BNode
{
	struct BNode* left;//左孩子
	struct BNode* right;//右孩子
	DataType data;
}Node;

//创建二叉链  前序
Node* BTreeCreate(DataType arr[], int* index) 
{
	if (arr[*index] == '#')
	{
		(*index)++;
		return NULL;
	}
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = arr[*index];
	(*index)++;
	node->left = BTreeCreate(arr, index);
	node->right = BTreeCreate(arr, index);
	return node;
}

//前序遍历  根-左-右
void bTreePrevOrder(Node* root)
{
	if (root == NULL)
		return;
	printf("%c ", root->data);
	bTreePrevOrder(root->left);
	bTreePrevOrder(root->right);
}


//中序遍历  左-根-右
void bTreeInOrder(Node* root)
{
	if (root)
	{
		bTreeInOrder(root->left);
		printf("%c ", root->data);
		bTreeInOrder(root->right);
	}
}


//后序遍历  左-右-根
void bTreePostOrder(Node* root)
{
	if (root)
	{
		bTreePostOrder(root->left);
		bTreePostOrder(root->right);
		printf("%c ", root->data);
	}
}


//节点个数  左子树+右子树+1
int BTreeSize(Node* root)
{
	if (root == NULL)
		return 0;
	return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}


//二叉树高度  max(左右子树的高度) + 1
int BTreeHeight(Node* root)
{
	if (root == NULL)
		return 0;
	int left = BTreeHeight(root->left);
	int right = BTreeHeight(root->right);
	return left > right ? left + 1 : right + 1;
}


//叶子节点个数 
int BTreeLeaf(Node* root)
{
	//空节点
	if (root == NULL)
		return 0;
	//叶子节点
	if (root->left == NULL && root->right == NULL)
		return 1;
	//非叶子节点
	return BTreeLeaf(root->left) + BTreeLeaf(root->right); 
}


//第K层节点个数   
int BTreeKSize(Node* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeKSize(root->left, k - 1) + BTreeKSize(root->right, k - 1);
}


//二叉树查找值为x的节点
Node* BTreeFind(Node* root, char val)
{
	if (root)
	{
		Node* node;
		if (root->data == val)
			return root;
		node = BTreeFind(root->left, val);
		if (node)
			return node;
		else
			return BTreeFind(root->right, val); 
	}
	else
		return NULL;
}



//层序遍历   用队列当作容器
void bTreeLevelOrder(Node* root)
{
	struct queue q;
	queueInit(&q);//队列初始化
	if (root)
		queuePush(&q, root);//队列入队
	while (!queueEmpty(&q))//队列判空
	{
		 Node* node = queueFront(&q);//获取队头元素
		queuePop(&q);//出队
		printf("%c ", node->data);
		if (node->left)//左孩子不为空，入队
			queuePush(&q, node->left);
		if (node->right)//右孩子不为空，入队
			queuePush(&q, node->right);
	}
}


//判断是否是完全二叉树
int isBTreeComplete(Node* root)
{
	queue q;
	queueInit(&q);
	if (root)
		queuePush(&q, root);
	while (!queueEmpty(&q))
	{
		Node* node = queueFront(&q);
		queuePop(&q);
		if (node)
		{
			queuePush(&q, node->left);
			queuePush(&q, node->right);
		}
		else
			break;
	}
	while (!queueEmpty(&q))
	{
		Node* node = queueFront(&q);
		queuePop(&q);
		if (node != NULL)
			return 0;
	}
	return 1;
}

//销毁二叉树
void BTreeDestory(Node** root)
{
	if (*root)
	{
		BTreeDestory(&((*root)->left));
		BTreeDestory(&((*root)->right));
		free(*root);
		*root = NULL;
	}
}

码农公寓

1.二叉树的概念及结构

2. 二叉树的顺序结构

3. 二叉树链式结构

相关文章