空二叉树是什么

二又树是有限元素的集合，该集合或者为空，或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二又树为空二又树。在二又树中，一个元素也称作一个结点。

二又树是有限元素的集合，该集合或者为空，或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二又树为空二又树。在二又树中，一个元素也称作一个结点。

概念

二叉树是 n（n≥0）个结点的有限集合。n=0 的树称为空二叉树。n>0 的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。
显然，二叉树是一种有序树。二叉树中某个结点即使只有一个子树也要区分是左子树还是右子树。
二叉树中所有结点的形态共有 5 种：空结点、无左右子树结点、只有左子树结点、只有右子树结点和左右子树均存在的结点。

性质

性质 1：具有 n 个结点的非空二叉树有且仅有 n-1 个分支。
性质 2：非空二叉树的第 i 层最多有 2i-1 个结点。
性质 3：深度为 h 的非空二叉树最多有 2h-1 个结点。
性质 4：在任意非空二叉树中，若叶结点的数目为 n0，度为 2 的结点数目为 n2，则有关系 n0=n2+1 成立。
性质 5：具有 n（n>0）个结点的完全二又树的深度 h= log2n+1。

二叉树的基本运算

1、CreateBTree（bt，str）：已知二叉树的括号表示法表达字符串 str，建二叉树 bt。
2、BTHeight（bt）：求二叉树 bt 的高度。
3、NodeCount（bt）：求二叉树 bt 的结点个数。
4、LeafCount（bt）：求二叉树 bt 的叶子结点个数。

二叉树拓展

1、线索二叉树
按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有节点排列为一个线性序列。但是，二叉树中每个节点在这个序列中的直接前驱节点和直接后继节点在二叉树的存储结构中并没有反映出来，只有在对二叉树遍历的动态过程中才能够得到这些信息。线索二叉树就是研究在静态下，如何得到这样的信息。
2、二叉排序树
3、最优二叉树（哈夫曼树）
在权为 w1，w2，…，wn 的 n 个叶子所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为最优二叉树或 Huffman（赫夫曼）树。
4、平衡树
二叉平衡树（balanced binary tree）又称 AVL 树。它或者是一棵空二叉树，或者是具有下列性质的二叉树：
（1）它的左、右子树高度之差的绝对值不超过 1；
（2）它的左、右子树都是二叉平衡树。