樹是計算機算法最重要的非線性結(jié)構(gòu)。因為樹能很好地描述結(jié)構(gòu)的分支關(guān)系和層次特性，所以在計算機科學(xué)和計算機應(yīng)用領(lǐng)域有著廣泛的應(yīng)用。這篇文章我就帶大家一起了解一下樹、二叉樹這種結(jié)構(gòu)，下篇文章會重點向大家介紹二叉樹的遍歷算法

一、樹概念及結(jié)構(gòu)

1.1 樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

·有一個特殊的結(jié)點，稱為根結(jié)點，根節(jié)點沒有前驅(qū)結(jié)點

·除根節(jié)點外，其余結(jié)點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹類似的子樹。

·每棵子樹的根結(jié)點有且只有一個前驅(qū)，可以有0個或多個后繼因此，樹是遞歸定義的。

注意：樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)

1.2 樹的相關(guān)概念

節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度；如上圖：A的為6

葉節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點；如上圖：B、C、H、I...等節(jié)點為葉節(jié)點

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

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

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

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

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

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

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

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

節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點；如上圖：A是所有節(jié)點的祖先

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

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

1.3 樹的表示

樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲表示起來就比較麻煩了，既然保存值域，也要保存結(jié)點和結(jié)點之間的關(guān)系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。

如下圖所示：

二、二叉樹概念及結(jié)構(gòu)

2.1 概念

什么是二叉樹？簡言之一棵二叉樹是結(jié)點的一個有限集合，該集合:

1. 或者為空

2. 由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成

如下圖示

從上圖我們可以看出二叉樹的兩個特點

1. 二叉樹不存在度大于2的結(jié)點

2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

注意：對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：

2.2 特殊的二叉樹：

1. 滿二叉樹：一個二叉樹，如果每一個層的結(jié)點數(shù)都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為K，且結(jié)點總數(shù)是，則它就是滿二叉樹。

2. 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K 的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。

2.3 二叉樹的性質(zhì)

1. 若規(guī)定根節(jié)點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有 2^(i - 1)個結(jié)點.

2. 若規(guī)定根節(jié)點的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點數(shù)是2^h - 1.

3. 對任何一棵二叉樹, 如果度為0其葉結(jié)點個數(shù)為n0 , 度為2的分支結(jié)點個數(shù)為n1 ,則有n0 ＝n2 ＋1.

4. 若規(guī)定根節(jié)點的層數(shù)為1，具有n個結(jié)點的滿二叉樹的深度，h=log2(n + 1) (是log以2 為底，n+1為對數(shù))

5. 對于具有n個結(jié)點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點從0開始編號，則對于序號為i的結(jié)點有：

1. 若i>0，i位置節(jié)點的雙親序號：(i-1)/2；i=0，i為根節(jié)點編號，無雙親節(jié)點.

2.若2i+1<n, 左孩子序號；如果2i + 1 >=n 無左孩子

3. 若2i+2<n, 右孩子序號；如果2i + 1 >=n 無右孩子

解釋：二叉樹存儲下標(biāo)從0開始就會出現(xiàn)這種結(jié)果

2.4 二叉樹的存儲結(jié)構(gòu)

1. 順序存儲

順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲，關(guān)于堆我們后面的章節(jié)會專門講解。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。

2. 鏈?zhǔn)酱鎯?/h4>
二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。通常的方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈，后面課程學(xué)到高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹等會用到三叉鏈。

三、實現(xiàn)完全二叉樹堆并實現(xiàn)堆排序

3.1 堆的概念和結(jié)構(gòu)

如果有一個關(guān)鍵碼的集合K = { ，，，…， }，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中，并滿足： = 且 >= ) i = 0，1， 2…，則稱為小堆(或大堆)。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。

堆的性質(zhì)：堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；

堆總是一棵完全二叉樹。

3.2 實現(xiàn)堆的難點

向上調(diào)整算法和向下調(diào)整算法

由于堆是一種非線性存儲結(jié)構(gòu)，因此我們在執(zhí)行堆的刪除時會比較復(fù)雜，涉及到向下調(diào)整算法。

原先我們在棧和隊列那講中的挪動數(shù)據(jù)覆蓋根的位置的數(shù)據(jù)刪除會導(dǎo)致堆的結(jié)構(gòu)被破壞了，父子間的結(jié)構(gòu)全亂了。

向下調(diào)整算法的思路：

1、第一個數(shù)（根位置）和最后一個位置進行交換。

2、刪除最后一個數(shù)據(jù)。

3、找出左右孩子中小的那個和父親比較，如果比父親小，交換，再從交換的孩子位置繼續(xù)往下調(diào)整。

過程如下圖所示：

