C/C++数据结构与算法（第二弹）

目录栈和队列1.栈1.1栈的概念以及结构1.2栈的实现2.队列2.1队列的概念以及结构2.2队列的实现3.栈和队列OJ题1. 括号匹配问题。OJ链接2. 用队列实现栈。OJ链接3. 用栈实现队列。OJ链接4. 设计循环队列。OJ链接二叉树1.树概念以及结构1.1树的概念1.2树的相关概念1.3树的表示1.4树在实际中的运用表示文件系统的目录树结构2.二叉树概念以及结构2.1概念2.2特殊的二叉树1.满二叉树2.完全二叉树2.3二叉树的性质2.4二叉树的存储结构1.顺序结构2.链式存储3.二叉树的顺序结构以及实现3.1二叉树的顺序结构3.2堆的概念以及结构3.3堆的模拟实现3.3.1堆向下调整算法3.3.2堆的创建3.3.3建堆的时间复杂度3.3.4堆的插入3.3.5堆的删除3.2.6堆的代码模拟实现3.4堆的应用3.4.1堆排序4.Top-K问题1、用数据集合中前K个元素来建堆2、用剩余的N-K个元素依次与堆顶元素进行比较不满足则替换堆顶元素5.二叉树链式结构的实现5.1二叉树的遍历5.1.1前序、中序以及后序遍历5.2层序遍历5.3节点个数以及高度等1、二叉树的节点个数2、二叉树叶子节点个数3、二叉树第k层节点的个数5.4二叉树基础OJ题1. 单值二叉树。OJ链接2. 检查两颗树是否相同。OJ链接3. 对称二叉树。OJ链接4. 二叉树的前序遍历。OJ链接5. 二叉树中序遍历。OJ链接6. 二叉树的后序遍历。OJ链接7. 另一颗树的子树。OJ链接5.5二叉树的创建和销毁1、关于通过一个前序遍历的数组ABD##E#H##CF##G##构建二叉树的问题2、判断二叉树是否是完全二叉树栈和队列1.栈1.1栈的概念以及结构栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。1.2栈的实现栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。#pragma once #include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int STDataType; #define DEFAULT_CAPACITY 4 typedef struct Stack { STDataType* array; int top; int capacity; }Stack; //对栈进行初始化 void STInit(Stack* ps); //对栈结构进行释放 void STDestory(Stack* ps); //判断栈是否为空 bool STEmpty(Stack* ps); //拿到栈的大小 int STSize(Stack* ps); //入栈操作 void STPush(Stack* ps,STDataType x); //出栈操作 void STPop(Stack* ps); //访问栈顶元素 STDataType STTop(Stack* ps);#include Stack.h //对栈进行初始化 void STInit(Stack* ps) { assert(ps); //对栈进行初始化 ps-array (STDataType*)malloc( DEFAULT_CAPACITY* sizeof(STDataType)); if (NULL ps-array) { perror(malloc failed); return; } ps-capacity DEFAULT_CAPACITY; ps-top 0;//对栈顶初始化为0 } //对栈结构进行释放 void STDestory(Stack* ps) { assert(ps); free(ps-array); ps-array NULL; ps-capacity ps-top 0; } //判断栈是否为空 bool STEmpty(Stack* ps) { return ps-top 0; } //拿到栈的大小 int STSize(Stack* ps) { return ps-top; } //入栈操作 void STPush(Stack* ps, STDataType x) { assert(ps); if (ps-top ps-capacity) { //判断是否需要扩容---默认是扩容capacity的2倍 STDataType* tmp (STDataType*)realloc(ps-array,sizeof(STDataType)*ps-capacity*2); if (NULL tmp) { perror(realloc failed); return; } ps-array tmp; ps-capacity * 2; } ps-array[ps-top] x; ps-top; } //出栈操作 void STPop(Stack* ps) { assert(ps); assert(!STEmpty(ps)); ps-top--; } //访问栈顶元素 STDataType STTop(Stack* ps) { assert(ps); return ps-array[ps-top-1]; }2.队列2.1队列的概念以及结构队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFOFirst In First Out特点。入队列进行插入操作的一端称为队尾。出队列进行删除操作的一端称为队头。2.2队列的实现队列可以使用数组和链表结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。#pragma once #include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int QDataType; //队列中的每个节点的定义s typedef struct QueueNode { struct QueueNoe* next; QDataType data; }QNode; typedef struct Queue { QNode* head;//队列中的头结点 QNode* tail;//队列中的尾结点 int size;//记录当前队列中的元素 }Queue; //对队列进行初始化 void QueueInit(Queue* que); //对队列进行删除清理 void QueueDestroy(Queue* que); //查询队列是否为空 bool QueueEmpty(Queue* que); //返回队列的长度 int QueueSize(Queue* que); //入队列 void QueuePush(Queue* que,QDataType x); //出队列 void QueuePop(Queue* que); //访问队列的队头元素 QDataType QueueFront(Queue* que); //访问队列的队尾元素 QDataType QueueBack(Queue* que);#include Queue.h //对队列进行初始化 void QueueInit(Queue* que) { que-head que-tail NULL; que-size 0; } //对队列进行删除清理 void QueueDestroy(Queue* que) { assert(que); QNode* cur que-head; while (cur) { //遍历一遍队列元素 QNode* next cur-next; free(cur); cur next; } //到此已经删除队列元素 que-head que-tail NULL; que-size 0; } //查询队列是否为空 bool QueueEmpty(Queue* que) { assert(que); return que-size 0; } //返回队列的长度 int QueueSize(Queue* que) { assert(que); return que-size; } //入队列 void QueuePush(Queue* que, QDataType x) { //队尾进队头出 assert(que); //先创建出一个节点 QNode* newnode (QNode*)malloc(sizeof(QNode)); if (NULL newnode) { perror(malloc newnode failed); return; } //成功创建出节点 newnode-next NULL; newnode-data x; //在入队列之前先判断一下队列是否是空的 if (que-head NULL) { //头为空说明尾部肯定也是空 assert(que-tail NULL); que-head que-tail newnode; } else { //说明队列不是空的,队尾进队头出 que-tail-next newnode; que-tail newnode;//更新一下队尾的节点信息 } que-size; } //出队列 void QueuePop(Queue* que) { //队尾进队头出 assert(que); assert(!QueueEmpty(que)); //先判断一下队列里面是否就只有一个元素 if (que-head-next NULL) { //只有一个元素 free(que-head); que-head que-tail NULL; } else { //队列中不止只有一个元素 QNode* next que-head-next; free(que-head); que-head next; } que-size--; } //访问队列的队头元素 QDataType QueueFront(Queue* que) { //要访问元素首先得至少有一个 assert(que); assert(!QueueEmpty(que)); return que-head-data; } //访问队列的队尾元素 QDataType QueueBack(Queue* que) { //要访问元素首先得至少有一个 assert(que); assert(QueueEmpty(que) ! NULL); return que-tail-data; }除了普通的队列之外实际中我们有时还会使用一种队列叫做循环队列。例如生产者消费者模型就会使用循环队列。环形队列可以使用数组实现也可以使用循环链表实现。3.栈和队列OJ题1. 括号匹配问题。OJ链接思路利用栈这种数据结构如果是左括号就入栈遇到右边括号判断一下符不符合要求符合要求就出栈。2. 用队列实现栈。OJ链接思路利用两个队列来实现一个栈的部分接口保持que2队列是空的然后push的时候先往que2中push然后再把que1队列中的元素push进que2队列的后面然后再交换que1和que2队列。这样就能保证que1的front元素就是最后push的元素从而实现了类似于“栈”的效果。3. 用栈实现队列。OJ链接思路利用两个栈来实现一个队列的部分接口保持st2为空然后在push元素之前先把st1中的元素全部push进st2然后再把x元素push到st2栈顶最后把st2中的元素全部push回到st1中。从而就实现了FIFO的效果。4. 设计循环队列。OJ链接思路利用数组来模拟循环队列搞一个定长数组然后一个start变量表示队头元素的索引下标end变量表示队尾元素的下一个位置的索引capacity变量表示定长数组的size1个为啥是size1呢因为我们多开辟一个位置是标记位。其中判断循环队列是否为空使用start end ?来判断判断循环队列是否满使用 end 1% capacity start 来判断其中每次进队列或者出队列的时候end和start都要往后走1endend1%capacity or startstart1%capacity二叉树1.树概念以及结构1.1树的概念树是一种非线性的数据结构它是由nn 0个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来就像一棵倒挂的树也就是说它是根朝上而叶子是朝下的。有一个特殊的结点称为根结点根结点没有前驱结点。除了根结点之外其余结点被分成MM 0 个互不相交的集合t1、t2、......其中每一个集合ti1 i n又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或者多个后继。因此树是递归定义的。注意树形结构中子树之间不能有交集否则就不是树形结构。1.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棵互不相交的树的集合称为森林1.3树的表示树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既要保存值域也要保存节点与节点之间的关系。实际中树有很多种表示方式如双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。在这里我们就来简单了解一下其中的孩子兄弟表示法。typedef int DataType; struct Node { struct Node* firstChild;//表示第一个孩子节点 struct Node* nextBrother;//表示指向下一个兄弟节点 DataType data; //表示节点中的数据域 };1.4树在实际中的运用表示文件系统的目录树结构2.二叉树概念以及结构2.1概念一棵二叉树是结点的一个有限集合该集合1、或者为空。2、由一个根结点加上两棵别称为左子树和右子树的二叉树组成。从上图可以看出1、二叉树不存在度大于2的结点。2、二叉树的子树有左右之分次序不能颠倒因此二叉树是有序数。注意对于任意的二叉树都是由下面几种情况复合而成的2.2特殊的二叉树1.满二叉树一个二叉树如果每一层的节点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且节点数为2^k-1,则它就是满二叉树。2.完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个节点的二叉树当且仅当其每一个节点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。如果深度为K的完全二叉树的节点是的区间范围是[2^*(K-1), 2^K-1]完全二叉树的度为1的结点要么是0要么是12.3二叉树的性质1、若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个节点。2、若规定根结点的层数为1则深度为K的二叉树的最大节点数是2^K-1个。3、对任何一棵二叉树如果度为0其叶子节点个数为n0度为2的分支节点个数为n2则有n0n214、若规定根结点的层数为1具有n个节点的满二叉树的深度hlogn1注以2为底n1为对数5、对于具有n个节点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有a、若 i 0 i位置节点的双亲序号i-1/2; i 0i为根结点编号无双亲节点b、若2i 1 n,左孩子序号2i 1,2i 1 n 则无左孩子c、若2i 2 n,右孩子序号2i 2,2i 2 n 则无右孩子2.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; };3.二叉树的顺序结构以及实现3.1二叉树的顺序结构普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆一种二叉树使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两码事儿一个是数据结构一个是操作系统中管理内存的一块区域分段。3.2堆的概念以及结构如果一个关键码的集合K{K0K1,K2......Kn-1}把它的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中并满足Ki K(2*i1) 且 Ki K(2*i2) Ki K2i1 且 Ki K(2*i2) i0,1,2,3......,则称为小根堆或者大根堆。将根节点最大的堆叫做最大堆或者大根堆根节点最小的堆叫做最小堆或者小根堆。堆的性质1、堆中某个节点的值总是不大于或者不小于其父节点的值。2、堆总是一棵完全二叉树。3.3堆的模拟实现3.3.1堆向下调整算法现在我们给出一个数组逻辑上看作一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成为一个小堆。向下调整算法有一个前提左右子树必须是一个堆才可以调整。3.3.2堆的创建下面我们给出一个数组这个数组逻辑上可以看做一棵完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根节点左右子树不是堆我们该怎么调整呢这里我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。3.3.3建堆的时间复杂度因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明时间复杂度本来就是看近似值多几个节点不会影响最终结果因此建堆的时间复杂度ON3.3.4堆的插入先插入一个10数组到尾上再进行向上调整算法直到满足堆。3.3.5堆的删除删除堆是删除堆顶的数据将堆顶的数据和最后数据交换然后删除数组最后一个数据再进行向下调整算法。3.2.6堆的代码模拟实现这里实现一下大根堆#pragma once #include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int HPDataType; #define DEFAULTCAPACITY 4 //建立大堆 typedef struct Heap { HPDataType* array; int size; int capacity; }Heap; //初始化堆 void HPInit(Heap* php); //交换两个节点的信息 void Swap(HPDataType* p1, HPDataType* p2); //向上调整算法 void AdjustUp(HPDataType* array, int child); //向下调整算法 void AdjustDown(HPDataType* array, int n, int parent); //插入一个元素 void HPPush(Heap* php, HPDataType x); //删除第一个元素 void HPPop(Heap* php); //获取堆顶元素 HPDataType HPTop(Heap* php); //获取一共有多少元素 int HPSize(Heap* php); //判断堆是否为空 bool HPEmpty(Heap* php);#include Heap.h //初始化堆 void HPInit(Heap* php) { assert(php); php-array (HPDataType*)malloc(sizeof(HPDataType) * DEFAULTCAPACITY); if (NULL php-array) { perror(malloc failed); return; } php-size 0;//初始元素的下标索引为0 php-capacity DEFAULTCAPACITY; } //交换两个节点的信息 void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp *p1; *p1 *p2; *p2 tmp; } //向上调整算法---我们这里的堆是大根堆 void AdjustUp(HPDataType* array, int child) { //向上调整 int parent (child - 1) / 2; while (child 0) { //从下往上开始调整 if (array[child] array[parent]) { //父节点比孩子节点要小所以要调整 Swap(array[child], array[parent]); //交换完位置之后要更新位置 child parent; parent (child - 1) / 2; } else { //复合规则的 break; } } } //向下调整算法 void AdjustDown(HPDataType* array, int n, int parent) { //n为数组的大小 //向下调整---这里我们的堆是大根堆 int child parent * 2 1; while (child n) { //由于我们的堆是大根堆 //先判断左右孩子哪个更大---注意别child1越界了 if (child 1 n array[child 1] array[child]) { child; } //再判断当前的父节点和孩子节点的大小 if (array[child] array[parent]) { //先交换父节点和孩子节点 Swap(array[child], array[parent]); //更新节点的信息 parent child; child parent * 2 1; } else { //符合堆的条件 break; } } } //判断堆是否为空 bool HPEmpty(Heap* php) { assert(php); return php-size 0; } //获取一共有多少元素 int HPSize(Heap* php) { assert(php); return php-size; } //获取堆顶元素 HPDataType HPTop(Heap* php) { assert(php); return php-array[0]; } //插入一个元素 void HPPush(Heap* php, HPDataType x) { assert(php); //先判断当前是否需要扩容 if (php-size php-capacity) { HPDataType* tmp (HPDataType*)realloc(php-array,sizeof(HPDataType) * php-capacity * 2); if (NULL tmp) { perror(realloc failed); return; } php-array tmp; php-capacity * 2; } //插入数据并对堆进行向上调整 php-array[php-size] x; php-size; AdjustUp(php-array, php-size - 1); } //删除第一个元素 void HPPop(Heap* php) { assert(php); assert(!HPEmpty(php)); //先交换最后一个元素和第一个元素,然后删除最后一个元素 Swap((php-array[0]), (php-array[php-size - 1])); php-size--; AdjustDown(php-array, php-size, 0); }3.4堆的应用3.4.1堆排序堆排序即利用堆的思想来进行排序总共分为两个步骤1、建堆建立大根堆or建立小根堆2、利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。注堆排序排升序------建立大根堆堆排序排降序------建立小根堆//堆排序 void HeapSort(HPDataType* a, int n) { //传进来的数组和数组的大小 ////建堆---向上调整建堆---O(N*LogN) //for (int i 1; i n; i) //{ // AdjustUp(a, i); //} ////建堆---向下调整建堆---O(N) for (int i (n - 1 - 1) / 2; i 0; --i) { //从最后一个非叶子节点开始向下调整 AdjustDown(a, n, i); } //开始进行堆排序 int end n - 1;//最后一个元素 while (end 0) { //先交换最后一个元素和第一个元素 Swap(a[end], a[0]); AdjustDown(a, end, 0); --end; } }解释一下为啥堆排序的排升序要建立大根堆排降序要建立小根堆的原因我们先建立大根堆大根堆的含义是父节点要大于或者等于孩子节点这样我们的数组就变成了最大元素在堆顶最后一个元素是小元素。接着把堆顶元素和最后一个元素进行swap交换之后把最后一个元素排除在外向下调整数组n-1的元素。反复如此就让一个大根堆变成了升序数组大的元素被交换到了后面。排降序建立小根堆同理。4.Top-K问题Top-K问题即求数据中前K个最大的元素或者最小的元素一般情况下数据量都比较大。比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不打可取了可能数据都不能一下子全部加载到内存中。最佳的方式就是用堆来解决基本思路如下1、用数据集合中前K个元素来建堆前K个最大元素则建立小根堆。前K个最小元素则建立大根堆。2、用剩余的N-K个元素依次与堆顶元素进行比较不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K歌元素就是我们所要求的前K个最小或者前K个最大的元素。写一份代码测试一下#include stdio.h #include stdlib.h #include stdbool.h #include assert.h #include time.h void Swap(int* p1, int* p2) { int tmp *p1; *p1 *p2; *p2 tmp; } //建堆操作---向上调整建小根堆 void AdjustUp(int* 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 AdjustDown(int* 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 CreateData() { srand(time(NULL)); //先构建数据写到文件里面去 const char* filename data.txt; FILE* fp fopen(filename, w); if (NULL fp) { perror(Fopne fialed); return; } int n 10000; for (int i 0; i n; i) { int ran rand() % n;//在0~9999中随机生成 fprintf(fp, %d\n, ran); } fclose(fp); } //打印出前k个最大 void PrintTopK(const char* filename,int n,int k) { //先从文件中读取前k个元素建立小根堆 //先建立数组 int* a (int*)malloc(sizeof(int) * k); FILE* fp fopen(filename, r); if (NULL fp) { perror(Fopen fialed); return; } //先从文件中读取k个元素到数组中 for (int i 0; i k; i) { fscanf(fp, %d, a[i]); } //然后对这个k个元素进行建立小根堆 for (int i (k - 1 - 1) / 2; i 0; --i) { AdjustDown(a, k, 0); } //建堆完成之后,开始遍历剩下的N-K个元素 int val 0; int ret fscanf(fp, %d, val); while (ret ! EOF) { if (val a[0]) { //如果比堆顶元素要大就进入堆 a[0] val; AdjustDown(a, k, 0); } ret fscanf(fp, %d, val); } //打印一下数组中的内容 for (int i 0; i k; i) { printf(%d , a[i]); } printf(\n); free(a); fclose(fp); }5.二叉树链式结构的实现5.1二叉树的遍历5.1.1前序、中序以及后序遍历学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历是按照某种特定的规则依次堆二叉树中的结点进行相应的操作并且每个节点只操作依次。访问节点所做的操作依赖于具体的应用问题。遍历是二叉树最重要的运算之一也是二叉树上进行其他运算的基础。按照规则二叉树的遍历有前序、中序、后序的递归遍历。1、前序遍历访问根结点的操作发生在遍历其左右子树之前。2、中序遍历访问根结点的操作发生在遍历其左右子树之间。3、后序遍历访问根结点的操作发生在遍历其左右子树之后。由于被访问的结点必是某子树的根所以NNode、LLeft和RRight又可以解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。// 二叉树前序遍历 void PreOrder(BTNode* root); // 二叉树中序遍历 void InOrder(BTNode* root); // 二叉树后序遍历 void PostOrder(BTNode* root);前序遍历递归图解手写一个前序、中序、后序遍历的递归版本#include stdio.h #include stdlib.h #include assert.h typedef int DataType; typedef struct TreeNode { DataType data; struct TreeNode* left; struct TreeNode* right; }Node; Node* BuyNode(DataType x) { Node* newnode (Node*)malloc(sizeof(Node)); if (NULL newnode) { perror(malloc fail); return NULL; } newnode-data x; newnode-left NULL; newnode-right NULL; return newnode; } //前序遍历 void PreOrder(Node* root) { if (NULL root) return; printf(%d , root-data); PreOrder(root-left); PreOrder(root-right); } //中序遍历 void InOrder(Node* root) { if (NULL root) return; printf(%d , root-data); InOrder(root-left); InOrder(root-right); } //后序遍历 void PostOrder(Node* root) { if (NULL root) return; printf(%d , root-data); PostOrder(root-left); PostOrder(root-right); }5.2层序遍历层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点触发首先访问第一层的树根结点然后从左到右访问第2层上的节点接着是第三层的结点。依次类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。层序遍历需要借助队列这种数据结构一般先把root节点push进队列然后队列不为空就循环队列次遍历队列中的元素。5.3节点个数以及高度等1、二叉树的节点个数int BinaryTreeSize(BTNode* root) { return root NULL ? 0:BinaryTreeSize(root-left)BinaryTreeSize(root-right)1; }2、二叉树叶子节点个数int TreeSize(BTNode* root) { if(root NULL) return 0; if(!root-left !root-right) return 1; return TreeSize(root-left) TreeSize(root-right); }3、二叉树第k层节点的个数要求第k层节点的个数就代表要求左子树的第k-1层的节点个数加上右子树的第k-1层的节点个数int TreeLevelKSize(BTNode* root,int k) { if(k 0) return 0; if(k 1) return 1; int leftSizeTreeLevelKSize(root-left, k-1); int rightSizeTreeLevelKSize(root-right, k-1); return leftSizerightSize; }5.4二叉树基础OJ题1. 单值二叉树。OJ链接思路使用递归的方式首先如果存在左右子树就拿着当前节点值和左右子树进行比较。然后递归分别求出左子树是否是单值右子树是否是单值。2. 检查两颗树是否相同。OJ链接思路使用递归首先两棵树都存在的情况下保存它俩的结点是否相同的布尔值如果任意一个不存在则直接返回false接着再分别判断它俩的左右子树的节点值是否相同。3. 对称二叉树。OJ链接思路使用递归首先判断临界条件然后取root的左右子树判断其左右子树是否对称具体如何判断对称呢如果左右子树对称则左子树的左节点值等于右子树的有节点值左子树的右节点值等于右子树的左节点值。4. 二叉树的前序遍历。OJ链接思路常规的前序遍历无需多言。5. 二叉树中序遍历。OJ链接思路常规的中序遍历无需多言。6. 二叉树的后序遍历。OJ链接思路常规的后序遍历无需多言。7. 另一颗树的子树。OJ链接思路首先写一个判断两棵树是不是相同的方法。然后遍历root的左右子树上的结点从它的左右子树的节点开始跟subRoot树进行比较看两者是否相同。5.5二叉树的创建和销毁1、关于通过一个前序遍历的数组ABD##E#H##CF##G##构建二叉树的问题思路构建时我们只需按照同样的顺序递归创建节点遇到字符不是#就创建新节点然后递归构建左子树再递归构建右子树遇到#则返回NULL。2、判断二叉树是否是完全二叉树思路根据完全二叉树的定义前k-1层都是满的第k层的元素都是从左向右连续的。所以我们只需要对树进行层序遍历非空节点一定是连续的。#include iostream #include queue using namespace std; typedef int DataType; struct TreeNode { TreeNode* _left; TreeNode* _right; DataType _data; }; //判断一棵树是否为完全二叉树 bool isComplicate(TreeNode* root) { if (!root) return true; queueTreeNode* myq; bool hasNull false; myq.push(root); while (myq.size()) { int sz myq.size();//这一层队列中有多少元素 while (sz--) { TreeNode* tmp myq.front(); myq.pop(); if (tmp-_left) { if (!hasNull) myq.push(tmp-_left); else return false; } else hasNull true; if (tmp-_right) { if (!hasNull) myq.push(tmp-_right); else return false; } else hasNull true; } } return true; }