目录
学完次章节，我们二叉树就入门了，这些内容只能算二叉树的 1/5 内容，学习完这些内容多刷LeetCode上关于二叉树递归的题目，刷200道就可以入门了(简单题为主)，后续还有更多需要我们去学习的
树的概念及结构
树是一种非线性的数据结构，它是由 n（n>=0）个有限结点组成一个具有层次关系的集合
我们通常规定根节点开始为第一层，如果是空树就是第 0 层， 依次类推
如下图示例：
概念
- 结点的度：一个结点含有的子树的个数称为该节点的度，例如A为6，度为0的叫做叶子节点或者终端节点
- 兄弟节点：具有相同的父亲的结点，指的是亲兄弟
- 一棵树的度：一棵树中最大节点的度称为一棵树的度。 如上图，这棵树的度是 6
- 树的层次：从根开始，根为第一层、根得到子节点为第二层，以此类推。
- 树的高度或深度：树中节点最大的层次。如上深度为4。
二叉树的概念及结构
概念
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点: 1，每个结点最多有两棵子树，即二又树不存在度大于2的结点。
2.二叉树的子树有左右之分，其子树的次序不能颠倒
二叉树的性质
1，若规定根结点的层数为 i，则一棵非空二叉树的第 i 层上最多有2^(i-1) 个节点。
2，若规定根节点的层数为 i，则深度为 h 的二叉树得到最大结点数是 2^h -1 (求满二叉树，最多的结点数)
3，对任何一棵二叉树，如果度为0的叶子结点个数为 n0，度为2的分支节点个数为 n2，则 n0 = n2 + 1 (叶子结点比度为2的多一个)
满二叉树和完全二叉树
如图所示：
满二叉树
满二叉树：指从根节点开始每一层都是满的
满二叉树：总节点数 2^n - 1
完全二叉树
完全二叉树：假设有 K 层，前 K-1 层都是满的，第 K 层可以不满，但是必须从左到右连续
完全二叉树可以是满二叉树，满二叉树不一定是完全二叉树
深度的计算
二叉树顺序结构及实现
顺序存储
满二叉树和完全二叉树可以用数组存储，如果不是满二叉树和完全二叉树使用链表存储，用数组存储会用空间的浪费，因为一些位置要空出来
如图所示：我们针对满二叉树和完全二叉树使用顺序存储，不会造成空间的浪费，如果不是满二叉树和完全二叉树，使用顺序存储就会造成空间的浪费
重要概念：
父亲的下标是 i ，左孩子的下标是 2 * i + 1, 右孩子的下标是 2 * i + 2
孩子的下标是 i， 父亲的下标是 (i - 1) / 2
堆的概念
堆：由数组组成
逻辑结构：完全二叉树
物理结构：数组
大堆和小堆的概念：
数组建堆
主要依赖向下调整算法
小堆向下调整算法要求：调整的左右子树都是小堆
大堆向下调整算法要求：调整的左右子树都是大堆
向下调整
前提：左右子树都是小堆/大堆，根节点这棵树不满足，那么就可以使用向下调整算法
根节点开始调整
左右孩子比较一下，父亲和小的那个孩子进行交换，不断重复这个操作
为什么和小的那个孩子交换呢？？？
因为都是小堆结构，把小的数据往前挪，大的往后挪，数据依旧保持小的在前，大的在后(除根节点)那么向下调整的时间复杂度是多少？（N个节点，h是高度）
从根节点发出开始调整，最坏的情况下，需要调整这颗二叉树的高度次，二叉树的高度是logN (底数为2)， 满二叉树的高度是 log(N + 1), 完全二叉树是范围 [log(N + 1)，logN + 1]，所以时间复杂度是 logN
代码(小堆为例)
//交换
void Swap(HPDataTypde* p1, HPDataTypde* p2)
{
HPDataTypde tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整:前提左右子树都是大小堆
void AdjustDown(HPDataTypde* a, int n, int root)
{
int parent = root;
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;
}
}
}接收的参数分别是：数组、数组元素个数、从哪个节点开始调整
1，默认是左孩子，如果右孩子小于左孩子，child的下标取右孩子下标，即 child ++
孩子超出数组的范围就不存在 child < n 继续2，需要注意的是在进行左右孩子比较的时候如果到了数组末尾只剩一个左孩子，而没有右孩子，为了防止越界，则需要加入判断 child + 1 < n
3，如果孩子小于父亲，就交换(交换完后并没有结束)4，沿着某条路径不断迭代往下走，所有需要改变孩子和父亲的下标，当孩子大于等于父亲的时候，直接跳出循环，不需在进行交换(可以根据向下调整的示例图配合代码去理解)
堆的实现
完整代码
Heap.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
//实现小堆
typedef int HPDataTypde;
typedef struct Heap
{
HPDataTypde* _a;
int _size;
int _capacity;
}Heap;
//向下调整
void AdjustDown(HPDataTypde* a, int n, int root);
//初始化
void HeapInit(Heap* php, HPDataTypde* a, int n);
//向上调整
void AdjustUp(HPDataTypde* a, int n, int child);
//插入数据
void HeapPush(Heap* php, HPDataTypde x);
//删除堆顶的数据
void HeapPop(Heap* php);
//返回堆顶的值
HPDataTypde HeapTop(Heap* php);
//打印
void HeapPrint(Heap* php);
//销毁堆
void HeapDestory(Heap* php);Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
//交换
void Swap(HPDataTypde* p1, HPDataTypde* p2)
{
HPDataTypde tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整:前提左右子树都是大小堆
void AdjustDown(HPDataTypde* a, int n, int root)
{
int parent = root;
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 HeapInit(Heap* php, HPDataTypde* a, int n)
{
php->_a = (HPDataTypde*)malloc(sizeof(HPDataTypde) * n);
if (php->_a == NULL)
{
return;
}
memcpy(php->_a, a, sizeof(HPDataTypde) * n);
php->_capacity = n;
php->_size = n;
//构建堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(php->_a, php->_size, i);
}
}
//向上调整
void AdjustUp(HPDataTypde* a, int n, 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* php, HPDataTypde x)
{
assert(php);
if (php->_size == php->_capacity)
{
php->_capacity *= 2;
HPDataTypde* tmp = (HPDataTypde*)realloc(php->_a, sizeof(HPDataTypde) * php->_capacity);
if (tmp != NULL)
{
php->_a = tmp;
}
}
php->_a[php->_size++] = x;
AdjustUp(php->_a, php->_size, php->_size - 1);
}
//删除堆顶的数据
void HeapPop(Heap* php)
{
assert(php);
assert(php->_size > 0);
Swap(&php->_a[0], &php->_a[php->_size - 1]);
php->_size--;
AdjustDown(php->_a, php->_size, 0);
}
//返回堆顶的值
HPDataTypde HeapTop(Heap* php)
{
assert(php);
return php->_a[0];
}
//打印
void HeapPrint(Heap* php)
{
assert(php);
int i = 0;
for (i = 0; i < php->_size; i++)
{
printf("%d ", php->_a[i]);
}
printf("\n");
}
//销毁堆
void HeapDestory(Heap* php)
{
assert(php);
free(php->_a);
php->_a = NULL;
php->_capacity = php->_size = 0;
}Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
int main()
{
int a[] = { 27,15,19,18,28,34,65,49,25,37 };
Heap hp;
HeapInit(&hp, a, sizeof(a) / sizeof(a[0]));
HeapPrint(&hp);
HeapPush(&hp, 3);
HeapPrint(&hp);
//删除
HeapPop(&hp);
HeapPop(&hp);
HeapPop(&hp);
HeapPrint(&hp);
HeapDestory(&hp);
return 0;
}
堆的初始化(实现小堆为例)
Heap.h
//向下调整
void AdjustDown(HPDataTypde* a, int n, int root);
//初始化
void HeapInit(Heap* php, HPDataTypde* a, int n);Heap.c
//交换
void Swap(HPDataTypde* p1, HPDataTypde* p2)
{
HPDataTypde tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整:前提左右子树都是大小堆
void AdjustDown(HPDataTypde* a, int n, int root)
{
int parent = root;
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 HeapInit(Heap* php, HPDataTypde* a, int n)
{
php->_a = (HPDataTypde*)malloc(sizeof(HPDataTypde) * n);
if (php->_a == NULL)
{
return;
}
memcpy(php->_a, a, sizeof(HPDataTypde) * n);
php->_capacity = n;
php->_size = n;
//构建堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(php->_a, php->_size, i);
}
}1，前提：向下调整算法
我们知道了向下调整算法的实现，初始化堆就很容易了2，初始化的个数和容量都是数组的大小，因为堆开始就有数据，有容量
3，堆要么初始化成大堆，要么初始化成小堆，但是左右子树又不是大堆或者小堆，如果构建堆
思路：
构建小堆为例
我们可以从下往上调整，当我们调整好了最底层，就满足左右子树都是小堆，就可以使用向下调整，调整上一层(倒数第二层)，依次类推，直达根节点
但是叶子节点调整和没有调整都是一样的，所有我们代码可以优化一下，直接先从最后一个叶子结点的父亲开始向下调整假设有n个节点，最后一个结点的下标是 n-1，
根据重要结论，父亲下标 = (孩子 - 1) / 2 即 父亲下标 = (n-1 -1) / 2
如图所示：构建堆的过程路自己多画画
插入数据
Heap.h
//向上调整
void AdjustUp(HPDataTypde* a, int n, int child);
//插入数据
void HeapPush(Heap* php, HPDataTypde x);Heap.c
//向上调整
void AdjustUp(HPDataTypde* a, int n, 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* php, HPDataTypde x)
{
assert(php);
if (php->_size == php->_capacity)
{
php->_capacity *= 2;
HPDataTypde* tmp = (HPDataTypde*)realloc(php->_a, sizeof(HPDataTypde) * php->_capacity);
if (tmp != NULL)
{
php->_a = tmp;
}
}
php->_a[php->_size++] = x;
AdjustUp(php->_a, php->_size, php->_size - 1);
}插入数据不管是在顺序表，链表，堆，第一步都是先判断容量是否充足，如果不足则需要增容
其实可以使用向下调整，但是需要多传一个参数(数组的大小)，这样的话时间复杂度就比向上调整的时间复杂度更高，所有我们使用向上调整
1，增容
2，向上调整
向上调整算法的实现
删除堆顶的数据
Heap.h
//删除堆顶的数据
void HeapPop(Heap* php);Heap.c
//删除堆顶的数据
void HeapPop(Heap* php)
{
assert(php);
assert(php->_size > 0);
Swap(&php->_a[0], &php->_a[php->_size - 1]);
php->_size--;
AdjustDown(php->_a, php->_size, 0);
}我们如何删除堆顶的值呢，如果直接删掉头，再把后面的数据往前面挪，那么堆的结构重新调整就全部乱了，而且会带来大量的消耗(因为挪动大量的数据)
思路：
1，先交换
2，交换完成之后删除尾上的数据
3，向下调整堆
堆排序的实现
有了向下调整算法，实现堆排序就很轻松了
建小堆：排降序
建大堆：排升序
我们以建小堆为类(排降序)
思路：
1，先构建出小根堆
2，交换根的数据和最后一个结点的数据，然后让末尾的下标往前走一位(最后一位不算做堆里面的)，再进行向下调整。重复这个操作
假设有N的节点的数据，小根堆堆顶的数据一定是最小的，把最小的排末尾去，末尾的位置已经确定是最小的，然后在缩小区间范围，交换找次小的，调整缩小区间范围，不断重复
代码实现
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整:前提左右子树都是大小堆
void AdjustDown(int* a, int n, int root)
{
int parent = root;
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 HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
//再选次小的
AdjustDown(a, end, 0);
--end;
}
}
void HeapPrint(int* a, int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
}
int main()
{
int a[] = { 37 ,18,27,19,28,34,65,49,25,15 };
HeapSort(a, sizeof(a) / sizeof(a[0]));
HeapPrint(a, sizeof(a) / sizeof(a[0]));
return 0;
}建堆时间复杂度的计算
我们以满二叉树为例，向下调整的时间复杂度是 O(logN)，循环N / 2 次 ，时间复杂度是
(N / 2)*logN =O( N*logN) 吗，这是错误的，建堆的时间复杂度是 O(N)
如果AdjustDown(a, n, 0); 都是从根开始调整，那么时间复杂复就是 N*logN,
但是建堆每次都不是从根开始调整，假设满二叉树每个结点都需要调整，从n-1开始调整，这样方便计算时间复杂度
第一层 有 2^0 个节点需要调整 h次(树的高度次)
第二层 有 2^1个节点需要调整 h-1次(树的高度-1)
...
第h层有 2^(h-1)个节点，需要调整 2^(h-1)* 1
把循环的次数都加起来，就得到了时间复杂度
这里我们需要使用错位相减法，求时间复杂度
堆排序的时间复杂度是 O(N * log N)
建堆的时间复杂度 O(N)
调整的时间复杂度是 O(N* logN)
堆排序的时间复杂度是： O(N) + O(N* logN) =O(N*logN)
TopK问题
最小的K个数
思路：这个题目就是典型的 TopK问题，我们需要找到最小的前K个数，找小反而是建立大堆
建立好了K个数的大堆，我们拿堆顶的数据剩余的数据进行一一比较，如果比堆顶的 数据小，替换堆顶，然后向下调整，不断重复这种操作
其实我们可以换个例子，所有人的数据都有的情况下，相对于在全国找最穷的10个人，先随便把10个人排降序也就是建立大堆，然后用这个10个人中最富的去和剩下的所有人比较，只要比10个人中最富的还穷就进去堆，再次调整，还是10个人中最富的在堆顶，继续这个操作，最后比较完的结果就是最穷的10个人
代码
//调整为大堆
void AdjustDown(int* a,int n,int root)
{
int parent = root;
int child = parent *2 + 1;
while(child<n)
{
if(child+1 < n && a[child+1] >a[child])
{
++child;
}
if(a[child]>a[parent])
{
int temp = a[child];
a[child] = a[parent];
a[parent] = temp;
parent = child;
child = parent *2+1;
}
else
{
break;
}
}
}
int* smallestK(int* arr, int arrSize, int k, int* returnSize){
if(k==0)
{
return NULL;
}
int* retArr = (int*)malloc(sizeof(int)*k);
if(retArr == NULL)
{
return NULL;
}
for(int i = 0; i<k; i++)
{
retArr[i] = arr[i];
}
//建立大堆
for(int i = (k-1-1)/2; i>=0; --i)
{
AdjustDown(retArr,k,i);
}
//和堆顶进行比较
for(int j = k; j<arrSize; j++)
{
if(retArr[0]>arr[j])
{
retArr[0] = arr[j];
AdjustDown(retArr,k,0);
}
}
*returnSize = k;
return retArr;
}二叉树链式结构及实现
我们学习的二叉树不可能全是完全二叉树或者满二叉树，所以就得用链式结构来存储
二叉树的遍历结构
前序、中序、后序也叫深度优先遍历，而层序遍历也叫广度优先遍历
NULL可以看做是该子树的结束条件
前序遍历(先根遍历)
中序遍历(中根遍历)
后序遍历(后根遍历)
代码实现
我们先创建树的结构体，然后构建伪树
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
//前序遍历
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->_data);
PrevOrder(root->_left);
PrevOrder(root->_right);
}
//中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->_left);
printf("%c ", root->_data);
InOrder(root->_right);
}
//后序遍历
void postOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
postOrder(root->_left);
postOrder(root->_right);
printf("%c ", root->_data);
}
BTNode* CreateNode(int x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
return NULL;
}
node->_data = x;
node->_left = NULL;
node->_right = NULL;
return node;
}
int main()
{
//构建伪树
BTNode* A = CreateNode('A');
BTNode* B = CreateNode('B');
BTNode* C = CreateNode('C');
BTNode* D = CreateNode('D');
BTNode* E = CreateNode('E');
A->_left = B;
A->_right = C;
B->_left = D;
B->_right = E;
PrevOrder(A);
printf("\n");
InOrder(A);
printf("\n");
postOrder(A);
printf("\n");
return 0;
}
打印结果：
A B D NULL NULL E NULL NULL C NULL NULL
NULL D NULL B NULL E NULL A NULL C NULL
NULL NULL D NULL NULL E B NULL NULL C A
我们以前序遍历为例(中序、后序可以多画图去理解)
层序遍历
层序遍历和前、中、后序的关系不大，利用队列实现
前面我们学习了队列，写层序之前得先有一个队列的实现
思路：
1，根先进队列
2，迭代->队列不为空，出队头的数据，同时把出的结点的左右孩子带进去
3，直到队列为空
层序遍历
层序遍历的思路图解
代码实现
我们在使用队列的时候，队列里面存储的时候结点的指针，
如果存储数据入队，出队数据，数据就找不到它孩子了，所以我们存储它的指针，通过指针来访问数据还有它的孩子
注意：
如果想要队列里存储指针需要改变一个地方
Queue.h文件中 typedef struct BinaryTreeNode* QDataType;
但是这种情况下：BinaryTreeNode结构体在Test.c文件中，而Queue.h文件需要使用这个结构体，无法找到，就会报错
解决方法：
1，把这个结构体写到Queue.h文件中，但是我们只是用一下队列，这样感觉好怪，不过这种方式也可以
2，在定义(typedef struct BinaryTreeNode* QDataType)
之前声明一下extern struct BinaryTreeNode;
处理完这些，我们就可以实现层序遍历了
Queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
extern struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
struct QueueNode* _next;
QDataType _data;
}QueueNode;
typedef struct Queue
{
QueueNode* _head;
QueueNode* _tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
//1??0??
int QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->_head = pq->_tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->_head;
while (cur)
{
QueueNode* next = cur->_next;
free(cur);
cur = next;
}
pq->_head = pq->_tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
printf("内存不足\n");
exit(-1);
}
newnode->_data = x;
newnode->_next = NULL;
if (pq->_head == NULL)
{
pq->_head = pq->_tail = newnode;
}
else
{
pq->_tail->_next = newnode;
pq->_tail = newnode;
}
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->_head);
QueueNode* next = pq->_head->_next;
free(pq->_head);
pq->_head = next;
if (pq->_head == NULL)
{
pq->_tail = NULL;
}
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->_head);
return pq->_head->_data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->_tail);
return pq->_tail->_data;
}
//返回1是空，返回0是非空
int QueueEmpty(Queue* pq)
{
assert(pq);
return pq->_head == NULL ? 1 : 0;
}
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->_head;
int size = 0;
while (cur)
{
++size;
cur = cur->_next;
}
return size;
}
Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
BTNode* CreateNode(int x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
return NULL;
}
node->_data = x;
node->_left = NULL;
node->_right = NULL;
return node;
}
//层序遍历
void LevelOrderTraversal(BTNode* root)
{
//初始化队列
Queue q;
QueueInit(&q);
if (root == NULL)
return;
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c ", front->_data);
if (front->_left)
{
QueuePush(&q, front->_left);
}
if (front->_right)
{
QueuePush(&q, front->_right);
}
}
QueueDestory(&q);
printf("\n");
}
//判断一棵树是否是完全二叉树
//bool BinaryTreeComplete(BTNode* root)
//{
// Queue q;
// QueueInit(&q);
// if (root == NULL)
// return true;
// QueuePush(&q, root);
// 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;
// }
// }
// QueueDestory(&q);
// return true;
//}
int main()
{
//构建伪树
BTNode* A = CreateNode('A');
BTNode* B = CreateNode('B');
BTNode* C = CreateNode('C');
BTNode* D = CreateNode('D');
BTNode* E = CreateNode('E');
A->_left = B;
A->_right = C;
B->_left = D;
B->_right = E;
LevelOrderTraversal(A);
/*printf("%d\n", BinaryTreeComplete(A));*/
return 0;
}二叉树的相关例题(leetCode)
单值二叉树
解题思路：根据题意我们可知，单值二叉树就是这颗树的所有节点的值都是相同的，我们称为单值二叉树。
1，判断是否为空树，如果是空树返回 true
2，在左子树和右子树不为空的情况下，判断左子树和右子树的值与根的值是否相等 ，如果不相等返回false
3，使用前序遍历结构，因为如果根都不满足，遍历左子树或者右子树没有意义
代码
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);
}二叉树的最大深度
求二叉树的结点个数
int countNodes(struct TreeNode* root) {
if(root == NULL)
return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}思路：
我们在了解求二叉树的节点个数的时候，由此可以受到启发，求最大深度也是一个原理
如果二叉树为NULL树，就返回 0，只不过多了一步比较左右子树哪个大，取较大的值
如果存在一个结点，返回 1 (子树出发，返回0结束，所以要加1）
如果存在多个结点，不断递归(如果实在不能理解，可以多画画图，慢慢就会理解了)
代码：
int maxDepth(struct TreeNode * root)
{
if (root == NULL)
return 0;
int LeftDepth = maxDepth(root->left);
int RightDepth = maxDepth(root->right);
return LeftDepth > RightDepth ? LeftDepth
+ 1 : RightDepth + 1;
}注意：
如果按以下这种写法就会超出时间限制，maxDepth(root->left)和maxDepth(root->right)从根节点开始递归走到叶子，然后maxDepth(root->left)和maxDepth(root->right)又从根节点开始从新递归，存在重复递归，所以我们就把每次递归的值先保存然后再比较
int maxDepth(struct TreeNode * root)
{
if (root == NULL)
return 0;
return maxDepth(root->left) > maxDepth(root->right)? maxDepth(root->left)+1:maxDepth(root->right)+1;
}翻转二叉树
方法一
思路：
我们采取方法类似于前序遍历，根、左子树、右子树
先处理左树和右树，是左子树和右子树整体交换位置，然后递归下去不断这种操作就可以不断完成交换，直达NULL返回，最后返回 root
如图所示：
代码
struct TreeNode* mirrorTree(struct TreeNode* root){
if(root==NULL)
return NULL;
struct TreeNode* right = root->right;
root->right = root->left;
root->left = right;
mirrorTree(root->left);
mirrorTree(root->right);
return root;
}
方法二
思路：这种方式采用的是后序遍历，递出去到达叶子，然后交换叶子再依次往根的方向走
理解有点绕，可以画图理解
代码
struct TreeNode* invertTree(struct TreeNode* root) {
if(root==NULL)
return NULL;
struct TreeNode* right = root->right;
root->right = invertTree(root->left);
root->left = invertTree(right);
return root;
}相同的树
思路：
结构的比较：
1，首先判断两棵树树是否都为NULL树，如果都是NULL树，返回 true
2,如果一棵树为NULL，另外一棵不为NULL,返回 false
值的比较：
3，如果两棵树都不为空树，值不相同就返回 false
4，递归 p 树的左子树和q树的左子树，递归p树的右子树和p树的右子树
如图：
代码
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);
}对称二叉树
思路：我们在会相同的树的基础上，做这个对称二叉树就是分分钟拿捏了。
如果我们去掉根节点，我们会发现它的两颗子树就是一个相同的树求解的方法，在这里虽然是二叉树的镜像(二叉树的翻转)，但是我们利用相同的二叉树的求解就可以，把左子树的左孩子和右子树的右孩子比较 &&左子树的右孩子和右子树的左孩子比较(认真理解这句话就是关键)，如果相同就返回true，不断递出去，不断进行比较，只要存在一个false就返回false
如图所示：
代码：
bool isSameTree(struct TreeNode*s,struct TreeNode*t)
{
if(s==NULL&&t==NULL)
return true;
if(s==NULL || t==NULL)
return false;
if(s->val !=t->val)
return false;
return isSameTree(s->left,t->right)&&isSameTree(s->right,t->left);
}
bool checkSymmetricTree(struct TreeNode* root) {
if(root==NULL)
return true;
return isSameTree(root->left,root->right);
}另一棵树的子树
思路：
我们在以相同的两棵树为基础，解决此问题就很容易入手
root 和 subRoot 两棵树 ，判断 root 是否是 subRoot 的子树
1，如果root为空，直接返回 false
2,我们可以先和根节点比较只是否相同，不相同还得继续比较子树的值和结构
3，我们可以依次递下去进行比较，比较是否存在相同的两棵树，只有有一个不满足就直接返回 false
4，在 root 树中，无论是左树满足还是右树满足，只要有一边满足就返回 true，而不需要左树和右数同时成立
代码：
bool isSametree(struct TreeNode* root, struct TreeNode* subRoot)
{
if (root == NULL && subRoot == NULL)
return true;
if (root == NULL || subRoot == NULL)
return false;
if (root->val != subRoot->val)
return false;
return isSametree(root->left, subRoot->left) && isSametree(root->right, subRoot->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);
}判断一颗二叉树是否是平衡二叉树。
思路：此题必须掌握，这个题目的和另外一个树的子树思路类似
1，如果树是空树，返回 true
2，我们要求子树的深度，一层一层比较，只要子树的深度有一个超过了 1 就不满足，直接返回 false
代码
int DepthTree(struct TreeNode* root)
{
if(root == NULL)
return 0;
int left = DepthTree(root->left);
int right = DepthTree(root->right);
return left > right ? left +1 : right + 1;
}
bool isBalanced(struct TreeNode* root) {
if(root == NULL)
return true;
int gap = DepthTree(root->left) - DepthTree(root->right);
if(abs(gap) > 1)
return false;
return isBalanced(root->left)&& isBalanced(root->right);
}此时的时间复杂度是多少？？？
深度的计算(遍历整棵树)时间复杂度是O(N),当在根节点进行一次就满足最优的情况下是O(N),最坏的情况下是 O(N*N)，所以时间复杂度是 O(N*N),
那么此段代码如何优化成O(N)???
思路：我们可以采用后序遍历的方法，从后叶子结点开始计算深度，只要子树的深度不满足 就直接返回 false，如果一个子树满足，还需要判断所有的子树，最后到达根节点
代码
bool _isBalanced(struct TreeNode* root, int* depth) {
if (root == NULL) {
*depth = 0;
return true;
}
int leftDepth = 0;
if (_isBalanced(root->left, &leftDepth) == false)
return false;
int rightDepth = 0;
if (_isBalanced(root->right, &rightDepth)==false)
return false;
if (abs(leftDepth - rightDepth) > 1)
return false;
*depth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
return true;
}
bool isBalanced(struct TreeNode* root) {
int depth = 0;
return _isBalanced(root, &depth);
}二叉树的构建及遍历
题目描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述:
输入包括1行字符串，长度不超过100。
输出描述:
可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。
示例1
输入
abc##de#g##f###
输出
c b e g d f a***：#是表示叶节点的。这道题是按照输入先序生成的字符串，因此使用先序的递归调用，建立二叉树。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode
{
char val;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
TreeNode* CreateNode(char* str, int* pi)
{
if (str[*pi] == '#')
{
++(*pi);
return NULL;
}
else
{
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
if (root == NULL)
{
return NULL;
}
root->val = str[*pi];
++(*pi);
root->left = CreateNode(str, pi);
root->right = CreateNode(str, pi);
return root;
}
}
void InOrder(TreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->val);
InOrder(root->right);
}
int main()
{
char str[100];
printf("cin:>");
scanf("%s", str);
int pi = 0;
TreeNode* root = CreateNode(str, &pi);
InOrder(root);
return 0;
}