二叉树详解

哈喽，小伙伴们大家好，相信对数据结构有一定了解的小伙伴对树这个名字都不陌生。今天，我将为大家介绍以下什么是树，并主要介绍一种树中的特殊结构——二叉树。

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

它具有以下的特点：   

1.有一个特殊的结点，称为根结点，根结点没有前驱结点。（根节点：没有父节点的节点就称为这棵树的根节点，在一棵树中根节点有且只有一个。）

2.除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm（子树之间不能相交，若相交，不是树结构~），其中每一个集合Ti (1

若一个二叉树的节点个数为N，则该二叉树的高度为log2 (N+1)---向上取整。

eg：此时N = 13，二叉树的高度-log2 (13+1) ==>4

3.2.2 节点所在的层数为X，则该层最多有2^(X-1)个节点

eg：X == 3，第三层最多有4个节点 N == 2^(3-1) = 2^2 = 4。

3.2.3 在任意的一个二叉树中，度为2的节点N2和度为0的节点N0-------> N2 = N0 - 1

eg：在树中，节点的个数 = 边长 + 1。在二叉树中，N2+ N1+N0 = 2N2+N1+1==> N2 = N0 - 1

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（B）

A.不存在这样的二叉树 B.200 C.198 D.199

解析：N2 = N0 -1 ===》 N0 = N2 + 1 = 199 + 1 = 200

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（A）

A.n B.n+1 C.n-1 D.n/2

解析：N2 + N1 + N0 =  N0 - 1 + 1 + N0 = 2n ===》 N = n

在完全二叉树中，度为1的节点只可能是0或者1======只有一条边的节点只可能存在1个或者1个都不存在

记住结论：当完全二叉树是偶数个节点，则度为1的节点个数为1。当完全二叉树是奇数个节点，则不存在度为1的节点。

3.一个具有767个节点的完全二叉树，其叶子节点个数为（B）

A.383 B.384 C.385 D.386

解析：N2 + N1 + N0 = N0 - 1 + N0 = 767 = 》2N0 = 768 =》N0 = 384

4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（B）

A.11 B.10 C.8 D.12

解析：log2 (n + 1) = log2 532 =》 10