本章重點
樹的概念及結構
- 樹的相關概念
- 樹的表示
樹在實際中的運用
二叉樹概念及結構
- 概念
- 特殊的二叉樹：
- 二叉樹的性質
- 二叉樹的存盤結構
二叉樹的順序結構及實作
- 二叉樹的順序結構
- 堆的概念及結構
- 堆的性質
- 堆的實作
- - 堆向下調整演算法
  - 堆的創建
  - 建堆時間復雜度
  - 堆的插入
  - 堆的洗掉
  - 堆的代碼實作
- 堆的應用
- - 堆排序
  - TOP-K問題

禿頭俠們好呀，今天咱們來聊聊 二叉樹

本章重點

樹的概念及結構
二叉樹的概念及結構
二叉樹順序結構及實作

樹的概念及結構

樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，

在這里插入圖片描述

1、樹有一個特殊的結點，稱為根結點，根節點沒有前驅結點，
2、除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i<= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼，
3、因此，樹是遞回定義的，

注意：
1、樹形結構中，子樹之間不能有交集，否則就不是樹形結構
2、除了根節點外，其余結點有且僅有一個父節點
3、一棵有N個結點的樹，有N-1條邊

樹的相關概念

在這里插入圖片描述
節點的度：一個節點含有的子樹的個數稱為該節點的度；如上圖：A的為6

葉節點或終端節點：度為0的節點稱為葉節點；如上圖：B、C、H、I…等節點為葉節點

非終端節點或分支節點：度不為0的節點；如上圖：D、E、F、G…等節點為分支節點

雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；如上圖：A是B的父節點

孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；如上圖：B是A的孩子節點

兄弟節點：具有相同父節點的節點互稱為兄弟節點；如上圖：B、C是兄弟節點

樹的度：一棵樹中，最大的節點的度稱為樹的度；如上圖：樹的度為6

節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；

樹的高度或深度：樹中節點的最大層次；如上圖：樹的高度為4

堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點

節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先

子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫

森林：由m（m>0）棵互不相交的樹的集合稱為森林

樹的表示

樹結構相對線性表就比較復雜了，要存盤表示起來就比較麻煩了，既要保存值域，也要保存結點和結點之間的關系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等，我們這里就簡單的了解其中最常用的孩子兄弟表示法（左孩，右兄），

typedef int DataType;
struct Node
{
struct Node* firstChild1; // 第一個孩子結點
struct Node* pNextBrother; // 指向其下一個兄弟結點
DataType data; // 結點中的資料域
};

在這里插入圖片描述

樹在實際中的運用

檔案系統的目錄樹結構
在這里插入圖片描述在目前用樹表示的目錄結構中，從根目錄到任何資料檔案，有唯一通道，

二叉樹概念及結構

概念

一棵二叉樹是結點的一個有限集合，該集合:

或者為空
由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成

在這里插入圖片描述
從上圖可以看出：
1、二叉樹不存在度大于2的結點
2、二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

注意：對于任意的二叉樹都是由以下幾種情況復合而成的：
在這里插入圖片描述
讓我們來看看現實中的二叉樹：

特殊的二叉樹：

滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為k，且結點總數是2^(k-1) ，則它就是滿二叉樹，
完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹，要注意的是滿二叉樹是一種特殊的完全二叉樹，

二叉樹的性質

在這里插入圖片描述

二叉樹的存盤結構

二叉樹一般可以使用兩種結構存盤，一種順序結構，一種鏈式結構，

1、順序存盤

順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，而現實中使用中只有堆才會使用陣列來存盤，關于堆我們后面會講到，二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，

在這里插入圖片描述 2.、鏈式存盤

二叉樹的鏈式存盤結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系，通常的方法是鏈表中每個結點由三個域組成，資料域和左右指標域，左右指標分別用來給出該結點左孩子和右孩子所在的鏈結點的存盤地址，鏈式結構又分為二叉鏈和三叉鏈，當前我們學習中一般都是二叉鏈，

在這里插入圖片描述

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode{
struct BinTreeNode* Left; // 指向當前節點左孩子
struct BinTreeNode* Right; // 指向當前節點右孩子
BTDataType _data; // 當前節點值域
};

