坪山医院网站建设,龙岗网站建设推广报价,郑州网站制作汉狮,做室内概念图的网站#x1f387;个人主页#xff1a;Ice_Sugar_7 #x1f387;所属专栏#xff1a;初阶数据结构 #x1f387;欢迎点赞收藏加关注哦#xff01; 文章目录 #x1f349;前言#x1f349;链式结构#x1f349;遍历二叉树#x1f34c;前序遍历#x1f34c;中序遍历#x… 个人主页Ice_Sugar_7 所属专栏初阶数据结构 欢迎点赞收藏加关注哦 文章目录 前言链式结构遍历二叉树前序遍历中序遍历后序遍历 计数求结点数求叶子结点数求第k层结点数 树的深度查找结点构建二叉树销毁二叉树层序遍历判断是否为完全二叉树补充 写在最后 前言
在上一篇文章中我们讲了二叉树的顺序结构但是普通二叉树因为结点不连续没法使用顺序结构这就需要使用链式结构进行存储。本文将讲解二叉树的链式结构及常见函数的实现 链式结构
一个结点分为三个部分存放当前结点的数值的数据域、分别指向左、右子树的指针
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;遍历二叉树
二叉树有三种遍历方式通过递归实现 需要根据使用场景选择不同的遍历方式
前序遍历
先访问根结点接着是左子树最后访问右子树这里的“访问”指的是把结点的数值打印出来 采用递归那就要将大问题拆分为小问题直到问题无法再继续拆分 ●现在要访问左子树那可以把问题拆解为“依次访问它的根结点、左子树、右子树”拆解若干次之后会抵达叶子结点再往下就是空结点了此时没法继续拆解问题也就是到达递归的终点了需要回归了 ●右子树也同理
void BinaryTreePrevOrder(BTNode* root) {if (!root) { cout NULL ; //为了方便观察所以把NULL也打印出来return;}cout root-_data ;BinaryTreePrevOrder(root-_left);BinaryTreePrevOrder(root-_right);
}有了前序遍历作为参照那中后序遍历也就很轻松就能写出来了只要调整一下打印语句的位置就ok了下面直接上代码
中序遍历
void BinaryTreePrevOrder(BTNode* root) {if (!root) { cout NULL ; //为了方便观察所以把NULL也打印出来return;}BinaryTreePrevOrder(root-_left);cout root-_data ;BinaryTreePrevOrder(root-_right);
}后序遍历
void BinaryTreePrevOrder(BTNode* root) {if (!root) { cout NULL ; //为了方便观察所以把NULL也打印出来return;}BinaryTreePrevOrder(root-_left);BinaryTreePrevOrder(root-_right);cout root-_data ;
}计数
求结点数
求结点数可以转化为左子树结点数右子树结点数1根结点本身如果遇到空结点那就返回0
int BinaryTreeSize(BTNode* root) {if (!root)return 0;return BinaryTreeSize(root-_left) BinaryTreeSize(root-_right) 1;
}求叶子结点数
和求结点数差不多不过多了一个判断是否为叶子结点的语句如果是就返回1
//左右结点都为空返回1
int BinaryTreeLeafSize(BTNode* root) {if (!root)return 0;if (root-_left NULL root-_right NULL)return 1;//不为空or只有一个子树为空return BinaryTreeLeafSize(root-_left) BinaryTreeLeafSize(root-_right);
}求第k层结点数
这个的递归不太好找。 方法如下 假设k为5那么第k层相对于第一层就是第五层而它相对第二层则是第四层相对第三层是第三层……相对第五层就是第一层。也就是说要求第k层实际上是求“第一层”的结点个数有点像求一个数的阶乘时用到的递归思想
int BinaryTreeLevelKSize(BTNode* root, int k) {assert(k 0); //确保k为正数if (!root)return 0;if (k 1) //此时已经递归到了第k层return 1;return BinaryTreeLevelKSize(root-_left, k - 1) BinaryTreeLevelKSize(root-_right, k - 1);
}树的深度
深度是指从根结点到叶子结点的最长距离。这个问题可以拆解为求第二层的根结点到叶子结点的最长距离1再拆为第三层到叶子结点的最长距离2……最后遇到空结点就可以停下来了 最后返回左子树和右子树二者深度的较大值 代码如下
int BinaryTreeDepth(BTNode* root) {if (!root)return 0;int LeftSize BinaryTreeDepth(root-_left);int RightSize BinaryTreeDepth(root-_right);return LeftSize RightSize ? LeftSize 1 : RightSize 1;
}查找结点
要在二叉树里面查找值为x的结点。每次递归先找左子树找到就返回找不到就去找右子树。 下面两个条件满足其一递归终止①到空结点时返回NULL②找到值为x的结点就返回该结点 代码如下
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {if (!root)return NULL;if (root-_data x)return root;BTNode* ret BinaryTreeFind(root-_left, x);if (ret) //如果左子树找到指定结点就不用找右子树了return ret;return BinaryTreeFind(root-_right, x);
}构建二叉树
现在已知一个数组它是某二叉树前序遍历的结果该数组会用#表示空结点现在要我们通过这个数组来构建原二叉树 ●通过递归来构建。每次递归时数组当前位置的元素如果不为#就创建一个结点然后将它和双亲结点连起来。 ●既然要让结点间能够连接起来那函数就要返回结点或者NULL。这样在递归的过程中可以将新创建的结点或者NULL和双亲结点连接起来 ●递归的停止条件就是遇到#此时返回NULL
BTNode* BinaryTreeCreate(BTDataType* a, int n, int pi) { //n数组大小 pi指向数组下标if (a[pi] #) {pi;return NULL;}BTNode* node (BTNode*)malloc(sizeof(BTNode));node-_data a[pi]; //数组赋值给node之后记得node-_left BinaryTreeCreate(a, n, pi); //连接左子树node-_right BinaryTreeCreate(a, n, pi); //连接右子树return node; //返回根结点
}这里要说一下这个pi因为我们使用递归而非迭代需要知道数组下标即递归到哪个元素了所以要传下标 销毁二叉树
要采用后序遍历销毁结点如果采用前序或中序根结点都不是最后销毁的这样会导致无法找到某一边的子树。比如采用中序销毁左子树后把根结点给销毁了那就没法找到右子树了
void BinaryTreeDestory(BTNode** root) {assert(root);if (*root NULL)return;BinaryTreeDestory((*root)-_left);BinaryTreeDestory((*root)-_right);free(*root);*root NULL;
}层序遍历
前面讲的前、中、后序遍历都属于深度优先遍历以前序遍历为例会先递推到最左下的结点然后才回归这是一个纵向的过程。 而层序遍历又称为广度优先遍历顾名思义就是一层一层遍历。这种遍历需要使用队列 具体的过程为先让根结点入队标记为队首front然后将它的左右子树根结点入队前提是结点不为空如果为空那就不用入再让队头的根结点出队子树的根结点成为新的队头。 重复上面这个过程直到队列为空 举个栗子 代码如下
void BinaryTreeLevelOrder(BTNode* root) {if (!root)return;Queue q;QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q)) {QDataType front QueueFront(q); //队首元素cout QueueFront(q)-_data endl;QueuePop(q); //队首元素出队 然后要让它的左右子树入队if (root-_left)QueuePush(q, front-_left);if (root-_left)QueuePush(q, front-_right);}QueueDestroy(q);
} 判断是否为完全二叉树
完全二叉树的特点就是结点连续根据这个性质我们采用层序遍历不过这次层序遍历需要把空结点也入队。如果遇到空结点时后面的结点也全为空那就是完全二叉树反之如果后面还有非空结点那就不是 简而言之我们要判断front为空结点时队列剩下的元素是否全为空 代码如下
bool BinaryTreeComplete(BTNode* root) {if (!root)return true;Queue q;QueueInit(q);QueuePush(q, root);BTNode* front root;while (!QueueEmpty(q)){front QueueFront(q); if (front NULL) //队首是空结点就是遇到的第一个空结点跳出循环break;//空结点也要入队QueuePush(q, front-_left);QueuePush(q, front-_right);QueuePop(q); //队首元素出队}//到这里的时候说明已经遇到空结点//接下来要排查剩下的结点看看是否有非空结点while (!QueueEmpty(q)) {front QueueFront(q);QueuePop(q);if (front) { //若遇到不为空的结点说明不是完全二叉树QueueDestroy(q);return false;}}//到这里说明全部都是空结点那就是完全二叉树了QueueDestroy(q);return true;
}补充 while (!QueueEmpty(q)) {front QueueFront(q);QueuePop(q);if (front) { QueueDestroy(q);return false;}}我们已经将队首的结点pop掉那后面的if语句还能否访问front 答案是可以。因为front保存队首结点的值而这个值是二叉树结点的地址即指向二叉树的结点。刚才上面那个图是为了方便理解所以才把front的箭头指向队首pop掉队首结点并不会影响树的结点所以还是可以访问的 写在最后
以上就是本篇文章的全部内容如果你觉得本文对你有所帮助的话那不妨点个小小的赞哦比心
