求一颗二叉树叶子节点数算法的倒数第二层中数值最大的节点的值。如果深度不足2层返回1<<31

来源：蜘蛛抓取(WebSpider) 时间：2019-04-24 12:34 标签： 二叉树叶子节点数算法

树结构是面试中的考察的重点洏树的遍历又是树结构的基础。 

 //先序遍历递归版本 // 把根节点加入结果集 前序遍历顺序：根、左，右 所以对应的进栈顺序为：右、左（根節点进栈后马上出栈了） * 先序遍历递归版本

 堆有最大堆和最小堆之分最大堆就是每个节点的值都>=其左右孩子（如果有的话）值的完全二叉树叶子节点数算法。最小堆便是每个节点的值都<=其左右孩子值的完全二叉樹叶子节点数算法 


堆的三种基本操作(以下以最大堆为例)： 


⑴最大堆的插入 

    由于需要维持完全二叉树叶子节点数算法的形态，需要先将要插入的结点x放在最底层的最右边插入后满 足完全二叉树叶子节点数算法的特点； 

  然后把x依次向上调整到合适位置满足堆的性质,例如下图Φ插入80,先将80放在最后,然后两次上浮到合适位置.  


 //向最大堆中插入元素, heap:存放堆元素的数组
 
 
 //上升，让插入的数和父节点的数值比较当大于父节點的时候就和父节点的值相交换 
 
 //注意由于数值是从下标为1开始，当index = 1的时候已经是根节点了 
 
 //获取相应位置的数值 
 //如果父亲节点比index的数值小，就交换二者的数值 
 
 

    操作原理是：当删除节点的数值时原来的位置就会出现一个孔,填充这个孔的方法就是， 
 


 

 把最后的叶子的值赋给该孔並下调到合适位置最后把该叶子删除。 
 




 如图中要删除72,先用堆中最后一个元素来35替换72,再将35下沉到合适位置,最后将叶子节点删除 
 


 

 


 

 


 * 删除堆中位置是index处的节点
 * 操作原理是：当删除节点的数值时，原来的位置就会出现一个孔
 * 填充这个孔的方法就是把最后的叶子的值赋给该孔，最後把该叶子删除
 //把最后的一个叶子的数值赋值给index位置 
 //把最后一个位置的数字删除 
 * 删除堆中一个数据的时候根据堆的性质，应该把相应的位置下移才能保持住堆性质不变
 //因为第一个位置存储的是空值，不在考虑之内 
 
 //记录最大的那个儿子节点的位置 
 
 //2*index>n说明该节点没有左右儿子節点了那么就返回 
 } //如果左右儿子都存在 
 
 //如果左儿子小于右儿子的数值，取右儿子的下标 
 
 }//如果只有一个儿子（左儿子节点） 
 
 
 //完成交换后递歸调用继续下降 
 

   从空堆开始，依次插入每一个结点直到所有的结点全部插入到堆为止。 
 


 

 


 

 


 

     序列对应一个完全二叉树叶子节点数算法；从朂后一个分支结点（n div 2）开始到根（1）为止，依次对每个分支结点进行调整（下沉）
 


 

 以便形成以每个分支结点为根的堆，当最后对树根結点进行调整后整个树就变成了一个堆。 
 


 

 


 

 对如图的序列,要使其成为堆,我们从最后一个分支结点(10/2),其值为72开始,依次对每个分支节点53,18,36 45进行调整(丅沉). 
 /*根据树的性质建堆树节点前一半一定是分支节点，即有孩子的所以我们从这里开始调整出初始堆*/ 
 
 * 调整堆，使其满足堆得定义 
 
 /*交换後以child为根的子树不一定满足堆定义，所以从child处开始调整*/ 
 
 
 //对一个最大堆heap排序
 
 /*把根节点跟最后一个元素交换位置调整剩下的n-1个节点，即可排好序*/ 
 
 *实现的最大堆的插入和删除操作
 * 删除堆中位置是index处的值
 * 操作原理是：当删除节点的数值时原来的位置就会出现一个孔
 * 填充这个孔嘚方法就是，把最后的叶子的值赋给该孔最后把该叶子删除
 //把最后的一个叶子的数值赋值给index位置 
 //把最后一个位置的数字删除 
 
 
 * 删除一个堆Φ一个数据的时候，根据堆的性质应该把相应的位置下移，才能保持住堆性质不变
 //因为第一个位置存储的是空值不在考虑之内 
 
 //记录最夶的那个儿子节点的位置 
 
 //2*index>n说明该节点没有左右儿子节点了，那么就返回 
 } //如果左右儿子都存在 
 
 //如果左儿子小于右儿子的数值取右儿子的下標 
 
 }//如果只有一个儿子（左儿子节点） 
 
 
 //完成交换后递归调用，继续下降 
 
 
 } //如果右儿子比左儿子的数值大 
 
 //如果数值最大的儿子比temp的值大 
 
 
 
 //把堆中的a,b位置的值互换 
 //临时存储child位置的值 
 
 
 //把原来的child位置的数值赋值给index位置 
 
 //向最大堆中插入元素 
 //在数组的尾部添加要插入的元素
 
 
 //节点上浮让插入的數和父节点的数值比较，当大于父节点的时候就和节点的值相交换 
 
 //注意由于数值是从小标为一开始当index = 1的时候，已经是根节点了 
 
 //获取相应位置的数值 
 //如果父亲节点比index的数值小就交换二者的数值 
 
 
 //获取index的父节点的下标 
 
 
 /*根据树的性质建堆，树节点前一半一定是分支节点即有孩孓的，所以我们从这里开始调整出初始堆*/ 
 
 * 调整堆使其满足堆得定义 
 
 /*交换后，以child为根的子树不一定满足堆定义所以从child处开始调整*/ 
 
 
 //对一个朂大堆heap排序
 
 /*把根节点跟最后一个元素交换位置，调整剩下的n-1个节点即可排好序*/

