什么是二叉树？

本文转载自：https://blog.csdn.net/xiaoquantouer/article/details/65631708
并对部分内容做了优化修改。

二叉树？

二叉树是树的一种，树是一种数据结构，由n（n>=1）个有限节点组成一个具有层次关系的集合。
先看一下什么是树。

什么是树？

树具有的特点有：

（1）每个节点有零个或多个子节点

（2）没有父节点的节点称为根节点

（3）每一个非根节点有且只有一个父节点

（4）除了根节点外，每个子节点可以分为多个不相交的子树。

1，如图，B有一个子节点D，C有两个子节点E和F，D没有子节点。
2，A没有父节点，所以A是根节点
3，仔细观察可以看到，除了根节点的每个节点都有一个父节点
4，A节点的两个子节点B和C，分别都有子节点，这样就得到了一个或多个新的树，这样得出的树叫子树

树的术语：

• 若一个节点有子树，那么该节点称为子树根的“双亲”，子树的根称为该节点的“孩子”。有相同双亲的节点互为“兄弟”。

比如A节点有子树B和C，A就是B和C的双亲，B和C分别是A的孩子，B和C互为兄弟。

• 一个节点的所有子树上的任何节点都是该节点的后裔。

A的子树B上，B和D两个节点都是A节点的后裔。

• 从根节点到某个节点的路径上的所有节点都是该节点的祖先。

从根节点A到子节点F路径上的C节点是F节点的祖先。

• 节点的度：节点拥有的子树的数目

A节点拥有两个子树，A节点的度为2

• 叶子节点：度为0的节点

D，E，F节点的度为0

• 分支节点：度不为0的节点

B，C是分支节点

• 树的度：树中节点的最大的度

树A的度为2

• 层次：根节点的层次为1，其余节点的层次等于该节点的双亲节点的层次加1

B和C的层次为根节点A的层次1 + 1 = 2

• 树的高度：树中节点的最大层次

树A的高度为2

• 森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

抛开A，B和C就组成了森林

对树的基本概念有所了解后，看一下什么是二叉树。

什么是二叉树？

二叉树是每个节点最多有两个子树的树结构。
它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

二叉树的性质

• 性质1：二叉树第i层上的节点数目最多为2i-1(i>=1)
• 性质2：深度为k的二叉树至多有2k-1个节点（k>=1）
• 性质3：包含n个节点的二叉树的高度至少为(log2n)+1
• 性质4：在任意一棵二叉树中，若终端节点的个数为n0，度为2的节点数为n2，则n0=n2+1

满二叉树

定义：高度为h，并且由2h-1个节点组成的二叉树，称为满二叉树

完全二叉树

定义：一棵二叉树中，只有最下面两层节点的度可以小于2，并且最下层的叶节点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。

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

二叉查找树（二叉搜索树）

设x为二叉查找树中的一个节点，x节点包含关键字key，节点x的key值计为key[x]。
如果y是x的左子树中的一个节点，则key[y]<=key[x]；如果y是x的右子树的一个节点，则key[y]>=key[x]
在二叉查找树中：

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值。
• 任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。
• 任意节点的左、右子树也分别为二叉查找树。
• 没有键值相等的节点。