向下調(diào)整算法
void* AdjustDown(HPDataType* a, size_t size, size_t root)
{
       size_t parent = root;
       size_t child = parent * 2 + 1;//默認是左孩子
       while (child < size)
       {
              //1、選出左右孩子中小的那個，而且保證不會越界訪問
              if (child + 1 < size && a[child + 1] < a[child])
              {
                      child++;//左孩子變?yōu)橛液⒆?
              }
              if (a[child]< a[parent])
              {
                      Swap(&a[child], &a[parent]);
                      parent = child;//繼續(xù)計算
                      child = parent * 2 + 1;//默認還是計算左孩子
              }
              else
              {
                      break;
              }
       }
}

為了保持堆的結(jié)構(gòu)，我們還要引入向上調(diào)整算法，由于兩種算法原理差不多而且向上調(diào)整比較簡單易懂，我直接上代碼了。

void Adjustup(HPDataType* a, size_t child)
{
       size_t parent = (child - 1) / 2;
       while (child > 0)
       {
              //小堆a[child] <a[parent],大堆a[child] > a[parent]時交換
              if (a[child] < a[parent])
              {
                      Swap(&a[child], &a[parent]);//因為是指針傳參，所以要&
                      child = parent;
                      parent = (child - 1) / 2;
              }
              else
              {
                      break;
              }
       }
}

3.3 小堆的實現(xiàn)

頭文件：

#pragma once
// 小堆
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
void PrintTopk(int* a, int n, int k);
void HeapInit(HP* php);//堆的初始化
void HeapDestory(HP* php);//堆的銷毀
void Swap(HPDataType* pa, HPDataType* pb);//交換
void HeapPrint(HP* php);
void AdjustDown(HPDataType* a, size_t size, size_t root);//堆的向下調(diào)整算法
//插入x以后，依舊保持堆
void HeapPush(HP* php, HPDataType x);
void Adjustup(HPDataType* a, size_t child);//堆的向上調(diào)整算法
//刪除堆頂?shù)臄?shù)據(jù)，（最小/最?。?
void HeapPop(HP* php);
bool HeapEmpty(HP* php);
size_t HeapSize(HP* php);
HPDataType HeapTop(HP* php);

源文件：

#include"Heap.h"
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}
void HeapDestory(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
void HeapPrint(HP* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
//涉及堆排序
void Adjustup(HPDataType* a, size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		//小堆a[child] <a[parent],大堆a[child] > a[parent]時交換
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);//因為是指針傳參，所以要&
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;//默認是左孩子
	while (child < size)
	{
		//1、選出左右孩子中小的那個，而且保證不會越界訪問
		if (child + 1 < size && a[child + 1] < a[child])//建大堆時< 改 >
		{
			++child;//左孩子變?yōu)橛液⒆?
		}
		if (a[child] < a[parent])//建大堆時< 改 >
		{
			Swap(&a[child], &a[parent]);
			parent = child;//繼續(xù)計算
			child = parent * 2 + 1;//默認還是計算左孩子
		}
		else
		{
			break;
		}
	}
}
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
 
	if (php->size == php->capacity)//滿了，需要擴容
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		//翻譯：新定義一個無符號的newCapacity = 原來的capacity，如果原來的capacity = 0, 就賦值為4，4不夠就再*二倍
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType)* newCapacity);
		if (tmp == NULL)
		{
			printf("reallpc failed\n");
			exit(-1); 
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	//尾插
	php->a[php->size] = x;
	++php->size;
	//向上調(diào)整保持是一個小堆
	Adjustup(php->a, php->size - 1);
}
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	--php->size;
	AdjustDown(php->a, php->size, 0);
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
size_t HeapSize(HP* php)
{
	return php->size;
}
HPDataType HeapTop(HP* php)
{
	return php->a[0];
}

3.4 堆的應(yīng)用-堆排序

堆排序即利用堆的思想來進行排序，總共分為兩個步驟：

1. 建堆

升序：建大堆

降序：建小堆

2. 利用堆刪除思想來進行排序建堆和堆刪除中都用到了向下調(diào)整，因此掌握了向下調(diào)整，就可以完成堆排序。

代碼示例：

