二叉树及其应用（增删改查）

一、树的概念

树(tree)是n（n>0）个结点的有限集.在任何一个非空树中

        1）有且仅有一个特定的称为根的结点

        2）当n>1时，其余结点可分为m个互不相交的有限集T1、T2,,,Tm

        其中每个集合本身也是一颗树，叫根的子树

树的结点包含一个数据元素以及若干个指向其子树的分支

结点的度：结点拥有的子树的数量，称之为结点的度。度为0的结点称之为叶子结点或者终端结点。

度不为0的结点，称之为分支结点或者非终端结点

结点的层次：从根开始定义起，根为第一层，根的孩子为第二层，树中结点的最大层次叫树的深度或者高度

二、二叉树

二叉树是一种树状结构，它的特点是每个结点最多只有两颗子树，也就是二叉树不存在度大于2的结点。

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

二叉树的五种形态

1、空二叉树（一个结点都没有的二叉树）

2、只有一个根结点的二叉树

3、只有左子树

4、只有右子树

5、完全二叉树

 

三、二叉树的性质

1、在二叉树的第i层上至多有2^(i-1)个结点（i>=1）

2、深度为K的二叉树最多有(2^k)-1个结点

3、对于任意一颗二叉树，如果其终端节点数为n0，度为2的结点为n2，则有n2=n0-1

        1)满二叉树：一颗深度为K且具有(2^K)-1个结点的二叉树，满二叉树

        2)完全二叉树：满足以下条件的二叉树

                a:除去最后一层为满二叉树

                b：最后一层的结点必须依次从左往右紧密排列

练习：结点数699的完全二叉树的叶子结点（终端结点）的数量为多少？

2^9-1=511

699-511=188

K=9+1=10层