二叉树和堆

目录

1.二叉树的概念及结构

1.1概念

1.2特殊的二叉树

1.3二叉树的性质

1.4二叉树的存储结构

2.二叉树的顺序结构及实现（堆）

2.1二叉树的顺序结构

2.2堆的概念及结构

2.3堆的实现

2.3.1堆的插入

2.3.2堆的删除

2.3.3 Heap.h

2.3.4 Heap.c

2.3.5 test.c

2.4堆的创建

2.4.1建堆的时间复杂度

1.向下调整算法：

2.向上调整算法：

2.5堆的应用

2.5.1堆排序

2.5.2 TOP-K问题

3.二叉树链式结构的实现

3.1二叉树的遍历

3.1.1 前序、中序及后序的遍历

3.1.2节点个数及高度

3.1.3二叉树的销毁

3.1.4层序遍历

3.1.5判断二叉树是否为完全二叉树

3.2二叉树的oj

1.二叉树的概念及结构

1.1概念

一颗二叉树是节点的一个有限集合，该集合：

        1.或者为空

        2.由一个根节点加上两颗别称为左子树和右子树的二叉树组成

从上图可以看出：

1.二叉树不存在度大于2的节点

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

注意：对于任意的二叉树都是由以下几种情况复合而成：

1.2特殊的二叉树

1.满二叉树：一个二叉树，如果每一层得节点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且节点总数是，则它就是满二叉树。

2.完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为k的，有n个节点的二叉树当且仅当每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时称为完全二叉树。注意的是满二叉树是一种特殊的完全二叉树。

1.3二叉树的性质

1. 若规定根结点的层数为 1 ，则一棵非空二叉树的 第 i 层上最多有个结点.

2. 若规定根结点的层数为 1 ，则 深度为 h 的二叉树的最大结点数是

/*

* 假设二叉树有 N 个结点

* 从总结点数角度考虑： N = n0 + n1 + n2    ①

*

* 从边的角度考虑， N 个结点的任意二叉树，总共有 N-1 条边

* 因为二叉树中每个结点都有双亲，根结点没有双亲，每个节点向上与其双亲之间存在一条边

* 因此 N 个结点的二叉树总共有 N-1 条边

* 因为度为 0 的结点没有孩子，故度为 0 的结点不产生边 ; 度为 1 的结点只有一个孩子，故每个度为 1 的结点 产生一条边 ; 度为 2 的结点有 2 个孩子，故每个度为 2 的结点产生两条边，所以总边数为： n1+2*n2

* 故从边的角度考虑： N-1 = n1 + 2*n2 ②

* 结合 ① 和 ② 得： n0 + n1 + n2 = n1 + 2*n2 - 1

* 即： n0 = n2 + 1

*/

4. 若规定根结点的层数为 1 ，具有 n 个结点的满二叉树的深度 ， h=。

1.4二叉树的存储结构

二叉树一般可以使用两种结构存储，一种是顺序结构，一种是链式结构

1.顺序存储

 顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间浪费。而现实中使用只有堆才会用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.链式存储

二叉树的链式存储结构是指用链表来表示一颗二叉树，即用链表来表示元素的逻辑关系。通常方法是链表中每个节点由三个域组成，数据域和左右指针，左右指针分别用来给出该节点的左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链。

typedef int BTDataType;
//二叉链
struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
};
//三叉链
struct BinaryTreeNode
{struct BinaryTreeNode* parent;struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
};

2.二叉树的顺序结构及实现（堆）

2.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆（一种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统的虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2.2堆的概念及结构

• 堆中某个节点的值总是不大于或小于其父节点的值；
• 堆总是一颗完全二叉树。

2.3堆的实现

