赞
踩
数是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
• 节点的度:一个节点含有的子树的个数称为该节点的度;如上图:A的为2
• 叶节点:度为0的节点称为叶子节点;如上图:D、E、F节点为叶子节点
• 非终端节点或分支节点:度不为0的节点; 如上图:B、C为分支节点
• 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点
• 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点
• 兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点
• 树的度:一棵树中,最大的节点的度称为树的度;如上图:树的度为2
• 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
• 树的高度或深度:树中节点的最大层次;如上图:树的高度为3
• 堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:B、F互为堂兄弟节点
• 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
• 以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
• 由m棵互不相交的树的集合称为森林
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表示法,孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{
struct Node* firstChild1;
struct Node* pNextBrother;
DataType data;
};
一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点:
二叉树一般可以使用两种存储结构,一种顺序结构,一种链式结构。
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前介绍的是二叉链,后面课程学到高阶数据结构如红黑树等会用到三叉链。
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
};
- 若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.4.1中提到了堆,那么什么是堆呢?
堆从分类来分,分为大堆和小堆。从性质来看,堆其实是一个特别的完全二叉树,这个特别的完全二叉树中所有的父亲节点的值要么都大于等于子节点值(大堆),要么小于等于子节点值(小堆)。
堆的性质:
1.堆中某个节点的值总是不大于或不小于其父节点的值;
2.堆总是一棵完全二叉树。
首先先定义一个堆
.h文件
#include<assert.h>
#include<stdbool.h>
#include<time.h>
typedef int HeapDateType;
typedef struct Heap
{
HeapDateType* arr;
int size;
int capacity;
}HP;
//初始化
void HeapInit(HP* hp);
//销毁
void HeapDestory(HP* hp);
.c文件
#include"Heap.h"
//初始化
void HeapInit(HP* hp)
{
hp->arr = NULL;
hp->capacity = hp->size = 0;
}
//销毁
void HeapDestory(HP* hp)
{
assert(hp);
free(hp->arr);
hp->capacity = hp->size = 0;
}
堆的插入思路:
堆的插入代码:
.h文件
//插入数据
void HeapPush(HP* hp, HeapDateType x);
//向上调整
void AjustUp(HeapDateType* arr, int child);
.c文件
//向上调整 void AjustUp(HeapDateType* arr, int child) { assert(arr); int parent = (child - 1) / 2; while (child > 0) { //大于号是大堆,小于号是小堆 if (arr[child] > arr[parent]) { Swap(&arr[parent], &arr[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } //插入数据 void HeapPush(HP* hp, HeapDateType x) { //检查一下是否需要扩容 if (hp->capacity == hp->size) { hp->capacity = hp->capacity == 0 ? 4 : hp->capacity * 2; } HeapDateType* ptr = (HeapDateType*)realloc(hp->arr, hp->capacity * sizeof(HeapDateType)); if (ptr == NULL) { perror("HeapPushBack::realloc"); } hp->arr = ptr; hp->arr[hp->size++] = x; AjustUp(hp->arr, hp->size - 1); }
堆顶的删除思路:
堆顶删除的代码:
.h文件
//删除堆顶数据
void HeapPop(HP* hp);
//向下调整
void AjustDown(HeapDateType* arr, int len, int parent);
.c文件
//向下调整 void AjustDown(HeapDateType* arr, int len, int parent) { assert(arr); int child = parent * 2 + 1; while (child < len) { //大于号是大堆,小于号是小堆 if (child + 1 < len && arr[child + 1] > arr[child]) { child++; } //大于号是大堆,小于号是小堆 if (arr[child] > arr[parent]) { Swap(&arr[parent], &arr[child]); parent = child; child = parent * 2 + 1; } else { break; } } } //删除堆顶数据 void HeapPop(HP* hp) { assert(hp); assert(!HeapIsEmpty(hp)); //交换 Swap(&hp->arr[0], &hp->arr[hp->size - 1]); hp->size--; //向下调整 AjustDown(hp->arr, hp->size, 0); }
.h文件
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> #include<time.h> typedef int HeapDateType; typedef struct Heap { HeapDateType* arr; int size; int capacity; }HP; //初始化 void HeapInit(HP* hp); //销毁 void HeapDestory(HP* hp); //插入数据 void HeapPush(HP* hp, HeapDateType x); //删除堆顶数据 void HeapPop(HP* hp); //打印 void HeapPrint(HP* hp); //向上调整 void AjustUp(HeapDateType* arr, int child); //向下调整 void AjustDown(HeapDateType* arr, int len, int parent); //断空 bool HeapIsEmpty(HP* hp); //堆大小 int HeapSize(HP* hp); //堆顶 HeapDateType HeapTop(HP* hp); //交换 void Swap(HeapDateType* px, HeapDateType* py);
.c文件
#include"Heap.h" //交换 void Swap(HeapDateType* px, HeapDateType* py) { HeapDateType tmp = *px; *px = *py; *py = tmp; } //初始化 void HeapInit(HP* hp) { hp->arr = NULL; hp->capacity = hp->size = 0; } //销毁 void HeapDestory(HP* hp) { assert(hp); free(hp->arr); hp->capacity = hp->size = 0; } //向上调整 void AjustUp(HeapDateType* arr, int child) { assert(arr); int parent = (child - 1) / 2; while (child > 0) { //大于号是大堆,小于号是小堆 if (arr[child] > arr[parent]) { Swap(&arr[parent], &arr[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } //向下调整 void AjustDown(HeapDateType* arr, int len, int parent) { assert(arr); int child = parent * 2 + 1; while (child < len) { //大于号是大堆,小于号是小堆 if (child + 1 < len && arr[child + 1] > arr[child]) { child++; } //大于号是大堆,小于号是小堆 if (arr[child] > arr[parent]) { Swap(&arr[parent], &arr[child]); parent = child; child = parent * 2 + 1; } else { break; } } } //插入数据 void HeapPush(HP* hp, HeapDateType x) { //检查一下是否需要扩容 if (hp->capacity == hp->size) { hp->capacity = hp->capacity == 0 ? 4 : hp->capacity * 2; } HeapDateType* ptr = (HeapDateType*)realloc(hp->arr, hp->capacity * sizeof(HeapDateType)); if (ptr == NULL) { perror("HeapPushBack::realloc"); } hp->arr = ptr; hp->arr[hp->size++] = x; AjustUp(hp->arr, hp->size - 1); } //删除堆顶数据 void HeapPop(HP* hp) { assert(hp); assert(!HeapIsEmpty(hp)); //交换 Swap(&hp->arr[0], &hp->arr[hp->size - 1]); hp->size--; //向下调整 AjustDown(hp->arr, hp->size, 0); } //断空 bool HeapIsEmpty(HP* hp) { return hp->size == 0; } //堆大小 int HeapSize(HP* hp) { return hp->size; } //堆顶 HeapDateType HeapTop(HP* hp) { assert(!HeapIsEmpty(hp)); return hp->arr[0]; } //打印 void HeapPrint(HP* hp) { for (int i = 0; i < hp->size; i++) { printf("%d ", hp->arr[i]); } printf("\n"); }
说到时间复杂度,就要考虑到最坏情况。那么假设完全二叉树的每一个节点都需要调整需要多少时间复杂度呢?
因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):
堆排序的思路:
建堆代码(方法1):
//构建大堆
//方法1
for (int i = 1; i < n; i++)
{
AjustUp(a, i);
}
建堆代码(方法2):
//方法2
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AjustDown(a, n, i);
}
堆排序代码:
void HeapSort(int* a, int n) { assert(a); //构建大堆 //方法1 //for (int i = 1; i < n; i++) //{ // AjustUp(a, i); //} //方法2 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AjustDown(a, n, i); } for (int end = n - 1; end > 0; end--) { Swap(&a[end], &a[0]); AjustDown(a, end, 0); } }
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
//在n个数中找出最大的前K个 void PrintTopK(int* arr, int n, int k) { HP hp; HeapInit(&hp); //先建立一个小堆 for (int i = 0; i < k; i++) { HeapPush(&hp, arr[i]); } for (int i = k; i < n; i++) { if (arr[i] > hp.arr[0]) { HeapPop(&hp); HeapPush(&hp, arr[i]); } } for (int i = 0; i < k; i++) { printf("%d ", hp.arr[i]); } printf("\n"); } void test02() { int arr[10000] = { 0 }; for (int i = 0; i < 10000; i++) { int t = rand() % 10000; arr[i] = t; } arr[131] = 10001; arr[141] = 10002; arr[151] = 10003; arr[161] = 10004; arr[171] = 10005; arr[181] = 10006; arr[191] = 10007; arr[1311] = 10008; arr[885] = 10009; arr[240] = 10010; PrintTopK(arr, 10000, 10); }
typedef char BTDataType;
typedef struct BinaryTree
{
struct BinaryTree* left;
struct BinaryTree* right;
BTDataType val;
}BTNode;
前序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果
//二叉树前序遍历 根 左子树 右子树
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
printf("%c ", root->val);
PreOrder(root->left);
PreOrder(root->right);
}
}
中序遍历也可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最左边开始垂直掉到地上),然后从左往右数,得出的结果便是中序遍历的结果。
//二叉树中序遍历 左子树 根 右子树
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
InOrder(root->left);
printf("%c ", root->val);
InOrder(root->right);
}
}
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
后序遍历就像是剪葡萄,我们要把一串葡萄剪成一颗一颗的。
就是围着树的外围绕一圈,如果发现一剪刀就能剪下的葡萄(必须是一颗葡萄)(也就是葡萄要一个一个掉下来,不能一口气掉超过1个这样),就把它剪下来,组成的就是后序遍历了。
//二叉树后序遍历 左子树 右子树 根
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->val);
}
}
口诀
前序遍历: 先根 再左 再右
中序遍历: 先左 再根 再右
后序遍历: 先左 再右 再根
层次遍历很好理解,就是从根节点开始,一层一层,从上到下,每层从左到右,依次写值就可以了。
//层序遍历 void LevelOrder(BTNode* root) { Queue q; Init_Queue(&q); //先入根节点 Push_Queue(&q, root); while (!Empty(&q)) { BTNode* front = Front_Queue(&q); //出当前节点 Pop_Queue(&q); printf("%c ", front->val); if (front->left != NULL) { Push_Queue(&q,front->left); } if (front->right != NULL) { Push_Queue(&q, front->right); } } printf("\n"); }
//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
else
{
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
}
当一个节点的左孩子和右孩子都为空时,该节点就是叶子节点。
//二叉数叶子结点个数 int BinaryTreeLeafSize(BTNode* root) { //当左孩子和右孩子都是空的就是叶子结点 if (root == NULL) { return 0; } if (root->left = NULL && root->right == NULL) { return 1; } else { return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); } }
求第K层节点数的问题可以转换成左子树第K-1层节点数+右子树第K-1层节点数,由此递归下去。
//二叉树第K层节点数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k==1)
{
return 1;
}
int LeftKSize = BinaryTreeLevelKSize(root->left, k - 1);
int RightKSize = BinaryTreeLevelKSize(root->right, k - 1);
return LeftKSize + RightKSize;
}
//二叉树查找值为X的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->val = x) { return root; } BTNode* LeftNode = BinaryTreeFind(root->left, x); if (LeftNode != NULL) { return LeftNode; } BTNode* RightNode = BinaryTreeFind(root->right, x); if (RightNode != NULL) { return RightNode; } return NULL; }
//二叉树深度
int BinaryDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int LeftDepth = BinaryDepth(root->left);
int RightDepth = BinaryDepth(root->right);
return LeftDepth > RightDepth ? LeftDepth + 1 : RightDepth + 1;
}
判断的思路:
//判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; Init_Queue(&q); Push_Queue(&q, root); while (Empty(&q)) { BTNode* front = Front_Queue(&q); Pop_Queue(&q); if (front) { Push_Queue(&q, front->left); Push_Queue(&q, front->right); } else { break; } } while (!Empty(&q)) { BTNode* front = Front_Queue(&q); if (front != NULL) { Destory_Queue(&q); return false; } Pop_Queue(&q); } Destory_Queue(&q); return true; }
.h文件
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include"Queue.h" typedef char BTDataType; typedef struct BinaryTree { struct BinaryTree* left; struct BinaryTree* right; BTDataType val; }BTNode; //二叉树前序遍历 void PreOrder(BTNode* root); //二叉树中序遍历 void InOrder(BTNode* root); //二叉树后序遍历 void PostOrder(BTNode* root); //层序遍历 void LevelOrder(BTNode * root); //二叉树结点个数 int BinaryTreeSize(BTNode* root); //二叉数叶子结点个数 int BinaryTreeLeafSize(BTNode* root); //二叉树第K层节点数 int BinaryTreeLevelKSize(BTNode* root, int k); //二叉树查找值为X的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); //判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode * root); //二叉树深度 int BinaryDepth(BTNode* root); //二叉树销毁 void BinaryTreeDestory(BTNode *root);
.c文件
#include"BinaryTree.h" //二叉树前序遍历 根 左子树 右子树 void PreOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } else { printf("%c ", root->val); PreOrder(root->left); PreOrder(root->right); } } //二叉树中序遍历 左子树 根 右子树 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } else { InOrder(root->left); printf("%c ", root->val); InOrder(root->right); } } //二叉树后序遍历 左子树 右子树 根 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } else { PostOrder(root->left); PostOrder(root->right); printf("%c ", root->val); } } //层序遍历 void LevelOrder(BTNode* root) { Queue q; Init_Queue(&q); Push_Queue(&q, root); while (!Empty(&q)) { BTNode* front = Front_Queue(&q); Pop_Queue(&q); printf("%c ", front->val); if (front->left != NULL) { Push_Queue(&q,front->left); } if (front->right != NULL) { Push_Queue(&q, front->right); } } printf("\n"); } //二叉树结点个数 int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } else { return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right); } } //二叉数叶子结点个数 int BinaryTreeLeafSize(BTNode* root) { //当左孩子和右孩子都是空的就是叶子结点 if (root == NULL) { return 0; } if (root->left = NULL && root->right == NULL) { return 1; } else { return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); } } //二叉树第K层节点数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL) { return 0; } if (k==1) { return 1; } int LeftKSize = BinaryTreeLevelKSize(root->left, k - 1); int RightKSize = BinaryTreeLevelKSize(root->right, k - 1); return LeftKSize + RightKSize; } //二叉树查找值为X的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->val = x) { return root; } BTNode* LeftNode = BinaryTreeFind(root->left, x); if (LeftNode != NULL) { return LeftNode; } BTNode* RightNode = BinaryTreeFind(root->right, x); if (RightNode != NULL) { return RightNode; } return NULL; } //判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; Init_Queue(&q); Push_Queue(&q, root); while (Empty(&q)) { BTNode* front = Front_Queue(&q); Pop_Queue(&q); if (front) { Push_Queue(&q, front->left); Push_Queue(&q, front->right); } else { break; } } while (!Empty(&q)) { BTNode* front = Front_Queue(&q); if (front != NULL) { Destory_Queue(&q); return false; } Pop_Queue(&q); } Destory_Queue(&q); return true; } //二叉树深度 int BinaryDepth(BTNode* root) { if (root == NULL) { return 0; } int LeftDepth = BinaryDepth(root->left); int RightDepth = BinaryDepth(root->right); return LeftDepth > RightDepth ? LeftDepth + 1 : RightDepth + 1; } //二叉树销毁 使用递归 先释放左子树在释放右子树最后释放根 void BinaryTreeDestory(BTNode* root) { if (root == NULL) { return; } BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); free(root); }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。