Data Structure--二叉树的顺序结构及实现

冷不防 2022-10-31 02:00 147阅读 0赞

### 二叉树的顺序结构及实现 ###

*  二叉树顺序存储
 *  堆
 *   *  (1)堆的具体结构
     *  (2)堆的接口声明
     *  (3)堆的实现
     *   *  1.初始化
         *  2.堆插入
         *  3.堆删除
         *  4.堆容量检查
         *  5.小堆向下调整
         *  6.大堆向下调整
         *  7.小堆向上调整
         *  8.大堆向上调整
         *  9.传出堆首
         *  10.判空
         *  11.堆排序

# 二叉树顺序存储 #

存储方式分为两种:完全和非完全  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]

# 堆 #

当所有的元素按照**完全二叉树**存储在一维数组中的数据,我们就叫做**堆**,将根节点最大的堆叫做最大堆，根节点最小的堆叫做最小堆。  
**堆的性质:**  
1.堆中某个节点的值总是不大于或不小于其父节点的值；  
2.堆总是一棵完全二叉树。

## (1)堆的具体结构 ##

typedef int HDataType;
    
    typedef struct heap{ 
    
    	HDataType* _data;	//数据
    	int _size;			//存储大小
    	int _capacity;		//存储容量
    }heap;

## (2)堆的接口声明 ##

//1.初始化
    void heapInit(heap* hp);
    //2.堆插入
    void heapPush(heap* hp, HDataType val);
    //3.堆删除
    void heapPop(heap* hp);
    //4.堆容量检查
    void checkCapacity(heap* hp);
    //5.小堆向下调整
    void shiftDown(int * arr, int n, int cur);
    //6.大堆向下调整
    void shiftDownD(int * arr, int n, int cur);
    //7.小堆向上调整
    void shiftUp(int* arr, int n, int cur);
    //8.大堆向上调整
    void shiftUpD(int* arr, int n, int cur);
    //9.传出堆首
    HDataType heapTop(heap* hp);
    //10.判空
    int heapEmpty(heap* hp);
    //11.堆排序
    void test();

## (3)堆的实现 ##

### 1.初始化 ###

void heapInit(heap* hp){ 
    	
    	if (hp == NULL)		//判空
    		return;
    
    	hp->_data = NULL;	//元素为空
    	hp->_capacity = hp->_size = 0;		//容量和大小为0
    }

### 2.堆插入 ###

因为对于堆来说,你要始终必须满足大小的一个顺序,所以,每插入一个元素,就要进行依次的调整,调整后符合规则的才是新的堆

void heapPush(heap* hp, HDataType val){ 
    	
    	if (hp == NULL)		//判空
    		return;
    	//检查空间
    	checkCapacity(hp);
    
    	//尾插
    	hp->_data[hp->_size++] = val;
    	//小堆向上调整
    	shiftUp(hp->_data, hp->_size, hp->_size - 1);
    }

### 3.堆删除 ###

同样删除也需要调整

void heapPop(heap* hp){ 
    	
    	if (hp->_size > 0){ 
    		//交换
    		Swap(hp->_data[0], &hp->_data[hp->_size - 1]);
    		//尾删
    		hp->_size--;
    		//从堆顶向下调整
    		shiftDown(hp->_data, hp->_size, 0);
    	}
    }

### 4.堆容量检查 ###

void checkCapacity(heap* hp){ 
    	
    	if (hp->_size == hp->_capacity){ 
    		
    		int newC = hp->_capacity == 0 ? 1 : 2 * hp->_capacity;	//等于则开辟2倍
    		hp->_data = (HDataType*)realloc(hp->_data, sizeof(HDataType)*newC);	//直接realloc开辟空间
    		hp->_capacity = newC;	//更新
    	}
    }

### 5.小堆向下调整 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]