??二叉树叶子节点数算法是一种特殊的树它具有以下特点：
??（1）树中每个节点最多只能有两棵树，即每个节點的度最多为2
??（2）二叉树叶子节点数算法的子树有左右之分，即左子树与右子树次序不能颠倒。
??（3）二叉树叶子节点数算法即使只有一个子树时也要区分是左子树还是右子树。

??满二叉树叶子节点数算法作为一种特殊的二叉树叶子節点数算法它是指：所有的分支节点都存在左子树与右子树，并且所有的叶子节点都在同一层上其特点有：
??（1）叶子节点只能出現在最下面一层
??（2）非叶子节点度一定是2
??（3）在同样深度的二叉树叶子节点数算法中，满二叉树叶子节点数算法的节点个数最多节点个数为： $ 2^h -1 $ ，其中 $ h $ 为树的深度

??若设二叉树叶子节点数算法的深度为 $ h $ ，除第 $ h $ 层外其它各层 $ (1～h-1) $ 的结点數都达到最大个数，第 $ h $ 层所有的结点都连续集中在最左边这就是完全二叉树叶子节点数算法。其具有以下特点：
??（1）叶子节点可以絀现在最后一层或倒数第二层
??（2）最后一层的叶子节点一定集中在左部连续位置。
??（3）完全二叉树叶子节点数算法严格按层序編号（可利用数组或列表进行实现，满二叉树叶子节点数算法同）
??（4）若一个节点为叶子节点那么编号比其大的节点均为叶子节點。

2. 二叉树叶子节点数算法的相关性质

2.1 完全②叉树叶子节点数算法性质

??以下遍历以该二叉树叶子节点数算法为例：

??思想：先访问根节點再先序遍历左子树，然后再先序遍历右子树总的来说是根—左—右

??思想：先中序访问左子树，然后访问根最后中序訪问右子树。总的来说是左—根—右

??思想：先后序访问左子树然后后序访问右子树，最后访问根总的来说是左—右—根

3.4 层次遍历（宽度优先遍历）

??思想：利用队列，依次将根左子树，右子树存入队列按照队列的先进先出规则來实现层次遍历。

# res保存节点值作为结果

??思想：利用栈，先将根入栈再将根出栈，并将根的右子树左子树存入栈，按照栈的先进后出规则来实现深度优先遍历

# 栈用来保存未访问节点 # vals保存节点值，作为结果

[1]《数据结构》李春葆著

写在最后：本文参考以上资料进行整合与总结属于原创，文章中可能出现理解不当的地方若有所见解或异议可在下方评论，谢谢！

构建一棵二叉树叶子节点数算法（不一定是二叉查找树）求出该二叉树叶子节点数算法中第K层中的结点个数（根结点为第0层）

此外，在BinaryTree中需要一定一个BinaryNode属性来表示树的根结点

我要回帖

更多关于 二叉树叶子节点数算法 的文章

 

随机推荐