二叉樹的順序結構及實作

二叉樹的順序結構

普通的二叉樹是不適合用陣列來存盤的，因為可能會存在大量的空間浪費，而完全二叉樹更適合使用順序結構存盤，現實中我們通常把堆(一種二叉樹)使用順序結構的陣列來存盤，需要注意的是這里的堆和作業系統虛擬行程地址空間中的堆是兩回事，一個是資料結構，一個是作業系統中管理記憶體的一塊區域分段，

堆的概念及結構

在這里插入圖片描述

堆的性質

堆中某個節點的值總是不大于或不小于其父節點的值
堆總是一棵完全二叉樹
所有的陣列都可以表示成完全二叉樹，但是他不一定是堆

在這里插入圖片描述

堆的實作

堆向下調整演算法

現在我們給出一個陣列，邏輯上看做一顆完全二叉樹，我們通過從根節點開始的向下調整演算法可以把它調整成一個小堆，向下調整演算法有一個前提：左右子樹必須是一個堆，才能調整，

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

在這里插入圖片描述

堆的創建

下面我們給出一個陣列，這個陣列邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現在我們通過演算法，把它構建成一個堆，根節點左右子樹不是堆，我們怎么調整呢？這里我們從倒數的第一個非葉子節點的子樹開始調整，一直調整到根節點的樹，就可以調整成堆，

int a[] = {1,5,3,8,7,6};

在這里插入圖片描述

建堆時間復雜度

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明(時間復雜度本來看的就是近似值，多幾個節點不影響最終結果)

在這里插入圖片描述
因此：建堆的時間復雜度為O(N)，

堆的插入

先插入一個10到陣列的尾上，再進行向上調整演算法，直到滿足堆
在這里插入圖片描述

堆的洗掉

洗掉堆是洗掉堆頂的資料，將堆頂的資料根最后一個資料一換，然后洗掉陣列最后一個資料，再進行向下調整演算法
在這里插入圖片描述

堆的代碼實作

Heap.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int	HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void AdjustUp(HPDataType* a, int child);

void AdjustDown(HPDataType* a, int size, int parent);

void Swap(HPDataType* px, HPDataType* py);

void HeapInit(HP* hp);

void HeapDestroy(HP* hp);

void HeapPush(HP* hp,HPDataType x);

void HeapPop(HP* hp);

HPDataType HeapTop(HP* hp);

void HeapPrint(HP* hp);

bool HeapEmpty(HP* hp);

int	HeapSize(HP* hp);

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->capacity = hp->size = 0;
}

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;

	AdjustUp(hp->a, hp->size - 1);
}

void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

void HeapPrint(HP* hp)
{
	assert(hp);
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

bool HeapEmpty(HP* hp)
{
	assert(hp);

	return hp->size == 0;
}

void HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);

}

int HeapSize(HP* hp)
{
	assert(hp);

	return hp->size;
}

HPDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->a[0];
}

void AdjustDown(HPDataType* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child<size)
	{
		// 選出左右孩子中小的那一個
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		// 如果小的孩子小于父親，則交換，并繼續向下調整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}	
	}
}

堆的應用

堆排序

給你一個陣列int a[N]={x,x,x,x,x…}讓你按升序排列

我們先用一個笨辦法，建立一個N個數的小堆，堆頂的肯定是最小值，把這個最小值放到陣列里，然后pop一下堆疊頂，再取下一個次小值，

void HeapSort(int*a,int n)
{
    HP hp;
    HeapInit(&hp);
    for(int i=0;i<n;i++)
    {
        HeapPush(&hp,a[i]); 
    }
    for(int i=0;i<n;i++)
    {
        a[i]=HeapTop(&hp);
        HeapPop(&hp);
    }
    HeapDestroy(&hp);
}

這樣有什么問題嗎？
空間復雜度為O(N)，因為你又開辟了一個小堆，并且你這樣為了排序，還得寫一個堆實作，這里能不能有更優的方法呢？比如將空間復雜度控制到O(1)，