void shiftDown(int * arr, int n, int cur){ 
    	//找到孩子的位置
    	//左孩子
    	int child = 2 * cur + 1;	//这个为左孩子的性质
    
    	while (child < n){ 
    		//左右孩子中找到最小的
    		if (child + 1 < n && arr[child + 1] < arr[child])//如果右孩子小于左孩子
    			++child;	//直接++
    		//和当前数据比较
    		//1.调整
    		if (arr[child] < arr[cur]){ 		//并让左孩子和父节点比较,如果孩子节点小直接交换
    			int tmp = arr[child];
    			arr[child] = arr[cur];
    			arr[cur] = tmp;
    
    			//位置更新
    			cur = child;
    			child = 2 * cur + 1;	//继续循环
    		}
    		//2.不调整
    		else
    			break;
    	}
    }

### 6.大堆向下调整 ###

void shiftDownD(int * arr, int n, int cur){ 
    	
    	
    	int child = 2 * cur + 1;
    
    	while (child < n){ 
    		
    		if (child + 1 < n && arr[child + 1] > arr[child]) //和上面的一样,只不过交换了符号
    			++child;
    		
    		if (arr[child] > arr[cur]){ 		//交换了符号
    			int tmp = arr[child];
    			arr[child] = arr[cur];
    			arr[cur] = tmp;
    
    			
    			cur = child;
    			child = 2 * cur + 1;
    		}
    		//2.不调整
    		else
    			break;
    	}
    }

### 7.小堆向上调整 ###

void shiftUp(int* arr, int n, int cur){ 
    
    	//和父节点进行比较
    	int parent = (cur - 1) / 2;		//向上就直接和父节点比较就可以了
    
    	while (cur > 0){ 			//存在时
    		if (arr[cur] < arr[parent]){ 	//如果子节点小,则交换
    
    			int tmp = arr[cur];
    			arr[cur] = arr[parent];
    			arr[parent] = tmp;
    
    			//更新
    			cur = parent;
    			parent = (cur - 1) / 2;		//继续循环,这里可以去看看上一篇的二叉树的性质
    		}
    		else
    			break;
    	}
    }

### 8.大堆向上调整 ###

void shiftUpD(int* arr, int n, int cur){ 
    
    	
    	int parent = (cur - 1) / 2;
    
    	while (cur > 0){ 
    		if (arr[cur] > arr[parent]){   //同上,只交换符号
    
    			int tmp = arr[cur];
    			arr[cur] = arr[parent];
    			arr[parent] = tmp;
    
    			
    			cur = parent;
    			parent = (cur - 1) / 2;
    		}
    		else
    			break;
    	}
    }

### 9.传出堆首 ###

HDataType heapTop(heap* hp){ 
    	
    	return hp->_data[0];	//直接返回第一个元素
    }

### 10.判空 ###

int heapEmpty(heap* hp){ 
    
    	if (hp == NULL || hp->_size == 0)	//判空
    		return 1;
    	else
    		return 0;
    }

### 11.堆排序 ###

一样的,每发生一次元素的增删都要进行调整一次

void test(){ 
    	
    	int arr[] = { 20,17,4,16,5,3};		//随机定义数组
    	int n = sizeof(arr) / sizeof(arr[0]);		//看有多少个元素
    	//建堆O(n)
    	for (int i = (n - 2) / 2; i >= 0; --i){ 	//这里的是双亲序号,进行循环
    		
    		shiftDown(arr, n, i);	//分别向下调整
    	}
    	//堆排序 nlog(n)
    	int end = n - 1;	//定义整形变量
    
    	while (end > 0){ 	//循环
    		
    		Swap(&arr[0], &arr[end]);	//基础的交换两个节点,自己写出来这个接口
    									//交换堆头和堆尾的元素
    		shiftDown(arr, end, 0);		//向下调整
    		end--;						//循环进行
    	}
    }

这是二叉树顺序结构的实现,大家多理解就可以了,多看看上一篇中**二叉树的性质**,挺重要的!!!多敲代码!!!一起加油!!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/021554b0855f4d2790becaaedaa84eb9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221024/f60446a7e2d74cfd9e16c3a2034e0a7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]: /images/20221024/6e39010fa6ac44848ebf7d78da794736.png