文章目录
- 前言
- 💙二叉树的基本性质
- 🍒性质一
- 🍓性质二
- 🍇性质三
- 💖完全二叉树的基本性质
- 🍉性质四
- 🍊性质五
- 总结
提示:以下是本篇文章正文内容
💙二叉树的基本性质
🍒性质一
二叉树的第 i 层上最多有 2^(i-1) 个结点(i>=1)
🍓性质二
一颗深度为k的二叉树中,最多有(2^k) -1个结点,最少有k个结点
注:
深度为k且具有2^(k-1)个结点的二叉树一定是满二叉树,但是深度为k且具有k个结点的二叉树不一定是斜树
🍇性质三
在一颗二叉树中,如果有叶子结点数为n0,度为2的结点数位n2, 则有:n0 = n2 + 1
分支数n-1,逆向思考,从最底层向第一层看
💖完全二叉树的基本性质
🍉性质四
具有n个结点的完全二叉树的深度为╚ log2(n)╝+1
🍊性质五
对一棵具有n个结点的完全二叉树中从1开始按层序编号,则对于任意的序号为i( 1n,则结点i无左孩子,结点i为叶子结点
(3)如果2i+1≤n,则结点i的右孩子的序号为2i+1;如果2i+1>n,则结点i无右孩子
对一棵具有n个结点的完全二叉树中从1开始按层序编号,
(1)结点 i 的双亲结点为 i/2
(2)结点 i 的左孩子 为2i
(3)结点 i 的右孩子 为2i+1
在完全二叉树中,结点的层序编号反映了结点间的逻辑关系
关注
打赏