我們可以把陣列直接當成一個堆，那我們把這個堆調整為大堆還是小堆呢？
我們這里排的是升序，我們首先想到的是建小堆，因為小堆的堆頂元素是最小值，這樣我們就選出來最小值了，那我們怎么選出次小值呢？

我們只能把最小的那個值放到陣列首，然后剩下的再看成一個堆（如圖）
在這里插入圖片描述
但是這樣的問題很明顯，我們之前建立好的小堆被打亂了，我們現在只能把剩下的再重新建小堆，這時的時間復雜度變成了O(N*N) 那咱還不如直接冒泡排序呢，

所以我們不妨來試試排升序建大堆
建大堆后，堆頂是最大值，然后讓堆頂和最后的交換，向下調整，這樣最大的值就被放到最后了，然后最后一個數不看成堆里面的元素，現在堆頂又是次大值了，再和后面交換，向下調整，以此類推最后就排序好了，

我們用向下調整法建堆，上面說過了，建堆的時間復雜度為O(N)
然后再選堆頂的數扔后面，向下調整，每一次時間復雜度為O(logN)
總共N個數，所以是NlogN
**所以最終的堆排序的時間復雜度為O(NlogN)，**

升序：建大堆
降序：建小堆

//向下調整建堆
for(int i=(n-1-1)/2;i>=0;i--)
{
    AdjustDown(a,n,i);
}
//依次選數調整
for(int end=n-1;end>0;end--)
{
    Swap(&a[end],&a[0]);
    AdjustDown(a,end,0);
}

TOP-K問題

問題是在N個數中找出最大的前K個數（一般K遠小于N）

方法一：

將N個數降序排序，那么前K個數就是最大的

這種方法的問題是什么呢，殺雞用牛刀，人家讓你找前K個數，你把所有數都排了，時間復雜度最快是O(N*logN)

方法二：

將N個數依次插入大堆，Pop K次，每次取堆頂的資料，就是前K個最大的數

N個數建堆時間復雜度是O(N)，Pop K次的時間復雜度O(KlogN)
總時間復雜度為O(N+KlogN)

但是假設N非常大，N是10億，記憶體中存不下這些資料，他們存在檔案中，此時方法一、二都不能用了，因為他倆都得是在記憶體中進行計算，所以我們只能用方法三：

用前K個數建立一個K個數的小堆
剩下的N-K個數依次和堆頂的數比較，如果比堆頂的數大，就替換掉這個數，將堆頂的數Pop掉，然后再插入新數（因為是降序找最大的K個數，我們建的是小堆，所以堆頂是最小的數，當有比它大的數就替換它進堆）
最后堆里的K個數就是最大的前K個數

建立一個K個數的堆時間復雜度是O(K)
剩下N-K個數向下調整時間復雜度O( (N-K)*logK )
總時間復雜度為O(K+(N-K)*logK)≈O(N)

void PrintTopK(int*a,int n,int k)
{
    HP hp;
    HeapInit(&hp);
    for(int i=0;i<k;i++)
    {
         HeapPush(&hp,a[i]);
    }
    for(int i=k;i<n;i++)
    {
        if(a[i]>HeapTop(&hp))
        {
            HeapPop(&hp);
            HeapPush(&hp,a[i]);
        }
    }
    HeapPrint(&hp);
    HeapDestroy(&hp);
}

二叉樹鏈式結構的實作和相關內容放到下篇

感謝閱讀，我們下期再見
如有錯歡迎提出一起交流

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/382873.html

標籤：其他

上一篇：XShell收費？5款免費且超贊的SSH工具，一個比一個香

下一篇：二叉樹的遞回套路——最低公共祖先

資料結構【二叉樹】（堆實作）（堆排序）（TopK問題）

目錄

本章重點

樹的概念及結構

樹的相關概念

樹的表示

樹在實際中的運用

二叉樹概念及結構

概念

特殊的二叉樹：

二叉樹的性質

二叉樹的存盤結構

二叉樹的順序結構及實作

二叉樹的順序結構

堆的概念及結構

堆的性質

堆的實作

堆向下調整演算法

堆的創建

建堆時間復雜度

堆的插入

堆的洗掉

堆的代碼實作

堆的應用

堆排序

TOP-K問題