摘要：文章目录前言二叉树的链式结构二叉树的遍历方式前序遍历中序遍历后序遍历二叉树前中后序遍历练习前序遍历练习中序遍历练习后序遍历练习利用前序遍历中序遍历结合二叉树其他操作二叉树结点个数二叉树叶子结点个数二叉树第层节点个
typora-copy-images-to: upload
上一章讲到二叉树的顺序结构实现以及运用,而此篇文章是为了讲解二叉树的链式结构以及相关运用.
如果想用链式结构进行实现二叉树,那么一定少不了左右指针(指向孩子),所以实现结构如下:
typedef char BTDataType;typedef struct BinaryTree{ BTDataType val; struct BinaryTree* left; struct BinaryTree* right;}BTNOde;二叉树的遍历方式主要有四种,前面先介绍3种,最后再介绍第四种.
其中这三种遍历方式一般都用递归进行实现.
上面已经说到,前序遍历方式为根结点—>左子树—>右子树,我们用下图为例
按照前序遍历方式,其遍历顺序为A–>B–>D–>R–>T–>E–>Y–>C–>Q–>U–>W,这个答案可能和大家想的不一样,理由就是没有明白我们的遍历方式.按照前序遍历方式,我们应该先遍历根结点,即A,然后遍历左子树,当进入左子树后,我们是需要又执行前序遍历方式,即遍历根结点B,然后又要遍历左子树,当我们再进入左子树,又是先遍历根结点即D,然后又遍历左子树,按照顺序遍历到R,此时终于完成 根结点,左子树,我们遍历右子树,进入右子树后又遍历根结点,即T…所以我们的这种遍历方式其实递归性质的.
前序遍历代码:
void PreOreder(BTNode* root){ if(!root) return ; //如果为空结点,直接打印NULL printf("%c-->",root->val); //遍历根结点 PreOreder(root->left); //遍历左子树 PreOreder(root->right); //遍历右子树}测试:
中序遍历方式为左子树,根结点,右子树,所以仍以上面的图为例,我们的遍历方式顺序为:
R–>D–>T–>B–>E–>Y–>A–>Q–>U–>C–>W
中序遍历代码:
void InOrder(BTNode* root){ if(!root) return; //如果当前结点为空,直接结束 InOrder(root->left); //遍历左子树 printf("%c",root->val); //打印当前结点值 InOrder(root->right); //遍历右子树}测试:
后序遍历方式为 左子树,右子树,根结点.,按照上面的图示,我们得出的遍历顺序应该如下:
R–>T–>D–>Y–>E–>B–>U–>Q–>W–>C–>A
后序遍历代码如下:
void PostOrder(BTNode* root){ if(!root) return; //如果当前结点为空,直接结束 InOrder(root->left); //遍历左子树 InOrder(root->right); //遍历右子树 printf("%c",root->val); //打印当前结点值}测试:
按照递归思想,计算二叉树的结点数量,我们可以认为
数量 = 1 + 左子树数量 + 右子树数量,其中1是当前根结点数量(前提是存在)
int BinaryTreeSize(BTNode* root){ if(!root) return 0; int left = BinaryTreeSize(root->left); int right = BinaryTreeSize(root->right); return 1 + left + right;}按照递归思想,计算二叉树的叶子结点数量,我们可以认为
数量等于 = 0 + 左子树叶子结点数量 + 右子树叶子结点数量,0是因为当前根结点有子树,说明根结点不是叶子结点.
int BinaryTreeLeafSize(BTNode* root){ if(!root) return 0; if(root->left == NULL && root->right == NULL) return 1; int left = BinaryTreeLeafSize(root->left); int right = BinaryTreeLeafSize(root->right); return left + right;}第k层是指从根结点开始算第一层,往下到第K层.
按照递归思想我们反过来,根结点是第k层,后面向下k逐渐递减,k等于1时候便是我们所求.
而数量等于左子树第k层加上右子树第k层.
int BinaryTreeKSize(BTNode* root,int k){ if(!root) return 0; if(k==1) return 1; int left = BinaryTreeLeafSize(root->left,k-1); int right = BinaryTreeLeafSize(root->right,k-1); return left + right;}按照递归思想,先判断当前结点是否是目标,然后查找左子树,再查找右子树.
如果左右子树都没有找到,就返回
NULL
BTNode* BinaryTreeFind(BTNode* root, int n){ if(!root) return NULL; if(root->val == n) return root; BTNode* left = BinaryTreeFind(root->left,n); if(left) return left; BTNode* right = BinaryTreeFind(root->right,n); if(right) return right; return NULL;}按照递归思想,二叉树的高度等于1 + 左右子树高度的最大值.
int BinaryTreeDepth(BTNode* root){ if(!root) return 0; int left = BinaryTreeDepth(root->left); int right = BinaryTreeDepth(root->right); int maxval = left < right ? right : left; return 1 +maxvalue;}层序遍历我们一般需要使用队列,什么是程序遍历呢?
层序遍历就是遍历顺序是**整整一层,**以下图为例:
程序遍历结果为: 3-->4-->3-->8-->6-->6-->7.
而我们利用队列是怎样进行实现呢?答案是先进去一个结点,再出去一个结点,但是结点出去之前,孩子按左右顺序进入.
如下图:
我们前面已经实现过了队列的各种操作,这里便不再续写队列,直接引用.
队列定义细节修改:
typedef struct BinaryTree QDataType;typedef struct Queue{ QdataType* val; struct Queue* next;}Queue;层序遍历:
int main(){ Queue q = {0}; BTNode* tree = CreateTree(); QueueInit(&q); QueuePush(&q,tree); while(!QueueEmpty(&q)) { BTNode* top = QueueFront(&q); QueuePop(&q); if(top->left) QueuePush(&q,top->left); if(top->right) QueuePush(&q,top->right); printf("%c ",top->val); } return 0;}文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/119951.html
摘要：代码实现如下二叉树的创建与销毁二叉树的创建问题通过前序遍历的数组给定一串字符串，代表的是空树，其他的都是节点。 ⭐️本篇博客我要来和大家一起聊一聊数据结构中的二...
摘要：完全二叉树完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。链式存储二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。而完全二叉树更适合使用顺序结构存储。 目录 树概念及结构 树的概念 树的相关概念 树的表示 树在实际中的运用（表示文件系统的目...
摘要：但是二叉树的一些基本实现结构，例如前序遍历，中序遍历。。。二叉树节点声明二叉树的遍历二叉树的遍历，是学习二叉树结构的重要部分。一颗二叉树的节点个数主要以三个部分构成根节点左子树的节点个数右子树的节点个数。 前言 二叉树不同于顺序表，一颗普通的二叉树是没有增删改查的意义。普通的二叉树用来存...
文章目录 前言树的概念树的表示树结构在实际中的运用二叉树的概念特殊的二叉树满二叉树完全二叉树二叉树性质 二叉树的存储结构顺序存储链式存储 熟悉树结构的习题练习 前言 陆陆续续的,我们已经学完了顺序表,链表,栈和队列等线性的数据结构,而今天博主要介绍的就是树形的数据结构,和线性数据结构一样,我们先介绍什么是树形结构以及树的特点 树的概念 树是一种非线性的数据结构，它是由n（n>=0）个有...
阅读 2877·2021-11-19 11:31
阅读 2955·2021-09-26 09:55
阅读 1882·2021-09-14 17:57
阅读 2936·2021-09-02 15:15
阅读 861·2019-08-29 17:22
阅读 944·2019-08-29 16:38
阅读 2349·2019-08-26 13:56
阅读 715·2019-08-26 12:16
