【手撕数据结构】二叉树的性质
目录
- 叶子节点和边的性质
- 概念
- 小试牛刀
叶子节点和边的性质
概念
- 可以看到度为0的节点如F没有边，度为1的节点如C有一条边，而度为2的节点如B有两条边。
- 那么设度为2的节点为a个，度为1的节点为b个。二叉树边 = 2a+b
- 另⼀⽅⾯，由于共有 a+b+c 个节点，所以边数等于 a+b+c-1
- 这里-1是因为：
- 综合上面两个公式，我们2a+b = a + b + c - 1; 推出c = a+1(c为度为0节点，a为度为2节点)
- 所以叶子结点n0 = n2 + 1;
小试牛刀
- 这道题已经告诉了我们度为2的节点个数，那么是不是直接可以用上面的公式n0 = n2 + 1.
- 故答案为B
- 节点个数n0+n1+n2,所以2n = n0+n1+n2 ,n0 = n2 + 1, 带入有：2n0+n1-1 = 2n
- 在完全二叉树中，因为完全二叉树是从左到右依次存储，n1要么为0,要么为1
- n1 = 1时，n0 = n, n1 = 0时 , n0为分数。
- 选A
- 一颗完全二叉树的最大节点树为2^h - 1.
- 一颗完全二叉树的第h层最大节点个数为2^(h-1)
- 此时完全二叉树节点个树为531,2^10 = 1024
- 在h层，就要符合小于等于h层的最大节点个数。