2.3.1堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType temp =*p1;*p1 = *p2;*p2 = temp;
}void AdjustUp(HPDataType* a, int child)//向上调整算法
{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 HeapPush(Heap* hp, HPDataType x)//插入
{if (hp->capacity == hp->size){int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;hp->capacity = newcapacity;HPDataType* temp = (HPDataType*)realloc(hp->a, hp->capacity * sizeof(HPDataType));if (temp == NULL){perror("realloc fail");return;}hp->a = temp;}hp->a[hp->size] = x;hp->size++;AdjustUp(hp->a, hp->size - 1);
}

2.3.2堆的删除

void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] > a[child + 1]){child = child + 1;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(Heap* hp)//删除
{assert(hp);assert(hp->size > 0);Swap(&hp->a[0], &hp->a[hp->size - 1]);hp->size--;AdjustDown(hp->a, hp->size, 0);
}

2.3.3 Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>//typedef int BTDataType;
二叉链
//struct BinaryTreeNode
//{
//	struct BinaryTreeNode* left;
//	struct BinaryTreeNode* right;
//	BTDataType data;
//};
三叉链
//struct BinaryTreeNode
//{
//	struct BinaryTreeNode* parent;
//	struct BinaryTreeNode* left;
//	struct BinaryTreeNode* right;
//	BTDataType data;
//};
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;void HeapInit(Heap* hp);//初始化void HeapDestory(Heap* hp);//销毁void HeapPush(Heap* hp, HPDataType x);//插入void HeapPop(Heap* hp);//删除HPDataType HeapTop(Heap* hp);//取堆顶数据int HeapSize(Heap* hp);//数据个数bool HeapEmpty(Heap* hp);//判空void AdjustUp(HPDataType* a, int child);void AdjustDown(HPDataType* a, int n, int parent);void Swap(HPDataType* p1, HPDataType* p2);

2.3.4 Heap.c

#include"heap.h"
void HeapInit(Heap* hp)//初始化
{assert(hp);hp->a = NULL;hp->capacity = hp->size = 0;
}void HeapDestory(Heap* hp)//销毁
{assert(hp);free(hp->a);hp->a = NULL;hp->capacity = hp->size = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType temp =*p1;*p1 = *p2;*p2 = temp;
}void AdjustUp(HPDataType* a, int child)//向上调整算法
{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 HeapPush(Heap* hp, HPDataType x)//插入
{if (hp->capacity == hp->size){int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;hp->capacity = newcapacity;HPDataType* temp = (HPDataType*)realloc(hp->a, hp->capacity * sizeof(HPDataType));if (temp == NULL){perror("realloc fail");return;}hp->a = temp;}hp->a[hp->size] = x;hp->size++;AdjustUp(hp->a, hp->size - 1);
}void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] > a[child + 1]){child = child + 1;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(Heap* hp)//删除
{assert(hp);assert(hp->size > 0);Swap(&hp->a[0], &hp->a[hp->size - 1]);hp->size--;AdjustDown(hp->a, hp->size, 0);
}HPDataType HeapTop(Heap* hp)//取堆顶数据
{assert(hp);assert(hp->size > 0);return hp->a[0];
}
int HeapSize(Heap* hp)//数据个数
{assert(hp);return hp->size;
}bool HeapEmpty(Heap* hp)//判空
{assert(hp);return hp->size == 0;
}

2.3.5 test.c

#include"heap.h"void test1()
{int a[] = { 1,5,33,7,4,32,6,3,8,9,2 };Heap hp;HeapInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestory(&hp);
}int main()
{test1();return 0;
}

2.4堆的创建

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

2.4.1建堆的时间复杂度

1.向下调整算法：

向下调整算法的时间复杂度为O(N)。

2.向上调整算法：

2.5堆的应用

2.5.1堆排序

1.建堆

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

2.利用堆删除的思想来进行排序

void HeapSort(HPDataType* a, int n)
{//建堆从非叶子节点开始//降序建小堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}void test2()
{int a[] = { 1,5,33,7,4,32,6,3,8,9,2 };HeapSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); i++){printf("%d ", a[i]);}
}int main()
{test2();return 0;
}

2.5.2 TOP-K问题

     1.用数据的前K个元素建堆

