数据结构二叉树算法(数据结构二叉树知识点总结)

计算机科学一直是当今的热门专业。每年都有很多人从事这份方便的工作，也有很多人考研。考研计算机专业课程为全国统一考试科目，包括四个科目。知识点还是很多的。我们来看看考研计算机数据结构的核心考点二叉树。

?二叉树遍历

遍历的过程是将具有非线性结构的二叉树中的节点排列成线性序列的过程。

二叉树的遍历方法可以分为两类。一种是“广度优先”方法，从根节点开始，从上到下、从左到右逐层遍历；另一种是“深度优先”方法。 ”，即一棵子树遍历一棵子树。

从整体二叉树结构来看，二叉树可以分为三个部分：根节点、左子树和右子树。只要遍历完这三部分，二叉树就遍历完了。假设D代表根节点，L代表左子树，R代表右子树，则DLR有六种组合，分别是DLR、DRL、LDR、LRD、RDL和RLD。如果限制为先左后右，那么就只有三种：DLR、LDR、LRD，分别称为前（前）序法（第一根序法）、中序法（中根）序法、对称法）和后序法（最后序法）。根序法）。三种递归遍历算法如下：

1. 预订方式（DLR）

如果二叉树为空，则不进行操作，否则：访问根节点，依次遍历左子树，依次遍历右子树。

2. 中间顺序法（LDR）

如果二叉树为空，则不进行操作，否则：中序遍历左子树，访问根节点，中序遍历右子树。

3. 后序法（LRD）

如果二叉树为空，则不进行操作，否则：后序遍历左子树，后序遍历右子树，访问根节点。

?完全二叉树相关节点个数的计算

完全二叉树的定义：深度为k、有n 个节点的二叉树，当且仅当其每个节点对应于深度为k 的满二叉树中编号为1 到n 的节点时，称为完全二叉树。二叉树。

完全二叉树的叶子数为(n + 1)/2 向下舍入。

?森林和二叉树之间的转换以及转换过程中节点之间的关系

将树转换为二叉树的方法是：

1. 在树中所有相邻兄弟之间添加一条连接线。

2、对于树中的每个节点，只保留它与第一个子节点之间的连接，删除它与其他子节点之间的连接。

3、以树的根节点为轴，将整棵树顺时针旋转一定角度，使结构具有层次感。

将森林转换为二叉树的方法如下：

1. 将森林中的每棵树转换为对应的二叉树。

2、第一棵二叉树不动。从第二棵二叉树开始，后一个二叉树的根节点作为前一个二叉树根节点的右子节点。当所有的二叉树连接在一起时，得到的二叉树就是由森林转换而来的二叉树。

树和森林都可以转换为二叉树。两者的区别在于，树转换成的二叉树的根节点必须没有右孩子，而森林转换成的二叉树的根节点有右孩子。将二叉树恢复为树或森林，如下所示：

1. 如果一个节点是其父节点的左子节点，则将该节点的右子节点、右子节点的右子节点、与该节点的父节点用线连接起来。

2、删除原二叉树中父节点与右子节点的所有连接。

3. 组织步骤1和2中获得的树木或森林，使结构具有层次结构。

计算机科学是一门非常广泛和深刻的学科。它包含的内容千变万化，可以学到的东西数不胜数。二叉树是重要的考点，考生应该牢牢掌握它们。

  相关文章:

  第1篇    高中物理力的合成与分解技巧(物理高中力的合成与分解)    作者：admin

   三、力(常见的力、力的合成与分解)(1)常见的力1.重力G=mg(方向竖直向下，g=9.8m/s2≈10m/s2，作用点在重心，适用于地球表面附近)2.胡克定律F=kx{方向沿恢复形变方向，k：劲度系数(N/m)，x：形变量(m)｝3.滑动摩擦力F=μFN{与物体相对运动方向相反，μ：摩擦因数，FN：正压力(N)｝4.静摩擦力0≤f静≤fm(与物体相对

  第2篇    金属及其化合物知识点总结(高中化学金属及其化合物)    作者：admin

   金属及其化合物一、金属活动性Na＞Mg＞Al＞Fe。二、金属一般比较活泼，容易与O2反应而生成氧化物，可以与酸溶液反应而生成H2，特别活泼的如Na等可以与H2O发生反应置换出H2，特殊金属如Al可以与碱溶

  第3篇    清华大学2018年自主招生人数(清华大学2018自主招生试题数学)    作者：admin

   6月10日，清华大学2018年自主招生考试全面启动，2018年清华大学自主招生、领军计划依然在全国设置多个考点，考生可就近选择。自主招生测试为初试和复试。一、笔试时间初试时间为6月10日上午9:00-12:00，共3个小时。二、笔试模式初试采用笔试形式，理科类：数学、物理、化学；文科类：数学、语文、历史。清华理科笔试都是选择，共75题，数学35道题，

  第4篇    高考语文基础知识训练试题第十三套答案(高考语文基础知识训练试题第十三套卷)    作者：admin

   1.下列划线字的读音全部相同的一项是（）A．行旅行头行将就木行贿受贿B．给予给水自给自足不给面子C．测量掂量丈量土地量入为出D．应该应届得心应手理应如此2.下列各组词语中，字形全都正确的一组是（）A．脉搏扶直贫困晶莹寥若辰星B．焕发一幅对联关键性格不合C．提纲情有可原厮打连年歉收D．幅射绿草如茵松弛旁征博引3.依次填

  第5篇    甲烷的氧化反应现象(甲烷氧化的化学方程式)    作者：admin

   甲烷的氧化反应最基本的就是燃烧，高考网为大家整理了《2016高考化学知识点：甲烷的氧化反应》，供大家参考，更多关于甲烷的氧化反应知识点详解请关注高考网。2016高考化学知识点：甲烷的氧化反应甲烷氧化反应最基本的就是燃烧：甲烷完全燃烧：CH4+2O2=CO2+2H2O甲烷不完全燃烧：2CH4+3O2=2CO+4H2O甲烷