当前位置：网站首页>二叉树结构以及堆结构基础

二叉树结构以及堆结构基础

2022-06-27 07:31:00 【KevinJune】

1 二叉树结构

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

1、满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树[4] 。

2、完全二叉树：深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树 [4] 。

完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1 [4] 。

对于完全二叉树来说满足以下性质，例子：

2 堆结构

1. 堆结构就是用数组实现的完全二叉树结构

2. 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆

3. 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆

4. 堆结构的heapInsert与heapify操作

①如何把数组调整成一颗大根堆

heapinsert原理——每次都与父节点进行比较

将数组中的数字依次加入到堆中。对于每一个加入到堆中的数字，将其与其父节点的值进行比较，如果他大，则将他和他父节点的值进行交换。他的索引位置为 i ，则其父节点的索引位置为 (i-1)/2 。

注：-1/2的结果为0，所以index=0的时候也不用怕

#include<iostream>
#include<vector>
using namespace std;
 
void heapinsert(vector<int>&nums){
	if(!nums.size()) return;
 
	int temp=0, index=0;
	for(int i=0; i<nums.size(); i++){
 
		index=i;
		// -1/2的结果为0，所以index=0的时候也不用怕
		//不断的与父节点进行比较
		while(nums[index]>nums[(index-1)/2]){
			temp=nums[index];
			nums[index]=nums[(index-1)/2];
			nums[(index-1)/2]=temp;
			index=(index-1)/2;
		}
	}
	
	for(auto i:nums)
		cout<<i<<endl;
}
 
int main(){
	vector<int>nums={1,2,3,4,5,6,7,8,9};
	heapinsert(nums);
 
	return 0;
}

②heapify过程——每次都与子节点进行比较

堆中某个值发生了变化，如何调整。

比如大根堆中，索引位置为 i 的元素的值发生了改变（变小），则将其与左右两个孩子进行比较，将其与较大的孩子进行交换。左孩子的索引位置为 2*i+1 , 右孩子的索引位置为 2*i+2.

#include<iostream>
#include<vector>
using namespace std;
 
void heapify(vector<int>&nums){
	if(!nums.size()) return;
 
	int largest=0, i=0, temp=0;
	for(int index=0; index<nums.size(); index++){
		i=index;
		while((2*i+1)<nums.size()){
			
			//先判断右孩子是否越界，再选择两个孩子中的较大者，将大者的索引位置存入largest中
			largest=(2*i+2)<nums.size()?
				nums[2*i+1]>nums[2*i+2]?2*i+1:2*i+2
			:2*i+1;		
		
			//说明nums[i]已经不能再向下移动了
			if(nums[i]>=nums[largest]) break;
 
			//交换两个元素的值
			temp=nums[i];
			nums[i]=nums[largest];
			nums[largest]=temp;
 
			//此时该继续向下比较了
			i=largest;
		}
	}
	
	for(auto i:nums)
		cout<<i<<endl;
}
 
int main(){
	vector<int>nums={1,9,8,7,6,5,4,3,2};
	heapify(nums);
 
	return 0;
}

5. 堆结构的增大和减少

6. 优先级队列结构，介绍堆结构