数据结构:4_二叉树
二叉树
一.树概念及结构
1. 树的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
-
有一个**特殊的结点，称为根结点，**根节点没有前驱结点
-
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
-
因此，树是递归定义的。
-
注意：树形结构中，子树之间不能有交集，否则就不是树形结构
2. 树的相关概念
- 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
- 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
- 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
- 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
- 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
- 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
- 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
- 森林：由m（m>0）棵互不相交的树的集合称为森林；
3. 树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};
- 改方法是最优方法
- 初次之外还有两种方法表示树
4. 树在实际中的运用（表示文件系统的目录树结构）
二.二叉树概念及结构
1. 概念
-
一棵二叉树是结点的一个有限集合，该集合:
- (1). 或者为空
- (2). 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
-
从上图可以看出：
- (1). 二叉树不存在度大于2的结点
- (2). 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
-
注意：对于任意的二叉树都是由以下几种情况复合而成的：
2. 特殊的二叉树：
(1). 满二叉树：
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2k-1 ，则它就是满二叉树。
(2). 完全二叉树：
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。(即:前h-1层是满的，最后一层不一定满，但是从左到右必须连续)
3. 二叉树的性质
- (1). 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2(i-1)个结点.
- (2). 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2h - 1.
- (3). 对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有n0＝n2＋1
- (4). 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1). (ps：log2(n+1)是log以2为底，n+1为对数)
- (5). 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从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否则无右孩子
1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199
2.下列数据结构中，不适合采用顺序存储结构的是（ ）
A 非完全二叉树
B 堆
C 队列
D 栈
3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2
4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12
5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386
答案：
1.B
2.A
3.A
4.B
5.B
4.二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
(1).顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
(2).链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面学到高阶数据结构如红黑树等会用到三叉链。
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向当前节点的双亲struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}；
三.二叉树的顺序结构及实现
1. 二叉树的顺序结构
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
2. 堆的概念及结构
如果有一个关键码的集合K = {k0，k1，k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2*i+1且 Ki <= K2*i+2( Ki >= K2*i+1且Ki >= K2*i+2 ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
-
堆的性质:
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
-
注意: 数据结构中的堆和C语言中的堆不一样
-
堆 – 数据结构 ~~~~~~~~~~ 完全二叉树
-
堆 – c语言/操作系统 ~~ 内存区域的划分
-
不同学科里面的同名名称
1.下列关键字序列为堆的是：（）
A 100,60,70,50,32,65
B 60,70,65,50,32,100
C 65,100,70,32,50,60
D 70,65,100,32,50,60
E 32,50,100,70,65,60
F 50,100,70,65,60,32
2.已知小根堆为8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次
数是（）。
A 1
B 2
C 3
D 4
3.一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为
A(11 5 7 2 3 17)
B(11 5 7 2 17 3)
C(17 11 7 2 3 5)
D(17 11 7 5 3 2)
E(17 7 11 3 5 2)
F(17 7 11 3 2 5)
4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是（）
A[3，2，5，7，4，6，8]
B[2，3，5，7，4，6，8]
C[2，3，4，5，7，8，6]
D[2，3，4，5，6，7，8]1.A
2.C
3.C
4.C
3. 堆的实现
(1).堆向下调整算法 前提：左右子树必须是一个堆
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
int array[] = {27,15,19,18,28,34,65,49,25,37};
(2).堆的创建 将以有数组直接变成堆
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
- 注意:一般建堆使用法2,其有两点优势:①时间复杂度小O(N)②只用写一个AdjustDown函数(堆排序后面一定要用)
(3).建堆时间复杂度
①向下调整建堆时间复杂度
- 因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
②向上调整建堆时间复杂度
(4).堆的插入 向上调整的前提是前面的树构成堆
先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。
(5).堆的删除
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
(6).堆的代码实现
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
//堆的实现
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//小堆
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = 0;php->size = 0;
}void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 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 (a[parent] > a[child])
// {
// Swap(&a[parent], &a[child]);
// child = parent;
// parent = (child - 1) / 2;
// }
//}
//写法二
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//while (parent >= 0)while (child > 0){if (a[child] < a[parent])//大小堆改此处:a[child] > a[parent]{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//O(logN)
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}void AdjustDown(HPDataType* a,int size,int parent)
{int child = parent * 2 + 1;while (child<size){//假设左孩子小,如果假设错了,更新一下if (child + 1 < size && a[child + 1] < a[child])//大小堆改此处:a[child + 1] > a[child]{++child;}if (a[child] < a[parent])//大小堆改此处:a[child] > a[parent]{Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(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);
}HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}int HeapSize(HP* php)
{assert(php);return php->size;
}bool HeapEmpty(HP* php)
{return php->size == 0;
}
4. 堆的应用
(1).堆排序–本质是一种选择排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
-
- 建堆
- 升序：建大堆
- 降序：建小堆
-
- 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
- 利用堆删除思想来进行排序
(2). TOP-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
-
- 用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆
- 前k个最小的元素，则建大堆
-
- 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
- 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
void PrintTopK(int* a, int n, int k)
{// 1. 建堆--用a中前k个元素建堆// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
}
void CreateNDate()
{//造数据int n = 10000000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen fail");return;}for (int i = 0; i < n; i++){int x = (rand()+i) % n;fprintf(fin, "%d\n", x);}fclose(fin);
}
//Topk问题
void PrintTopK(const char* file, int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail");return;}//建堆int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc fail");return;}//读取前k个数据,建小堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);//%d后不用写/nAdjustUp(minheap, i);}int x = 0;while (fscanf(fout, "%d", &x)!=EOF)//%d后不用写/n{if (x > minheap[0]){minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}free(minheap);fclose(fout);
}
int main()
{//CreateNDate();PrintTopK("data.txt", 5);return 0;
}
四.二叉树链式结构的实现
1. 前置说明
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
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;
}
-
注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。
-
再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：
- 1 . 空树
- 2 . 非空：根节点，根节点的左子树、根节点的右子树组成的。
-
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
2. 二叉树的遍历
(1).前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
- 按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
- 1.前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。[根 左子树 右子树]
- 2.中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。[左子树 根 右子树]
- 3.后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。[左子树 右子树 根]
也叫做先根,中根,后根遍历
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。 NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
// 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);
//前序访问
void PrevOrder(TreeNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(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);
}
下面主要分析前序递归遍历，中序与后序图解类似，同学们可自己动手绘制。
前序遍历递归图解：
(2).层序遍历
void LevelOrder(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;while (!QueueEmpty(&q)){//levelSize是每一层的数据个数，控制一层一层出// 一层一层出while (levelSize--){TreeNode* front = QueueFront(&q);QueuePop(&q);printf("%c ", front->data);//根据BTDataType选择打印格式if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}printf("\n");levelSize = QueueSize(&q);}printf("\n");QueueDestroy(&q);
}
3. 节点个数以及高度等
- 注意:递归:
- 1.子问题分治
- 2.返回条件
// 1.二叉树节点个数
int TreeSize(TreeNode* root)
{return root == NULL ? 0 : 1 + TreeSize(root->left) + TreeSize(root->right);
}// 2.二叉树叶子节点个数
int TreeLeafSize(TreeNode* root)
{//空 返回0if (root == NULL)return 0;//不是空,是叶子 返回1if (root->left==NULL && root->right==NULL)return 1;//不是空 也不是叶子 分治=左右子树叶子之和 return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}// 补充:树的高度
//法一
int TreeHeight(TreeNode* root)
{if (root == NULL)return 0;int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
//法二
int TreeHeight(TreeNode* root)
{if (root == NULL)return 0;return fmax(TreeHeight(root->left), TreeHeight(root->right))+1;
}// 3.二叉树第k层节点个数
int TreeLevelK(TreeNode* root, int k)
{assert(k > 0);if (root == NULL){return 0;}if (k == 1){return 1;}else{return TreeLevelK(root->left, k - 1) + TreeLevelK(root->right, k - 1);}
}// 4.二叉树查找值为x的节点
TreeNode* TreeFind(TreeNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;TreeNode* left = TreeFind(root->left, x);if (left != NULL)return left;TreeNode* right = TreeFind(root->right, x);if (right != NULL)return right;return NULL;
}4. 二叉树基础oj练习
1. 单值二叉树
https://leetcode.cn/problems/univalued-binary-tree/
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
bool isUnivalTree(struct TreeNode* root) {if(root==NULL)return true;if(root->left!=NULL&&root->left->val!=root->val)return false;if(root->right!=NULL&&root->right->val!=root->val)return false;return isUnivalTree(root->left)&&isUnivalTree(root->right);
}
2. 相同的树
https://leetcode.cn/problems/same-tree/submissions/
/*** 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==q)return true;//一个为空一个不为空if((p==NULL&&q!=NULL)||(p!=NULL&&q==NULL))//或者直接写(p=NULL||q==NULL)return false;//都不为空if(p->val!=q->val)return false;return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
3. 对称二叉树
https://leetcode.cn/problems/symmetric-tree/
//法一:利用相同二叉树代码
/*** 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==q)return true;//一个为空一个不为空if((p==NULL&&q!=NULL)||(p!=NULL&&q==NULL))//或者直接写(p=NULL||q==NULL)return false;//都不为空if(p->val!=q->val)return false;return isSameTree(p->left,q->right)&&isSameTree(p->right,q->left);
}bool isSymmetric(struct TreeNode* root) {if(root==NULL)return true;return isSameTree(root->left,root->right);
}
//法二:新建子函数
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2) {if(root1==root2)return true;if(root1==NULL||root2==NULL)return false;if(root1->val!=root2->val)return false;return _isSymmetric(root1->left,root2->right)&&_isSymmetric(root1->right,root2->left);
}bool isSymmetric(struct TreeNode* root) {return _isSymmetric(root->left,root->right);
}
4. 二叉树的前序遍历
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 i = 0;int TreeSize(struct TreeNode* root) {return root == NULL ? 0 : 1 + TreeSize(root->left) + TreeSize(root->right);
}void preorder(struct TreeNode* root, int* a) {if (root == NULL)return;a[i++] = root->val;preorder(root->left, a);preorder(root->right, a);
}// 输出型参数 (leetcode如果函数返回值是数组，不知道数组的大小。需要int* returnSize这样的输出型参数返回数组大小。)
int* preorderTraversal(struct TreeNode* root, int* returnSize) {int n = TreeSize(root);int* a = (int*)malloc(sizeof(int) * n);*returnSize = n;i = 0;preorder(root, a);return a;
}
//法二:局部变量
/*** 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 : 1 + TreeSize(root->left) + TreeSize(root->right);
}void preorder(struct TreeNode* root, int* a, int* pi) {if (root == NULL)return;a[(*pi)++] = root->val;preorder(root->left, a, pi);preorder(root->right, a, pi);
}// 输出型参数 (leetcode如果函数返回值是数组，不知道数组的大小。需要int*
// returnSize这样的输出型参数返回数组大小。)
int* preorderTraversal(struct TreeNode* root, int* returnSize) {int n = TreeSize(root);int* a = (int*)malloc(sizeof(int) * n);*returnSize = n;int i = 0;preorder(root, a,&i);return a;
}
5. 二叉树的中序遍历
https://leetcode.cn/problems/binary-tree-inorder-traversal/
/*** 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:1+TreeSize(root->left)+TreeSize(root->right);
}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) {int n=TreeSize(root);*returnSize=n;int* a=(int*)malloc(sizeof(int)*n);int i=0;inorder(root,a,&i);return a;
}
6. 二叉树的后序遍历
https://leetcode.cn/problems/binary-tree-postorder-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:1+TreeSize(root->left)+TreeSize(root->right);
}void postorder(struct TreeNode* root, int* a,int* pi)
{if(root==NULL)return;postorder(root->left,a,pi);postorder(root->right,a,pi);a[(*pi)++]=root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize) {int n=TreeSize(root); *returnSize=n;int* a=(int*)malloc(sizeof(int)*n);int i=0;postorder(root,a,&i);return a;
}
7. 另一棵树的子树
https://leetcode.cn/problems/subtree-of-another-tree/description/
/*** 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==q)return true;//一个为空一个不为空if((p==NULL&&q!=NULL)||(p!=NULL&&q==NULL))//或者直接写(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 isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(isSameTree(root,subRoot))return true;if(root==NULL)return false;return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
5. 二叉树的创建和销毁
二叉树的构建及遍历。
https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
TreeNode* TreeCreate(char* a, int* pi)
// 二叉树销毁
void DestoryTree(TreeNode* root)
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
// 1. 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
TreeNode* TreeCreate(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = a[(*pi)++];root->left = TreeCreate(a, pi);root->right = TreeCreate(a, pi);return root;
}
// 2. 二叉树销毁
void DestoryTree(TreeNode* root)//调用的人调用后自己把root置空
{if (root == NULL)return;DestoryTree(root->left);DestoryTree(root->right);free(root);return;
}
// 3. 是否是完全二叉树
bool TreeComplete(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}// 前面遇到空以后,后面还有非空就不是完全二叉树while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front!=NULL)return false;}QueueDestroy(&q);return true;
}
五.总结
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
#include<math.h>typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}TreeNode;// 1.前序访问
void PrevOrder(TreeNode* root);
// 2.中序访问
void InOrder(TreeNode* root);
// 3.后序访问
void PostOrder(TreeNode* root);
// 4.层序遍历
void LevelOrder(TreeNode* root);
// 5.二叉树销毁
void DestoryTree(TreeNode* root);
// 6.是否是完全二叉树
bool TreeComplete(TreeNode* root);// 1.节点个数
int TreeSize(TreeNode* root);
// 2.叶子节点的个数
int TreeLeafSize(TreeNode* root);
//补充:树的高度
int TreeHeight(TreeNode* root);
// 3.第k层结点个数
int TreeLevelK(TreeNode* root, int k);
// 4.查找值为x的结点
TreeNode* TreeFind(TreeNode* root, BTDataType x);// 通过前序遍历的数组构建二叉树
TreeNode* TreeCreate(BTDataType* a, int* pi);// 手撕二叉树
TreeNode* BuyTreeNode(int x);
TreeNode* CreateTree();
#include"BinaryTree.h"
#include"Queue.h"// 1.前序访问
void PrevOrder(TreeNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);//根据BTDataType选择打印格式PrevOrder(root->left);PrevOrder(root->right);
}
// 2.中序访问
void InOrder(TreeNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);//根据BTDataType选择打印格式InOrder(root->right);
}
// 3.后序访问
void PostOrder(TreeNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);//根据BTDataType选择打印格式
}// 4.层序遍历
void LevelOrder(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;while (!QueueEmpty(&q)){//levelSize是每一层的数据个数，控制一层一层出// 一层一层出while (levelSize--){TreeNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);//根据BTDataType选择打印格式if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}printf("\n");levelSize = QueueSize(&q);}printf("\n");QueueDestroy(&q);
}// 5.二叉树销毁
void DestoryTree(TreeNode* root)//调用的人调用后自己把root置空
{if (root == NULL)return;DestoryTree(root->left);DestoryTree(root->right);free(root);return;
}// 6.是否是完全二叉树
bool TreeComplete(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}// 前面遇到空以后,后面还有非空就不是完全二叉树while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front!=NULL)return false;}QueueDestroy(&q);return true;
}// 1.节点个数
int TreeSize(TreeNode* root)
{return root == NULL ? 0 : 1 + TreeSize(root->left) + TreeSize(root->right);
}// 2.叶子节点的个数
int TreeLeafSize(TreeNode* root)
{//空 返回0if (root == NULL)return 0;//不是空,是叶子 返回1if (root->left == NULL && root->right == NULL)return 1;//不是空 也不是叶子 分治=左右子树叶子之和 return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}//补充:树的高度
//法一
//int TreeHeight(TreeNode* root)
//{
// if (root == NULL)
// return 0;
// int leftHeight = TreeHeight(root->left);
// int rightHeight = TreeHeight(root->right);
// return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
//}
//法二
int TreeHeight(TreeNode* root)
{if (root == NULL)return 0;return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}// 3.第k层结点个数
int TreeLevelK(TreeNode* root, int k)
{assert(k > 0);if (root == NULL){return 0;}if (k == 1){return 1;}else{return TreeLevelK(root->left, k - 1) + TreeLevelK(root->right, k - 1);}
}// 4.查找值为x的结点
TreeNode* TreeFind(TreeNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;TreeNode* left = TreeFind(root->left, x);if (left != NULL)return left;TreeNode* right = TreeFind(root->right, x);if (right != NULL)return right;return NULL;
}// 通过前序遍历的数组构建二叉树
TreeNode* TreeCreate(BTDataType* a, int* pi)
{if (a[*pi] == -1)//a[*pi] == '#'{(*pi)++;return NULL;}TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = a[(*pi)++];root->left = TreeCreate(a, pi);root->right = TreeCreate(a, pi);return root;
}// 手撕二叉树
TreeNode* BuyTreeNode(int x)
{TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));assert(node);node->data = x;node->left = NULL;node->right = NULL;return node;
}TreeNode* CreateTree()
{TreeNode* node1 = BuyTreeNode(1);TreeNode* node2 = BuyTreeNode(2);TreeNode* node3 = BuyTreeNode(3);TreeNode* node4 = BuyTreeNode(4);TreeNode* node5 = BuyTreeNode(5);TreeNode* node6 = BuyTreeNode(6);TreeNode* node7 = BuyTreeNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node2->right = node7;return node1;
}
相关文章：
数据结构:4_二叉树
二叉树 一.树概念及结构 1. 树的概念 树是一种非线性的数据结构，它是由n（n>0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 有一个**特殊的…...
设计模式之：状态模式（State Pattern）
状态模式（State Pattern） 状态模式是一种行为设计模式，允许一个对象在其内部状态改变时改变它的行为。这种模式通过把状态的变化逻辑分布到State的子类之间，减少了相互间的依赖，使得状态的切换更加清晰。 状态模式的…...
【微服安全】API密钥和令牌与微服务安全的关系
什么是 API 密钥和令牌 API 密钥 API 密钥是一串用于识别应用程序或用户的字符串。它通常用于授权应用程序或用户访问 API。API 密钥可以是公开的，也可以是私有的。公开的 API 密钥可供任何人使用，而私有的 API 密钥只能由授权的应用程序或用户使用。 …...
Mock.js
在开发后端的应用中，我们使用postman来测试接口，观察和验证前后端之间的数据传递是否正常。 在开发前端的应用中，我们使用Mock.js来模拟后端服务，以便进行前端业务逻辑的开发和测试。 一般情况下，个人开发或者小团队开…...
【c++】list详细讲解
> 作者简介：დ旧言~，目前大二，现在学习Java，c，c，Python等 > 座右铭：松树千年终是朽，槿花一日自为荣。 > 目标：熟悉list库 > 毒鸡汤：你的脸上云淡…...
C#面：在.NET中 类 System.Web.UI.Page 可以被继承吗？
可以。 它是 ASP.NET WebForms中的一个重要类，用于表示 Web 页面。通过继承 System.Web.UI.Page 类，可以创建自定义的 Web 页面，并在其中添加自己的逻辑和功能。 继承 System.Web.UI.Page 类的好处是，可以重用和扩展已有的功能。…...
AI：128-基于机器学习的建筑物能源消耗预测
🚀点击这里跳转到本专栏，可查阅专栏顶置最新的指南宝典~ 🎉🎊🎉 你的技术旅程将在这里启航！ 从基础到实践，深入学习。无论你是初学者还是经验丰富的老手，对于本专栏案例和项目实践都有参考学习意义。 ✨✨✨ 每一个案例都附带有在本地跑过的关键代码，详细讲解供…...
php基础学习之可变函数（web渗透测试关键字绕过rce和回调函数）
可变函数 看可变函数的知识点之前，蒟蒻博主建议你先去看看php的可变变量，会更加方便理解，在本篇博客中的第五块知识点->php基础学习之变量-CSDN博客 描述 当一个变量所保存的值刚好是一个函数的名字（由函数命名规则可知该值必…...
MongoDB聚合操作符：$acos
$acos操作符返回一个值的反余弦。从MongoDB4.2版本开始支持。 语法 { $acos: <expression> }$acos接受任何可被解析为值在-1到1之间的表达式，即：-1 < value < 1$acos返回值以弧度为单位，使用$radiansToDegrees操作符可以把输出…...
开源PDF工具 Apache PDFBox 认识及使用(知识点+案例)
文章目录 前言源码获取一、认识PDFBox二、导入依赖三、基础功能demo1：读取pdf所有内容demo2：读取所有页内容（分页）demo3：添加页眉、页脚demo4：添加居中45文字水印demo5：添加图片到右上角 参考文…...
微软.NET6开发的C#特性——委托和事件
我是荔园微风，作为一名在IT界整整25年的老兵，看到不少初学者在学习编程语言的过程中如此的痛苦，我决定做点什么，下面我就重点讲讲微软.NET6开发人员需要知道的C#特性，然后比较其他各种语言进行认识。 C#经历了多年发展…...
卷积神经网络的基本结构
卷积神经网络的基本结构 与传统的全连接神经网络一样，卷积神经网络依然是一个层级网络，只不过层的功能和形式发生了变化。 典型的CNN结构包括： 数据输入层（Input Layer）卷积层（Convolutional Layer&#x…...
python：使用GDAL库读取遥感影像指定行列数/经纬度坐标的像素值
作者：CSDN @ _养乐多_ 本文将介绍如何使用GDAL库来读取单波段遥感影像数据，如何获取指定行列位置的像素的经纬度坐标，并根据像素行列数或者经纬度坐标获取像素值。代码由python实现。 文章目录 一、读取影像二、获取指定行列位置的像素坐标三、根据地理坐标获取像素值四、根…...
Redis篇----第一篇
系列文章目录 文章目录 系列文章目录前言一、什么是 Redis?二、Redis 与其他 key-value 存储有什么不同？三、Redis 的数据类型？四、使用 Redis 有哪些好处？五、Redis 相比 Memcached 有哪些优势？前言 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住…...
C语言-----用二维数组解决菱形的打印问题
1.打印菱形，多组输入，一个整数（2~20），表示输出的行数，也表示组成“X”的反斜线和正斜线的长度。 #include <stdio.h>int main() {int n0;while(scanf("%d",&n)! EOF){int i0;int j0;f…...
.NET Core WebAPI中使用swagger版本控制，添加注释
一、效果 二、实现步骤 在代码中添加注释 在项目属性中生成API文档 在Program中注册Swagger服务并配置文档信息 // 添加swagger注释 builder.Services.AddSwaggerGen(x > {x.SwaggerDoc("v1", new OpenApiInfo { Title "Swagger标题", Version "…...
css篇---移动端适配的方案有哪几种
移动端适配 移动端适配是指同一个页面可以在不同的移动端设备上都有合理的布局。主流实现的方案有 响应式布局通过rem或者vw,vh 等实现不同设备有相同的比例而实现适配 首先需要了解viewport 【视口】 视口代表了一个可看见的多边形区域（通常来说是矩形࿰…...
一、部署Oracle
部署Oracle 一、Docker部署1.Oracle11g1.1 测试环境1.1.1 拉取镜像1.1.2 启动容器1.1.3 配置容器环境变量1.1.4 修改sys、system用户密码1.1.5 创建表空间1.1.6 创建用户并授权1.1.5 使用DBeaver测试连接 二、安装包部署 一、Docker部署 1.Oracle11g 1.1 测试环境 当前只能用…...
11-编写自动化测试
上一篇： 10-通用类型、特质和生命周期 Edsger W. Dijkstra 在 1972 年发表的文章《The Humble Programmer》中说："程序测试可以非常有效地显示错误的存在，但对于显示错误的不存在却无能为力。这并不意味着我们不应该尽可能多地进行测试&…...
爱上JVM——常见问题（一）：JVM组成
1 JVM组成 1.1 JVM由那些部分组成，运行流程是什么？ 难易程度：☆☆☆ 出现频率：☆☆☆☆ JVM是什么 Java Virtual Machine Java程序的运行环境（java二进制字节码的运行环境） 好处： 一次编写&…...
React 第五十二节 Router中 useResolvedPath使用详解和注意事项示例
前言 useResolvedPath 是 React Router v6 提供的一个实用钩子，用于解析给定路径为完整路径对象。 它根据当前路由上下文解析相对路径，生成包含 pathname、search 和 hash 的完整路径对象。 一、useResolvedPath 核心用途 路径解析：将相对…...
云计算 Linux Rocky day03（which、快捷键、mount、家目录、ls、alias、mkdir、rm、mv、cp、grep）
云计算 Linux Rocky day03（which、快捷键、mount、家目录、ls、alias、mkdir、rm、mv、cp、grep） 目录 云计算 Linux Rocky day03（which、快捷键、mount、家目录、ls、alias、mkdir、rm、mv、cp、grep）1.which找到命令所对应的程序…...
mamba架构和transformer区别
Mamba 架构和 Transformer 架构存在多方面的区别，具体如下： 计算复杂度1 Transformer：自注意力机制的计算量会随着上下文长度的增加呈平方级增长，例如上下文增加 32 倍时，计算量可能增长 1000 倍，在处理长序…...
第1章_数据分析认知_知识点笔记
来自：数据分析自学课程-戴戴戴师兄 逐字稿：【课程4.0】第1章_分析认知_知识点笔记 【课程4.0】第1章 分析认知 知识点总结 数据分析的核心价值不是工具，而是用数据驱动业务增长。 一、数据分析的本质认知 数据分析是什么？ 不是酷…...
灵活控制，modbus tcp转ethernetip的 多功能水处理方案
油田自动化和先进的油气行业软件为油气公司带来了诸多益处。其中包括： 1.自动化可以消除多余的步骤、减少人为错误并降低运行设备所需的能量，从而降低成本。 2.油天然气行业不断追求高水平生产。自动化可以更轻松地减少计划外停机时间，从而…...
护网行动面试试题（1）
文章目录 1、描述外网打点的流程？2、举几个 FOFA 在外网打点过程中的使用小技巧？3、如何识别 CDN？4、判断出靶标的 CMS，对外网打点有什么意义？5、Apache Log4j2 的漏洞原理是什么？6、如何判断靶标站点是 wi…...
在MyBatis中设计SQL返回布尔值（Boolean）有几种常见方法
方案一：使用COUNT查询存在性（推荐） <select id"checkUserExists" resultType"_boolean">SELECT COUNT(*) > 0 FROM users WHERE username #{username} </select> 说明： MySQL中COU…...
电脑开不了机，主板显示67码解决过程
文章目录 现象分析内存条问题BIOS设置问题其它问题 解决清理内存条金手指所需工具操作步骤注意事项 电脑在运行过程中，显示内存不足，重启电脑却无法启动。 现象 System Initialization 主板风扇是转的，也有灯光显示，插上屏幕&am…...
Maven相关问题：jna版本与ES冲突 + aop失效
文章目录 1、背景2、解决3、一点思考4、环境升级导致AOP失效5、okhttp Bean找不到6、总结 记录一些Maven依赖相关的思考 1、背景 做一个监控指标收集，用一下jna依赖： <dependency><groupId>net.java.dev.jna</groupId><artifact…...
ServBay 1.13.0 更新，新增第三方反向代理/内网穿透
ServBay 作为一款简化本地开发环境搭建与管理的强大工具，致力于打造一个开箱即用、稳定可靠的本地开发平台，让用户专注于代码编写，提升开发效率。 ServBay 1.13.0 正式发布！本次更新聚焦于提升本地开发项目的外部可访问性、增强国…...