数据结构--二叉树相关性质
1.性质
1.满二叉树每层节点个数：等比数列
3.（重要）任意二叉树：度为0（叶子节点）的比度为2的永远多一个。。度：就是看有多少孩子
如下图解析：（用推到归纳来分析）
2.前3条性质相关例题相关习题
2.用排除法：栈，堆，队列中循环队列适合。
A（不按照顺序）
3.(推导方法如下 )
假设度为0：N0
1:N1
2:N2
N0+N1+N2=2n(等于节点个数）
且根据性质：N0=N2+1
所以：N0+N1+N0-1=2n
完全二叉树，度为1的个数等于1或者0；
因为2n为偶数，因此左边一定也是偶数，所以只有当N1是1时满足，左边才是偶数
推出：N0=n.
相关题：一个具有767个节点的完全二叉树，其叶子节点个数为多少？
度为0：N0;
1:N1;
2:N2;
N0+N1+N2=767;
推出N1为0；
2N0-1=767
2N0=768
N0=384
4.一棵完全二叉树的节点树为531个，那么这棵树的高度为多少？
分析：
完全二叉树：
分别带入一定在两者中间，因此带入卡中间值即可。
5.通过前序和中序来推出树的后序等一系列内容。
如果选择可以用排除法
思路：
1.前序确定根
中序分割左右子树
得出1一定是树的根
2.前序下一个值就是左子树的根
所以2就是左子树的根
3.左子树前序走完开始看右子树，右子树的根就是4（还是通过前序确定根）
原文地址：https://blog.csdn.net/XSTIT/article/details/140298215
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！