void AdjustDown(HPDataType* a, size_t size, size_t root)
{
       size_t parent = root;
       size_t child = parent * 2 + 1;//默認是左孩子
       while (child < size)
       {
              //1、選出左右孩子中小的那個，而且保證不會越界訪問
              if (child + 1 < size && a[child + 1] <a[child])//建大堆時< 改 >
              {
                      ++child;//左孩子變?yōu)橛液⒆?
              }
              if (a[child] < a[parent])//建大堆時< 改 >
              {
                      Swap(&a[child], &a[parent]);
                      parent = child;//繼續(xù)計算
                      child = parent * 2 + 1;//默認還是計算左孩子
              }
              else
              {
                      break;
              }
       }
}
void HeapSort2(int* a, int n)
{
	//向上調(diào)整--建堆
	//for (int i = 1; i < n; ++i)
	//{
	//	AdjustUp(a, i);
	//}
	//向下調(diào)整--建堆O（N）
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);//為什么向下調(diào)整要多傳一個參數(shù)，因為當(dāng)child>=size 時說明已經(jīng)到了邊界
	}
	size_t end = n - 1;//n - 1是最后一個數(shù)據(jù)的下標(biāo)
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		//次大的數(shù)到了倒數(shù)第二個位置
		--end;
	}
}
int main()
{
//	TestHeap();
	int a[] = { 4 , 2, 7, 8, 5, 1, 0, 6 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

四.Top-k問題

TOP-K問題：即求數(shù)據(jù)結(jié)合中前K個最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。

比如：專業(yè)前10名、世界500強、富豪榜、游戲中前100的活躍玩家等。

對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果數(shù)據(jù)量非常大，排序就不太可取了(可能數(shù)據(jù)都不能一下子全部加載到內(nèi)存中)。

最佳的方式就是用堆來解決，基本思路如下：

1. 用數(shù)據(jù)集合中前K個元素來建堆前k個最大的元素，則建小堆前k個最小的元素，則建大堆 2. 用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素。

將剩余N-K個元素依次與堆頂元素比完之后，堆中剩余的K個元素就是所求的前K個最小或者最大的元素。

因為N非常大，k非常小，所以復(fù)雜度相當(dāng)于0（N）

設(shè)置10個比100萬大的數(shù)，然后讓電腦隨機生成數(shù)，找出大于100萬的10個數(shù)。

void PrintTopk(int* a, int n, int k)
{
	//1、建堆-- 用a中前k個元素建堆
	int* kminHeap = (int*)malloc(sizeof(int)* k);
	assert(kminHeap);
	//2、將剩余n-k元素依次與堆頂元素交換，不滿則替換
	for (int i = 0; i < k; i++)
	{
		kminHeap[i] = a[i];//將前k個數(shù)給給它
	}
	//第k-1個是最后一位數(shù)的下標(biāo)，(k - 1 -1) / 2是倒數(shù)第一個非葉子結(jié)點
	//建小堆
	for (int j = (k - 1 - 1) / 2; j >= 0; --j)
	{
		AdjustDown(kminHeap, k, j);
	}
	//2、將剩余n - k元素依次與堆頂元素交換，不滿則替換
	for (int i = k; i < n; ++i)
	{
		if (a[i] > kminHeap[0])
		{
			kminHeap[0] = a[i];
			AdjustDown(kminHeap, k, 0);//從根這個點向下調(diào)
		}
	}
	for (int j = 0; j < k; j++)
	{
		printf("%d ", kminHeap[j]);
	}
	printf("\n");
	free(kminHeap);
}
void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int)* n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2305] = 1000000 + 6;
	a[99] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[0] = 1000000 + 1000;
	PrintTopk(a, n, 10);
}
int main()
{
	TestTopk();
	return 0;
}

總結(jié)

本文近7500字，主要從樹以及二叉樹的概念和結(jié)構(gòu)展開詳講，再詳細介紹了堆（特殊的二叉樹）這種數(shù)據(jù)結(jié)構(gòu)的概念、原理以及實現(xiàn)，還有堆的重要應(yīng)用：堆排序以及TOPK問題等，希望大家讀后能夠有所收獲。

到此這篇關(guān)于C語言近萬字為你講透樹與二叉樹的文章就介紹到這了,更多相關(guān)C語言樹與二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

軟件下載

源碼下載

軟件編程

網(wǎng)絡(luò)編程

在線工具

數(shù)據(jù)庫

CMS

常用工具

C語言近萬字為你講透樹與二叉樹

目錄

一、樹概念及結(jié)構(gòu)

1.1 樹的概念

1.2 樹的相關(guān)概念

1.3 樹的表示

二、二叉樹概念及結(jié)構(gòu)

2.1 概念

2.2 特殊的二叉樹：

2.3 二叉樹的性質(zhì)

2.4 二叉樹的存儲結(jié)構(gòu)

1. 順序存儲

三、實現(xiàn)完全二叉樹堆并實現(xiàn)堆排序

3.1 堆的概念和結(jié)構(gòu)

3.2 實現(xiàn)堆的難點

3.3 小堆的實現(xiàn)

3.4 堆的應(yīng)用-堆排序

四.Top-k問題

總結(jié)

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

C語言近萬字為你講透樹與二叉樹

目錄

一、樹概念及結(jié)構(gòu)

1.1 樹的概念

1.2 樹的相關(guān)概念

1.3 樹的表示

二、二叉樹概念及結(jié)構(gòu)

2.1 概念

2.2 特殊的二叉樹：

2.3 二叉樹的性質(zhì)

2.4 二叉樹的存儲結(jié)構(gòu)

1. 順序存儲

三、實現(xiàn)完全二叉樹堆并實現(xiàn)堆排序

3.1 堆的概念和結(jié)構(gòu)

3.2 實現(xiàn)堆的難點

3.3 小堆的實現(xiàn)

3.4 堆的應(yīng)用-堆排序

四.Top-k問題

總結(jié)

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

一、樹概念及結(jié)構(gòu)

二、二叉樹概念及結(jié)構(gòu)