兖州中材建设有限公司网站,wordpress怎么选择中文版,珠海网站开发价格,wordpress更换域名缩略图不显示文章目录 前言1. 二叉树链式结构的意义2. 手搓一棵二叉树3. 二叉树的遍历#xff08;重要#xff09;3.1 遍历的规则3.2 先序遍历3.3 中序遍历3.4 后序遍历3.5 遍历的代码实现3.5.1 先序遍历代码实现3.5.2 中序遍历代码实现3.5.3 后序遍历代码实现 4. 统计二叉树结点的个数5.… 文章目录 前言1. 二叉树链式结构的意义2. 手搓一棵二叉树3. 二叉树的遍历重要3.1 遍历的规则3.2 先序遍历3.3 中序遍历3.4 后序遍历3.5 遍历的代码实现3.5.1 先序遍历代码实现3.5.2 中序遍历代码实现3.5.3 后序遍历代码实现 4. 统计二叉树结点的个数5. 统计二叉树的高度6. 统计二叉树的指定层数的结点个数 前言
如果有看过的堆和堆排序这篇文章的话你一定对二叉树的顺序存储有了一定的了解但是这个是有特定的使用环境的。
那么在本文中我将要给大家讲解二叉树的另一种表示方式——链式结构以及我会给大家讲解有了顺序存储结构为什么还要使用链式存储结构以及如何用链式创建一棵二叉树此外还要讲解递归在二叉树中扮演着何种角色 1. 二叉树链式结构的意义
在学习堆时我们说堆的本质就是一棵完全二叉树而完全二叉树的结构注定了我们使用顺序表来存储比较方便而这个就是二叉树的顺序存储。 可能大家也意识到了一个点好像二叉树的顺序存储有个要求那就是这棵二叉树必须得是完全二叉树。没错
如果我们不分青红皂白地使用顺序结构来存储二叉树会发生什么可怕的是事情呢 请大家将目光往下注视 可以看到如果我们遇到的是一棵非完全二叉树并且我们还要有顺序结构来存储这棵树。第一步我们就得在逻辑上将这颗树补全为完全二叉树但是补的地方我们是不能进行任何的操作的。那这个就十分尴尬自己创建的空间却不能愉快地使用有点扯淡了而且这样的方式很浪费空间资源从上图你就可以看出有几个空间是没有办法使用的。
那该怎么办呢此时天空一声巨响二叉树的链式结构就闪亮登场了
二叉树的链式结构针对的群体就是普通的二叉树。 那至于普通二叉树链式是如何被我们用代码创建的让我们接着往下看
2. 手搓一棵二叉树
这里为了降低大家的学习成本我先不教大家如何用函数创建二叉树如果大家对自己的二叉树比较有自信的话可以移步到本文的后面学习如何用函数创建一棵二叉树。
学习是要一步一步来的我们不能不懂装懂有时候也得直面不完美的自己
二叉树链式结构示意图
那我们这里开始就开始手搓一棵二叉树为了方便大家学习我会按照下面的图的给大家建立往后的操作都是以这副图为基础。 代码如下
//二叉树结点的结构体
typedef int BTDataType;typedef struct BTNode
{BTDataType data;struct BTNode* left;struct BTNode* right;}BTNode;BTNode* BuyNewnode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));newnode-data x;newnode-left NULL;newnode-right NULL;return newnode;
}BTNode* CreateTree()
{BTNode* node1 BuyNewnode(1);BTNode* node2 BuyNewnode(2);BTNode* node3 BuyNewnode(3);BTNode* node4 BuyNewnode(4);BTNode* node5 BuyNewnode(5);BTNode* node6 BuyNewnode(6);//开始结点之间的链接node1-left node2;node1-right node3;node2-left node4;node2-right node5;node3-right node6;return node1;
}这种方式初学者来说十分的友好。 3. 二叉树的遍历重要
接下来我来讲一下本文的精华 —— “二叉树的遍历”。为什么会说是精华的部分呢因为想要学会这个就得先知道递归的规则并且这是科班同学在练习中会经常遇到的题目。同时这个也是二叉树的入门门槛
二叉树遍历有四种方式分别是 先序遍历可能有的书籍会称其为先根遍历中序遍历后序遍历层序遍历 3.1 遍历的规则
先序遍历遍历顺序为根、左子树、右子树。记忆的规则就是先序又称先根顾名思义就是根结点先遍历。中序遍历遍历顺序为左子树、根、右子树。记忆的规则就是中序是将根结点放在遍历的中间顺序。后序遍历遍历顺序为左子树、右子树、根。记忆的规则就是后序是将根节点但在遍历的最后顺序。层序遍历遍历的顺序时按照一层层开始每一层从左往右依次遍历各节点。
在本文会重点讲解先序遍历、中序遍历以及后序遍历。
为了更好的讲解每种遍历的规则接下来我会分篇幅给大家做进一步的讲解。
3.2 先序遍历
先序遍历遍历顺序为根、左子树、右子树。
任何一颗树都是由根节点及其子树所构成的。二叉树也是如此二叉树由其根节点、左子树和右子树所构成。其中左子树由其根节点、左子树和右子树所构成…。给人一种循环的感觉而这个就是递归大家可以从下图(只做了部分的划分)感受一下 好了我们根据先序遍历的规则写出它的数据遍历的顺序注意空树用NULL表示。 先序遍历的顺序1 2 4 NULL NULL 5 NULL NULL 3 NULL 6 NULL NULL 怎么样不是很困难吧。
3.3 中序遍历
中序遍历遍历顺序为左子树、根、右子树
趁热打铁我们把中序遍历也讲了。
有了先序遍历的经验中序遍历洒洒水啦 这里我就直接写答案了 中序遍历的顺序NULL 4 NULL 2 NULL 5 NULL 1 NULL 3 NULL 6 NULL 3.4 后序遍历
后序遍历遍历顺序为左子树、右子树、根。 后序遍历的顺序NULL NULL 4 NULL NULL 5 2 NULL NULL NULL 6 3 1 3.5 遍历的代码实现
这个就体现出递归的魅力时刻了
这里我会拿先序遍历作为重点讲解其余遍历方式的思维都是一样的。
3.5.1 先序遍历代码实现
先序遍历遍历顺序为根、左子树、右子树。
//先序遍历
void PreOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%d ,root-data);PreOrder(root-left);PreOrder(root-right);
}当遇到一个递归却被深深绕进去时最好画一个递归展开图 3.5.2 中序遍历代码实现
中序遍历遍历顺序为左子树、根、右子树
//中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d ,root-data);InOrder(root-right);
}3.5.3 后序遍历代码实现
后序遍历遍历顺序为左子树、右子树、根。
//后序遍历
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}可能大家在平常的练习中看到的是这种形式的 要想出来这个效果我们只需要把printf(NULL )这个语句注释掉即可。但是需要提醒大家的一点就是上面这幅图的结果并不是二叉树原本的模样大家要理解本质 4. 统计二叉树结点的个数
在这里我要给大家将一个非常重要的思想 —— “分治思想”。 给大家设置一个场景假如现在我是一位大学的校长我要统计学校的人数。我该怎么做 第一种方法我到学生宿舍一个一个人的统计人数每当宿舍有一个新生时我就在我的小本本上画正字的一个笔画。最后我只要统计小本本上有多少个正字即可。 但是这个方法非常的费校长。不经的会感叹到这个校长当得也太累了吧 第二种方法既然身为一校之长我肯定有一定的权力。我就让每个院的院长汇报各自院的人数给我我再统计不就好了。院长接到任务后就命令每个专业的系主任汇报各专业人数给我。每个系主任又叫每个班的班长统计各班的人数给他。之后以宿舍为单位让宿舍长汇报宿舍人数给班长班长再做汇总将结果给系主任。 这不就纯纯是打工人体系 汇报人数的情况 有了这个思想之后我们写代码
int TreeSize(BTNode* root)
{//写法一if(root NULL){return 0;}return TreeSize(root-left) TreeSize(root-right) 1;/* //写法二return root NULL? 0: TreeSize(root-left) TreeSize(root-right) 1;*/
}5. 统计二叉树的高度
用了分治思想这个代码似乎也能理解了。
int TreeHeight(BTNode* root)
{if(root NULL){return 0; }int left_height TreeHeight(root-left);int right_height TreeHeight(root-right);return left_height right_height? left_height 1:right_height 1;}6. 统计二叉树的指定层数的结点个数
这里给大家提供一个思路当前K层结点的个数 对应左子树K-1层结点的个数 对应右子树K-1层结点的个数
int TreeKLevel(BTNode* root, int k)
{if(root NULL){return 0;}if(k 1){return 1;}int leftK TreeKLevel(root-left,k-1);int rightK TreeKLevel(root-right,k-1);return leftK rightK;
} 好了本文就到这里结束了
本文主要讲解了二叉树链式结构的定义以及接口的实现其中有个重要的思想可以帮助我们更快的理解递归背后的本质体会到递归的魅力。
最后如果觉得本文写的不错的话麻烦给偶点个赞吧
