数据结构与算法完全二叉树某题（适合刚学完二叉树的练手）

完全二叉树

文章目录

• 二叉树的性质
• 一、完全二叉树是什么？
• 二、某道例题
• • 1.题目描述
  • 2.解题思路
• 总结

---

二叉树的性质

性质1：二叉树的第i层上至多有2^(i-1)（i≥1） 个节点 。
性质2：深度为i的二叉树中至多含有2^i-1个节点 。
性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1 。
性质4：具有n个节点的满二叉树深为[log₂n]+1。
注：这里[log₂n]是对log₂n向下取整
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点 。
当i>1时，该节点的双亲节点的编号为i/2 。
若2i≤n，则有编号为2i的左节点，否则没有左节点 。
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点 。

---

一、完全二叉树是什么？

一棵深度为k的有n个结点的 二叉树 ，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与 满二叉树 中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

二、某道例题 1.题目描述

一棵完全二叉树上有1001个结点，其中叶结点的个数是（E）
A.250
B.500
C.254
D.505
E.以上答案都不对

2.解题思路

总结

不会多画图，多理解性质，不要光看。

纸上得来终觉浅，绝知此事要躬行。