目錄
1 -> 樹的概念及結構
1.1 -> 樹的概念
1.2 -> 樹的相關概念
1.3 -> 樹的表示
1.4 -> 樹在實際中的運用(表示文件系統(tǒng)的目錄樹結構)
2 -> 二叉樹概念及結構
2.1 -> 二叉樹的概念
2.2 -> 現(xiàn)實中的二叉樹
2.3 -> 特殊的二叉樹
2.4 -> 二叉樹的性質
2.5 -> 二叉樹的存儲結構
3 -> 二叉樹的順序結構及實現(xiàn)
3.1 -> 二叉樹的順序結構
3.2 -> 堆的概念及結構
3.3 -> 堆的實現(xiàn)
3.3.1 -> 堆向下調整算法
3.3.2 -> 堆的創(chuàng)建
3.3.3 -> 建堆的時間復雜度
3.3.4 -> 堆的插入
3.3.5 -> 堆的刪除
3.3.6 -> 堆的代碼實現(xiàn)
Heap.h
Heap.c
3.4 -> 堆的應用
3.4.1 -> 堆排序
4 -> 二叉樹鏈式結構的實現(xiàn)
4.1 -> 前置說明
4.2 -> 二叉樹的遍歷
4.2.1 -> 前序、中序和后序遍歷
?4.3 -> 節(jié)點個數(shù)以及高度
1 -> 樹的概念及結構
1.1 -> 樹的概念
樹是一種非線性的數(shù)據(jù)結構，它是由n(n >= 0)個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，葉朝下。
- 有一個特殊的結點，稱為根結點，根結點沒有前驅結點。
- 除根結點外，其余結點被分成M(M > 0)個互不相交的集合T1、T2、……、Tn，其中每一個集合Ti(1 <= i <= m)又是一棵結構與樹類似的子樹。每棵樹的根結點有且只有一個前驅，可以有0個或多個后繼。
- 樹是遞歸定義的。
注：
樹形結構中，子樹之間不能有交集，否則就不是樹形結構。
1.2 -> 樹的相關概念
節(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 -> 樹的表示
樹結構相對線性表比較復雜，要存儲表示起來比較麻煩，既然保存值域，也要保存結點和結點之間的關系，實際中樹有很多種表示方式，如：雙親表示法、孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。最常用的是孩子兄弟表示法。
#include <iostream>
using namespace std;
typedef int DataType;
typedef struct Node
{
struct Node* _firstChild1; // 第一個孩子結點
struct Node* _pNextBrother; // 指向其下一個兄弟結點
DataType _data; // 結點中的數(shù)據(jù)域
}Node;
int main()
{
return 0;
}
1.4 -> 樹在實際中的運用(表示文件系統(tǒng)的目錄樹結構)
2 -> 二叉樹概念及結構
2.1 -> 二叉樹的概念
一棵二叉樹是結點的一個有限集合，該集合：
- 或為空
- 由一個根結點加上兩顆分別稱為左子樹和右子樹的二叉樹組成
從上圖可以看出：
- 二叉樹不存在度大于2的結點
- 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
注：
對于任意二叉樹都是由以下幾種情況復合而成的：
2.2 -> 現(xiàn)實中的二叉樹
2.3 -> 特殊的二叉樹
- 滿二叉樹：一個二叉樹，如果每一個層的結點數(shù)都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為K，且結點總數(shù)是，則它就是滿二叉樹。
- 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結構，完全二叉樹是由滿二叉樹引出的。對于深度為K的，有n個結點的二叉樹，當且僅當每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。
2.4 -> 二叉樹的性質
- 若規(guī)定根結點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有個結點。
- 若規(guī)定根結點的層數(shù)為1，則深度為h的二叉樹的最大結點數(shù)是。
- 對任何一棵二叉樹，如果度為0其葉結點個數(shù)為，度為2的分支結點個數(shù)為，則有
。
- 若規(guī)定根結點的層數(shù)為1，具有n個結點的滿二叉樹的深度，
，(ps:
是log以2為底，n+1為對數(shù))。
- 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序對所有結點從0開始編號，則對于序號為i的結點有：
- 若i > 0，i位置結點的雙親序號：(i - 1) / 2；i = 0，i為根結點編號，無雙親結點
- 若2i + 1 < n，左孩子序號：2i + 1，2i + 1 >= n否則無左孩子
- 若2i + 2?< n，右孩子序號：2i + 2，2i + 2 >= n否則無右孩子
2.5 -> 二叉樹的存儲結構
二叉樹一般可以使用兩種結構存儲，一種順序結構，一種鏈式結構。
1. 順序存儲：
順序結構存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。
2. 鏈式存儲：
二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。 通常的方法是鏈表中每個結點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址 。鏈式結構又分為二叉鏈和三叉鏈。
#include <iostream>
using namespace std;
typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向當前節(jié)點左孩子
struct BinTreeNode* _pRight; // 指向當前節(jié)點右孩子
BTDataType _data; // 當前節(jié)點值域
};
// 三叉鏈
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向當前節(jié)點的雙親
struct BinTreeNode* _pLeft; // 指向當前節(jié)點左孩子
struct BinTreeNode* _pRight; // 指向當前節(jié)點右孩子
BTDataType _data; // 當前節(jié)點值域
};
3 -> 二叉樹的順序結構及實現(xiàn)
3.1 -> 二叉樹的順序結構
普通的二叉樹不適合用數(shù)組存儲，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。現(xiàn)實中我們通常把堆(一種二叉樹)使用順序結構的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數(shù)據(jù)結構，一個是操作系統(tǒng)中內存管理的一塊區(qū)域分段。
3.2 -> 堆的概念及結構
如果有一個關鍵碼的集合?，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中，并滿足：且
(
且
) i = 0,1,2，……，則稱為小堆(或大堆)。將根結點的最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆。
堆的性質：
- 堆中某個結點的值總是不大于或不小于其父節(jié)點的值；
- 堆總是一棵完全二叉樹。
3.3 -> 堆的實現(xiàn)
3.3.1 -> 堆向下調整算法
現(xiàn)在給出一個數(shù)組，邏輯上看做一棵完全二叉樹。我們通過從根結點開始的向下調整算法可以把它調整成一個小堆。向下調整算法有一個前提：左右子樹必須是一個堆，才能調整。
int arr[] = {27,15,19,18,28,34,65,49,25,37};
3.3.2 -> 堆的創(chuàng)建
int arr[] = {1,5,3,8,7,6};
3.3.3 -> 建堆的時間復雜度
因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明(時間復雜度本來看的就是近似值，多幾個結點不影響結果)。
因此：建堆的時間復雜度為O(N).
3.3.4 -> 堆的插入
先插入一個10到數(shù)組的尾上，再進行向上調整算法，直到滿足堆。
3.3.5 -> 堆的刪除
刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)根最后一個數(shù)據(jù)一換，然后刪除數(shù)組最后一個數(shù)據(jù)，再進行向下調整算法。
3.3.6 -> 堆的代碼實現(xiàn)
Heap.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#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 HeapInit(HP* php);
// 堆的銷毀
void HeapDestory(HP* php);
// 堆的向上調整
void AdjustUp(HPDataType* a, int child);
// 堆的向下調整
void AdjustDown(HPDataType* a, int child);
// 堆的插入
void HeapPush(HP* php, HPDataType x);
// 堆的刪除
void HeapPop(HP* php);
// 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(HP* php);
// 堆的數(shù)據(jù)個數(shù)
int HeapSize(HP* php);
// 堆的判空
bool HeapEmpty(HP* php);Heap.c
#include "Heap.h"
// 堆的初始化
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
// 堆的銷毀
void HeapDestory(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->capacity = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 堆的向上調整
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0)
while (child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
// 堆的向下調整
void AdjustDown(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0)
while (child > 0)
{
if (a[child] < a[parent])
{
HPDataType tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
// 堆的插入
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
php->size++;
AdjustDwon(php->a, php->size - 1);
}
// 堆的刪除
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
// 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
return php->a[0];
}
// 堆的數(shù)據(jù)個數(shù)
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
// 堆的判空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}3.4 -> 堆的應用
3.4.1 -> 堆排序
堆排序即利用堆的思想來進行排序，總共分兩個步驟：
1. 建堆
- 升序：建大堆
- 降序：建小堆
2. 利用堆刪除思想來進行排序
建堆和堆刪除中都用到了向下調整，因此掌握了向下調整，就可以完成堆排序。
4 -> 二叉樹鏈式結構的實現(xiàn)
4.1 -> 前置說明
手動快速創(chuàng)建簡單的二叉樹：
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->_left = node2;
node1->_right = node4;
node2->_left = node3;
node4->_left = node5;
node4->_right = node6;
return node1;
}注：
上述代碼并不是創(chuàng)建二叉樹的方式。
4.2 -> 二叉樹的遍歷
4.2.1 -> 前序、中序和后序遍歷
學習二叉樹結構，最簡單的方式就是遍歷。所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點進行相應的操作，并且每個節(jié)點只操作一次。訪問結點所做的操作依賴于具體的應用問題。 遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎。
按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結構遍歷：
- 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點的操作發(fā)生在遍歷其左右子樹之前。
- 中序遍歷((Inorder Traversal)——訪問根結點的操作發(fā)生在遍歷其左右子樹之中(間)。
- 后序遍歷(Postorder Traversal)——訪問根結點的操作發(fā)生在遍歷其左右子樹之后。
由于被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。
前序遍歷：
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}中序遍歷：
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}后序遍歷：
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}4.2.2 -> 層序遍歷
層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設二叉樹的根節(jié)點所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點，然后從左到右訪問第2層上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層訪問樹的結點的過程就是層序遍歷。
層序遍歷：
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
if(front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
printf("\n");
QueueDestroy(&q);
}?4.3 -> 節(jié)點個數(shù)以及高度
// 求節(jié)點的個數(shù)
int BTreeSize(BTNode* root)
{
/*if (root == NULL)
return 0;
return BTreeSize(root->left)
+ BTreeSize(root->right)
+ 1;*/
return root == NULL ? 0 : BTreeSize(root->left)
+ BTreeSize(root->right) + 1;
}
// 求葉子節(jié)點的個數(shù)
int BTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL
&& root->right == NULL)
{
return 1;
}
return BTreeLeafSize(root->left)
+ BTreeLeafSize(root->right);
}
// 求二叉樹的高度
int BTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftHeight = BTreeHeight(root->left);
int rightHeight = BTreeHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
// 二叉樹第k層結點個數(shù)
int BTreeLevelKSize(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BTreeLevelKSize(root->left, k - 1)
+ BTreeLevelKSize(root->right, k - 1);
}
// 二叉樹查找值為x的結點
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* ret1 = BTreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = BTreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}感謝各位大佬支持?。?！文章來源：http://www.zghlxwxcb.cn/news/detail-838967.html
大佬們互三啦?。。?/strong>文章來源地址http://www.zghlxwxcb.cn/news/detail-838967.html
到了這里，關于【海賊王的數(shù)據(jù)航海：利用數(shù)據(jù)結構成為數(shù)據(jù)海洋的霸主】探究二叉樹的奧秘的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
