二叉树 二叉树叶子结点计算方法

一、二叉树的作用

二叉树应用非常广泛。首先二叉树是树的基础，利用二叉树可以构造树和森林。在操作系统源程序中，树和森林被用来构造文件系统。我们看到的window和linux等文件管理系统都是树型结构。

在编译系统中，如C编译器源代码中，二叉树的中序遍历形式被用来存放C语言中的表达式。

在游戏设计领域，许多棋类游戏的步骤都是按树型结构编写。

其次二叉树本身的应用也非常多，如哈夫曼二叉树用于JPEG编解码系统（压缩与解压缩过程）的源代码中，甚至于编写处理器的指令也可以用二叉树构成变长指令系统，另外二叉排序树被用于数据的排序。总之，二叉树应用广泛，应好好掌握。

二、二叉树有几种不同的形态

二叉树有五种基本形态和两种特殊形态。

二叉树的五种基本形态：

1)空二叉树：空树；

2)只有一个根结点的二叉树：只有根的树，即单结点；

3)只有左子树：有根且有一个左子树；

4)只有右子树：有根且有一个右子树；

5)完全二叉树：有根且有一个左子树，有一个右子树。

特殊类型：

1、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

2、完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k，有n个结点的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。

三、二叉树树叶是什么意思

二叉树是一类非常重要的树形结构，它可以递归地定义如下：二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。

若用n,n1和n2分别表示T，u(1)和u(2)的结点数，则有n=1+n1+n2。u(1)和u(2)有时分别称为T的第一和第二子树。