void CreatNode()
{int n = 100000;srand((unsigned)time(NULL));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; i++){int x = (rand() + i) % 100000000;//+i防止重复数过多,并且数的大小不超过一亿fprintf(fin, "%d\n", x);}fclose(fin);
}void TopK()
{int k = 0;printf("请输入k>");scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail");return;}const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fout fail");}for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kminheap, k, i);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > kminheap[0]){kminheap[0] = x;AdjustDown(kminheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");
}int main()
{// CreatNode();TopK();return 0;
}

3.1二叉树的遍历

3.1.1 前序、中序及后序的遍历

所谓二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行对应的操作，并且每个节点只操作一次。按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历。

1. 前序遍历——访问根节点的操作发生在遍历其左右子树之前（根 左 右）。
2. 中序遍历——访问根节点的操作发生在遍历其左右子树之间（左 根 右）。
3. 后序遍历——访问根节点的操作发生在遍历其左右子树之后（左 右 根）。

//前序遍历
void PreOrder(TreeNode* root)
{if (root == NULL){printf("n ");return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

//中序遍历
void InOrder(TreeNode* root)
{if (root == NULL){printf("n ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

//后序遍历
void PostOrder(TreeNode* root)
{if (root == NULL){printf("n ");return ;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

//二叉树节点个数
int BinaryTreeSize(TreeNode* root)
{if (root == NULL){return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

//二叉树叶子节点个数
int BinaryTreeLeafSize(TreeNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

//二叉树高度
int BinaryTreeHight(TreeNode* root)
{if (root == NULL){return 0;}int leftHight = BinaryTreeHight(root->left);int rightHight = BinaryTreeHight(root->right);return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
}

TreeNode* BinaryTreeFind(TreeNode* root, TreeDataType x)//查找值为x的节点
{if (root == NULL)return NULL;if (root->data == x){return root;}//将左右子树查找的节点记录下来，找到就返回这个节点，如果不记录就不会返回TreeNode* ret1 = BinaryTreeFind(root->left, x);if (ret1){return ret1;}TreeNode* ret2 = BinaryTreeFind(root->right, x);if (ret2)return ret2;return NULL;
}

void DestoryTree(TreeNode* root)//销毁
{if (root == NULL){return;}DestoryTree(root->left);DestoryTree(root->right);free(root);
}

void LevelOrder(TreeNode* root)//层序遍历
{Queue pq;QInit(&pq);if (root)//根节点先进队列QPush(&pq, root);while (!QEmpty(&pq)){TreeNode* front = QueueFront(&pq);QPop(&pq);printf("%d ", front->data);//左右子树入队列if (front->left){QPush(&pq, front->left);}if (front->right){QPush(&pq, front->right);}}
}

bool BinaryTreeComplete(TreeNode* root)
{Queue pq;QInit(&pq);//根节点入队列if (root)QPush(&pq, root);while (!QEmpty(&pq)){TreeNode* front = QueueFront(&pq);QPop(&pq);//当队头为空的时候跳出if (front == NULL){break;}QPush(&pq, front->left);QPush(&pq, front->right);}//如果为完全二叉树，此时队列里全为空，如果出现非空则不是while (!QEmpty(&pq)){TreeNode* front = QueueFront(&pq);QPop(&pq);if (front != NULL){QDestory(&pq);return false;}}QDestory(&pq);return true;
}

bool isUnivalTree(struct TreeNode* root) 
{if(root == NULL)return true;if(root->left && root->left->val != root->val)return false;if(root->right && root->right->val != root->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{if(p == NULL&&q == NULL)return true;if(p == NULL||q == NULL)return false;if(p->val != q->val)return false;return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

bool _isSymmetric(struct TreeNode* p,struct TreeNode* q)
{if(p == NULL && q == NULL) return true;if(p == NULL || q == NULL)return false;if(p->val != q->val)return false;return _isSymmetric(p->left,q->right) && _isSymmetric(p->right,q->left);
}bool isSymmetric(struct TreeNode* root) 
{if(root == NULL)return true;struct TreeNode* left = root->left;struct TreeNode* right = root->right;return _isSymmetric(left,right);
}

int TreeSize(struct TreeNode*root)
{return root == NULL ? 0 : TreeSize(root->left) +TreeSize(root->right) + 1;
}void PreOrder(struct TreeNode* root,int* arr,int *i)
{if(root == NULL){return;}arr[(*i)++] = root->val;PreOrder(root->left,arr,i);PreOrder(root->right,arr,i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{*returnSize = TreeSize(root);int *ret = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;PreOrder(root, ret, &i);return ret;
}

bool issameTree(struct TreeNode* q, struct TreeNode *p)
{if(q == NULL && p == NULL){return true;}if(q == NULL || p == NULL){return false;}if(q->val != p->val){return false;}return issameTree(q->left,p->left) && issameTree(q->right,p->right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) 
{if(root == NULL){return false;}if(issameTree(root,subRoot)){return true;}return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);}

#include <stdio.h>
#include <stdlib.h>typedef struct TreeNode
{char val;struct TreeNode* left;struct TreeNode* right;
}TreeNode;TreeNode* CreatTree(char *arr,int *i)
{while(arr[*i] == '#'){(*i)++;return NULL;}TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->val = arr[(*i)++];root->left = CreatTree(arr, i);root->right = CreatTree(arr, i);return root;
}void InOrder(TreeNode* root)
{if(root == NULL){return;}InOrder(root->left);printf("%c ",root->val);InOrder(root->right);
}int main() 
{char arr[100];scanf("%s",arr);int i = 0;TreeNode* root = CreatTree(arr, &i);InOrder(root);return 0;
}