数据结构 | 树对应二叉树中无右孩子结点个数
已知一棵有n个节点的树,其叶子节点个数为x,求该树对应二叉树中无右孩子结点个数
Ans:n-x+1 即 分支结点数+1
证明:
n个节点的树,有n-1个边
由于叶子节点个数为x,此树有n-x个非叶结点
每个非叶结点有且仅有一个长子,对应二叉树有n-x左向边
右向边 = 总边数 - 左向边 = (n-1) - (n-x) = x-1
总共有n个点,其中只有x-1个点有右孩子,剩下的n-x+1个点没有右孩子(即证)
形象理解:
对于森林中的所有分支结点(分支结点就是非叶子结点,包含了根节点):
其所有孩子都会连到它对应二叉树的左子树中,最左边的孩子成为这棵左子树的根节点,最右边的孩子由于没有兄弟了,转为二叉树后,它的右孩子一定为空。
也就是说,对于森林中的每个分支结点,都存在它的1个孩子结点,转换为二叉树后右孩子为空,设森林有n个分支结点,故有n个对应的无右孩子的结点。
再来看二叉树的根节点(见下图中的B结点):
它作为分支结点,提供了一个无右孩子的结点(见下图B的黑色箭头);
作为根结点本身,在森林中的最右兄弟(见下图中的D结点)转为二叉树后也是没有右孩子的(见下图B的红色箭头),因此根节点总共提供了2个无右孩子的结点。
因此,森林转二叉树,无右孩子的结点由两部分提供:
每个分支结点提供一个+根节点额外提供一个,总共有n+1个结点无右孩子。树可以看做只有1棵树的森林,也能得到同样的结论。
一图胜千言,看这张图应该会容易理解一些,黑色箭头指向作为分支结点提供的无右孩子的结点,红色表示根结点作为其本身提供的无右孩子的结点
参考来源
森林转二叉树,二叉树无右孩子结点的个数_一头小学牲的博客-CSDN博客_二叉树中无右孩子的结点个数
已知一棵有n个节点的树,其叶子节点个数为x,求该树对应二叉树中无右孩子结点个数_weixin_47560863的博客-CSDN博客
相关文章
- 数据结构与算法(周鹏-未出版)-第六章 树-6.3 二叉树基本操作的实现
- [ 数据结构--C语言 ]不收藏必后悔系列--二叉树初阶
- Morris遍历判断二叉树是否为搜索二叉树
- 【Leetcode】297. 二叉树的序列化与反序列化 (困难)
- 将顺序结构打印成完全二叉树
- 《剑指offer》之从上到下打印二叉树Ⅰ、Ⅱ、Ⅲ
- 二叉树的层序遍历-Python
- 求解二叉树的最短深度-Python
- 【数据结构】二叉树知识点详解
- [数据结构][树]链表模拟二叉树及其基本操作
- 剑指 Offer 28. 对称的二叉树
- 数据结构 | 【树与二叉树】考研相关结论与习题
- 《剑指offer》--二维数组中的查找、从头到尾打印链表、重建二叉树、旋转数组的最小数字
- LeetCode426之公共祖先(相关话题:二叉树后序,Set和Map的应用)
- 【数据结构/二叉树】leetcode刷题路线(持续更新)
- 【数据结构/二叉树/二叉搜索树属性】题解+详细备注(共5题)
- 试题 G: 完全二叉树的权值
- 数据结构之---C语言实现线索二叉树
- 《数据结构》树和二叉树代码整理(C语言实现)
- 数据结构——二叉树的遍历
- 【leetcode】98:验证是否是二叉树
- [LeetCode] 1339. Maximum Product of Splitted Binary Tree 分裂二叉树的最大乘积
- [LeetCode] 971. Flip Binary Tree To Match Preorder Traversal 翻转二叉树以匹配先序遍历
- [LeetCode] Invert Binary Tree 翻转二叉树
- [LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二
- [LeetCode] 111. Minimum Depth of Binary Tree 二叉树的最小深度
- 数据结构:树的概念以及二叉树的实现
- LeetCode二叉树路径总和
- 26数据结构与算法分析之---线索二叉树