节点的度：一个节点所含有的子树的个数就是这个节点的度

树的度：一棵树中所有节点的度的最大值称为该树的度

叶子节点：度为0的结点称为叶子节点

父节点：一个节点含有子节点，那么这个节点就是子节点的父节点

根节点：没有双亲的节点称为根节点

节点的层次：根节点为第一层，根节点的子节点为第二层，以此类推

树的深度：树中节点的最大层次

二叉树

在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

注意：

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)

二叉树的子树有左右之分，次序不能颠倒

二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

二叉树的性质

二叉树有许多重要的性质，理解并记忆有助于我们做题

性质1：根节点的层数为1，二叉树第i层上的节点数目最多为2^（i-1）(i>=0)

性质2：根节点的二叉树的深度为1，深度为k的二叉树至多有（2^k）-1个节点（k>=0）

性质3：包含n个节点的二叉树的高度至少为(log2n)+1

性质4：在任意一棵二叉树中，若叶子节点的个数为n0，度为2的结点数为n2，则n0=n2+1

性质5：一棵树有N个节点，则有N-1条边

满二叉树

高度为h，并且由（2^h）-1个节点组成的二叉树，称为满二叉树

完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

性质4公式推导

假设任意一颗二叉树中有N个节点：

记度为0的节点为n0，度为1的节点为n1，度为2的节点为n2

则有：N = n0+n1+n2

由上图的二叉树我们可以看出，一个度为1 的节点能向下产生一条边，一个度为2的节点向下产生两条边，一个度为0的节点向下产生0条边，一棵树有N个节点，则有N-1条边

那么度为1 的节点能产生n1条边，度为2的节点能产生2*n2条边，度为0的节点产生0条边

则有：N-1 = n1+2*n2

另两式相等则有：

n0+n1+n2 = n1+2*n2+1

推出：n0=n2+1

经典题目

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（） A 不存在这样的二叉树 B 200 C 198 D 199

由性质4得出，n0=n2+1，二叉树度为2的节点有199个，叶子节点个数为200个，选B

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（） A n B n+1 C n-1 D n/2

性质4：在任意一棵二叉树中，若叶子节点的个数为n0，度为2的结点数为n2，则n0=n2+1

本题节点个数为2n，是偶数情况

那么2n = n0 + 1 + n2

又因为n0 = n2 +1

则有：2n - 1 = 2n0 - 1

n0 = n

选A

3.一个具有767个节点的完全二叉树，其叶子节点个数为（） A 383 B 384 C 385 D 386

性质4：在任意一棵二叉树中，若叶子节点的个数为n0，度为2的结点数为n2，则n0=n2+1

767节点总数为奇数，则n1为0

则有：767 = n0 + n2

由 n0 = n2 + 1

n0 = 768/2 = 384

选B

4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（） A 11 B 10 C 8 D 12 答案： 1.B 2.A 3.B 4.B

性质3：包含n个节点的二叉树的高度至少为(log2n)+1

2^9 = 512 < 53B

节点数为531，要向上取整

2^10 = 1024

选B

“ 本期的分享就到这里了，记得给博主一个三连哈，你的支持是我创作的最大动力！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/592542

Java数据结构——认识二叉树_java哪些数据结构用二叉树

树的概念

树型结构

二叉树