1.树
1.1树的基本概念
树是一种非线性的数据结构，它是由n个有限节点组成的一个具有层次关系的集合。叫做树是因为像一个倒挂的树，有节点和树枝
有一个特殊的节点，叫做根节点，根节点没有前驱节点。
除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合 Ti(1 <= i<= m) 又是⼀棵结构与树类似的子树。每棵子树的根结点有且只有⼀个前驱，可以 有 0 个或多个后继。因此，树是递归定义的。
1.2 树的表示
struct TreeNode
{
//左孩子
struct TreeNode* leftchild;
//右兄弟
struct TreeNode* rightbrother;
int data;//节点中的数据域
}
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
2.二叉树
2.1 二叉树的特点
在树形结构中，我们最常用的就是二叉树，⼀棵二叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左子树和右子树的二叉树组成或者为空。
从上图可以看出⼆叉树具备以下特点： 1. 二叉树不存在度大于 2 的结点 2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
2.2 现实中的二叉树
2.3 特殊的二叉树
2.3.1 满二叉树
⼀个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果⼀个二叉树的层数为 K ，且结点总数是2的k次方减1，则它就是满二叉树。
满二叉树F（h)=2^0+2^1+2^2+...+2^(h-1) 等差数列最后算下来是F(h)=2^h-1 假设这棵树是N个节点，F(h)=2^h-1=N h=log(N+1),以2为底 满二叉树：每一层的节点数都达到最大
2.3.2 完全二叉树
完全二叉树：前h-1层都是满的，最后一层不满最后一层从左到右必须是连续的，没有空断
2.3.3 二叉树的性质
若规定根节点的层数为1，一棵非空二叉树的第i层最多有2的i次方减1个节点；
若规定根节点的层数为1，深度为h的二叉树最大节点数是2的h次方减1；
若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度 h = log2 (n + 1) ( log 以2为底， n+1 为对数)
3.二叉树的存储
3.1 堆的概念
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
堆具有以下性质 • 堆中某个结点的值总是不大于或不小于其父结点的值； • 堆总是⼀棵完全二叉树。
3.2 堆的实现
//Heap.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int capacity;
int size;
}HP;
//默认初始化堆
void HPInit(HP* php);
//销毁堆
void HPDestroy(HP* php);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//向上调整
void AdjustUp(HPDataType* a, int child);
//在堆中插入数据
void HPPush(HP* php, HPDataType x);
//删除堆顶数据
void HPPop(HP* php);
//判空
bool HPEmpty(HP* php);
//获取堆顶数据
HPDataType HPTop(HP* php);
//交换父亲和孩子位置的数据
void Swap(HPDataType* p1, HPDataType* p2);
//Heap.c
#include"Heap.h"
//默认初始化堆
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
//销毁堆
void HPDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
//在堆中插入数据
void HPPush(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, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc failed!");
return;
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] == x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
//交换数据
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 (child > 0)
{
if (a[child] < a[parent])//小堆，父亲数据小于孩子数据，否则需要调整
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整数据
void AdjustDown(HPDataType* a, int n, int parent)
{
//定义孩子节点
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//删除堆顶的数据
void HPPop(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);//0：把堆顶的元素已经删除了，剩下的数据不是一个堆了，但是根的左右子树还分别是堆，所以要从0的位置开始调整，把剩下的元素调整为一个新的堆
//php->size:传参传元素个数
}
//获取堆顶的数据
HPDataType HPTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
//判空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
//test.c
#include"Heap.h"
void TestHeap1()
{
int a[] = { 4,2,8,6,7,5,3,9,10 };
HP hp;
HPInit(&hp);
for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
{
HPPush(&hp, a[i]);
}
int k = 0;
scanf("%d", &k);//取出小堆里面的前k个数据
while (k--)
{
printf("%d", HPTop(&hp));
HPPop(&hp);
}
/*while (!HPEmpty(&hp))
{
printf("%d", HPTop(&hp));
HPPop(&hp);
}*/
}
int main(void)
{
TestHeap1();
return;
}
3.3 重点标注
3.3.1 向上调整画图解析
3.3.2 向下调整画图解析
图中提出改正：n是堆中元素个数！当孩子数据大于或者等于元素个数的时候，循环结束！
void HPPush(HP* php，HPDataType x);插入，
1.先将元素插入到堆的末尾，即最后一个孩子之后；
2.插入之后如果堆的性质遭到破坏，将新插入节点顺着其双亲往上调整到合适的位置即可
Pop删除：堆顶的数据（根位置）挪动覆盖删除堆顶数据，关系全乱了，兄弟变成父子，最好的办法就是将根数据和最后一个子数据互换，向下调整算法，小的去当孩子，左右孩子是小堆 1.将堆顶元素与堆中最后一个元素进行交换2.删除堆中最后一个元素3.将堆顶元素向下调整到满足堆特性为止
4. 时间复杂度分析
4.1 向下调整建堆的时间复杂度分析
4.2向上调整建堆的时间复杂度分析
性质分析：
向下调整：节点数量多，调整次数少；节点数量少，调整次数多。
向上调整：节点数量多，调整次数多；节点数量少，调整次数少。
5. 实现链式结构二叉树
用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//创建节点的空间
BTNode* BuyNode(int val)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = val;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
BTNode* CreateTree()
{
//创建每一个节点
BTNode* n1 = BuyNode(1);
BTNode* n2 = BuyNode(2);
BTNode* n3 = BuyNode(3);
BTNode* n4 = BuyNode(4);
BTNode* n5 = BuyNode(5);
BTNode* n6 = BuyNode(6);
//连接起来成树
n1->left = n2;
n1->right = n4;
n2->left = n3;
n4->left = n5;
n4->right = n6;
return n1;
}
//前序遍历
//根 左子树 右子树
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
//计算堆的数量
//思路：判断树是否为空，为空返回0；不为空则左子树的数量+右子树的数量+1（根节点）
int TreeHeapSize(BTNode* root)
{
return root == NULL ? 0 : TreeHeapSize(root->left) + TreeHeapSize(root->right) + 1;
}
//计算叶子的数量
//思路：判断树是否为空，为空返回0；不为空：返回左右子树叶子数量
//叶子的特点：左右子叶子指向空
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
//计算树的高度
//思路：判断树是否为空，为空返回0；不为空：左右子树最高的一边加1
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}
int main(void)
{
BTNode* root = CreateTree();
PrevOrder(root);
printf("\n");
printf("TreeHeapSize:%d\n", TreeHeapSize(root));
printf("TreeLeafSize:%d\n", TreeLeafSize(root));
printf("TreeHeight:%d\n", TreeHeight(root));
}
以上判断树的高度过程中会有重复调用的问题：这里可以使用fmax函数避免这一问题 ：
int fmax(int x,int y)
{
return x>y? x:y;
}
int TreeHeight(BTNode* root)
{
if(root == NULL)
return 0;
return famx((TreeHeight(root->left),TreeHeight(root->right))+1;
}
5.1 前中序遍历递归
//前序遍历
//根 左子树 右子树
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);
}
前序遍历递归调用画图分析：
5.2 求二叉树第k层的节点个数
思路：判断树是不是空树，是空树就返回k；判断k要是等于1，第一层只有一个节点，返回1；接着调用TreeLevelKSize找左右子树中是否有k。
BTNode* TreeLevelKSize(BTNode* root,int k)
{
if(root==NULL)
return 0;
if(k==1)
return 1;
return TreeLevelKSize(root->left,k-1)+TreeLevelKSize(root->right,k-1);
}
5.3 查找值为x的节点
思路：判断树是不是空树，如果是空树返回NULL；不是空树，判断根是不是要找的x，如果是返回根；如果都没有找到就创建两个新的节点分别去遍历左子树和右子树，找到了就返回。
BTNode* TreeFind(BTNode* root,BTDataType x)
{
if(root == NULL)
return NULL;
if(root == x)
return root;
BTNode* ret1 = TreeFind(root->left,x);
if(ret1)
return ret1;
BTNode* ret2 = TreeFind(root->right,x);
if(ret2)
return ret2;
return NULL;
}
5.4 销毁二叉树
void TreeDestory(BTNode* root)
{
if (root == NULL)
return;
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
6.二叉树算法OJ题
6.1单值二叉树
https://leetcode.cn/problems/univalued-binary-tree/description/
思路：根为空，返回NULL；根不为空，分别判断左右子树的值是否等于根的值，左子树不为空且不等于根的值，右子树不为空且不等于根的值，返回false，调用左右子树继续判断.
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);
}
6.2 相同的树
https://leetcode.cn/problems/same-tree/description/
思路：判断两棵树是否为空，为空返回true;再判断两棵树是否其一为空，其一为空返回false;接着就是两棵树的根都不为空的情况了，两个根的值不相等返回false；相等就调用判断左右子树。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *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);
}
6.3 二叉树前序遍历
https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int TreeSize(struct TreeNode* root)
{
return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void PrevOrder(struct TreeNode* root,int*a,int*pi)
{
if(root==NULL)
{
return;
}
a[(*pi)++]=root->val;
PrevOrder(root->left,a,pi);
PrevOrder(root->right,a,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize=TreeSize(root);
int*a=(int*)malloc(sizeof(int)*(*returnSize));
int i=0;
PrevOrder(root,a,&i);
return a;
}
6.3.1 二叉树中序遍历
https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
int TreeSize(struct TreeNode* root)
{
return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void Inorder(struct TreeNode* root,int*a,int*pi)
{
if(root==NULL)
return;
Inorder(root->left,a,pi);
a[(*pi)++]=root->val;
Inorder(root->right,a,pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize=TreeSize(root);
int* a=(int*)malloc(sizeof(int)*(*returnSize));
int i=0;
Inorder(root,a,&i);
return a;
}
6.4二叉树的构建和遍历
https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef
注意：构建二叉树：获取char类型的数组a，a有100个元素，scanf让用户输入，还需要数组下标，主函数中定义i；BTNode*CreateTree(参数传数组和数组元素下标）；当数组a为空时（a[(*pi)] == '#')，让(*pi)++变成#后面的值，接着返回NULL；
中序遍历二叉树：打印root的时候，用%c。
#include
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* CreateTree(char*a,int*pi)
{
if(a[*pi]=='#')
{
(*pi)++;
return NULL;
}
BTNode* root=(BTNode*)malloc(sizeof(BTNode));
root->val=a[(*pi)++];
root->left=CreateTree(a,pi);
root->right=CreateTree(a,pi);
return root;
}
void InOrder(BTNode*root)
{
if(root==NULL)
return;
InOrder(root->left);
printf("%c ",root->val);
InOrder(root->right);
}
int main() {
char a[100];
scanf("%s",a);
int i=0;
BTNode* root=CreateTree(a,&i);
InOrder(root);
return 0;
}
#include"StackQueue.h"
//层序遍历
void TreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root != NULL)
QueuePush(&q, root);//如果root不为空就插进去
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);//节点释放掉了还能访问吗
//队头删除的是QNode,front返回的是里面的data，把队列的头节点删除不会影响树的节点
printf("%d", front->data);
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
QueueDestroy(&q);
}
//主函数
6.5 另一棵子树
https://leetcode.cn/problems/subtree-of-another-tree/description/
思路：判断root是否为空，为空返回NULL，subRoot一定不为空
如果root和subRoot的值相等，现在就可以转换成是否为相同的树来解答isSameTree,如果根相等而且isSameTree也是成立的，那就说明是另一棵子树；否则调用isSubTree继续判断。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSametree(struct TreeNode*p,struct TreeNode* q)
{
if(p==NULL&&q==NULL)
return true;
if(q==NULL||p==NULL)
return false;
if(p->val!=q->val)
return false;
return isSametree(p->left,q->left)&&isSametree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
if(root==NULL)
return false;
if(root->val==subRoot->val&&isSametree(root,subRoot))
return true;
return isSubtree(root->right,subRoot)||isSubtree(root->left,subRoot);
}
7.判断是否是完全二叉树
完全二叉树假设有h层，第h-1层是满的，第h层不是满的但是连续的 1.层序遍历走，空也进队列 2.遇到第一个空节点时，开始判断，后面全空就是完全二叉树，后面有非空就不是完全二叉树 不可能出现，遇到空时后面还有非空没有进队列，
后面非空，一定是前面非空的孩子当层序出现的的时候，
前面非空都出完了，那他的孩子一定进队列了。
//判断是否是完全二叉树
bool TreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root != NULL)
QueuePush(&q);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//遇到第一个空，就可以开始判断，如果队列中还有非空，就不是完全二叉树
if (front == NULL)
{
break;
}
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//如果有非空一定不是完全二叉树
if (front)
{
QueueDestory(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
8.二叉树的性质
对任何一棵二叉树,如果度为 0 ，其叶结点个数为n0, 度为 2 的分支结点个数为n2,则有n0 =n2+1
爱考选择题！