唐山网站制作专业,企业网站报价模板,wordpress 目录别名,wordpress源码学习二叉树
一.树概念及结构
1. 树的概念
树是一种非线性的数据结构#xff0c;它是由n#xff08;n0#xff09;个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树#xff0c;也就是说它是根朝上#xff0c;而叶朝下的。 有一个**特殊的…二叉树
一.树概念及结构
1. 树的概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 有一个**特殊的结点称为根结点**根节点没有前驱结点 除根节点外其余结点被分成M(M0)个互不相交的集合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的子孙森林由mm0棵互不相交的树的集合称为森林
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,则有n0n21(4). 若规定根节点的层数为1具有n个结点的满二叉树的深度hlog2(n1). (pslog2(n1)是log以2为底n1为对数)(5). 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 ①. 若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点②. 若2i1n左孩子序号2i12i1n否则无左孩子③. 若2i2n右孩子序号2i22i2n否则无右孩子
1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为
A 不存在这样的二叉树
B 200
C 198
D 199
2.下列数据结构中不适合采用顺序存储结构的是
A 非完全二叉树
B 堆
C 队列
D 栈
3.在具有 2n 个结点的完全二叉树中叶子结点个数为
A n
B n1
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.B4.二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。
(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 {k0k1k2…kn-1}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足Ki K2*i1且 Ki K2*i2( Ki K2*i1且Ki K2*i2 ) i 012…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 堆的性质: 堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。 注意: 数据结构中的堆和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[3257468]
B[2357468]
C[2345786]
D[2345678]1.A
2.C
3.C
4.C3. 堆的实现
(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 (childsize){//假设左孩子小,如果假设错了,更新一下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-leftNULL root-rightNULL)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(rootNULL)return true;if(root-left!NULLroot-left-val!root-val)return false;if(root-right!NULLroot-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(pq)return true;//一个为空一个不为空if((pNULLq!NULL)||(p!NULLqNULL))//或者直接写(pNULL||qNULL)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(pq)return true;//一个为空一个不为空if((pNULLq!NULL)||(p!NULLqNULL))//或者直接写(pNULL||qNULL)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(rootNULL)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(root1root2)return true;if(root1NULL||root2NULL)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 rootNULL?0:1TreeSize(root-left)TreeSize(root-right);
}void inorder(struct TreeNode* root,int* a,int* pi)
{if(rootNULL)return;inorder(root-left,a,pi); a[(*pi)]root-val;inorder(root-right,a,pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {int nTreeSize(root);*returnSizen;int* a(int*)malloc(sizeof(int)*n);int i0;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 rootNULL?0:1TreeSize(root-left)TreeSize(root-right);
}void postorder(struct TreeNode* root, int* a,int* pi)
{if(rootNULL)return;postorder(root-left,a,pi);postorder(root-right,a,pi);a[(*pi)]root-val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize) {int nTreeSize(root); *returnSizen;int* a(int*)malloc(sizeof(int)*n);int i0;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(pq)return true;//一个为空一个不为空if((pNULLq!NULL)||(p!NULLqNULL))//或者直接写(pNULL||qNULL)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(rootNULL)return false;return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);
}5. 二叉树的创建和销毁
二叉树的构建及遍历。 https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId60tqId29483rp1ru/activity/ojqru/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
#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.h
#includemath.htypedef 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();#includeBinaryTree.h
#includeQueue.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;
}
