1.树的基础知识概述

树状图是一种数据结构，它是由 n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；

专业术语	中 文	描 述
Root	根节点	一棵树的顶点
Child	孩子节点	一个结点含有的子树的根结点称为该结点的子结点
Leaf	叶子节点	没有孩子的节点（度为0）
Degree	度	一个节点包含的子树的数量
Edge	边	一个节点与另外一个节点的连接
Depth	深度	根节点到这个节点经过的边的数量
Height	节点高度	从当前节点到叶子节点形成路径中边的数量
Level	层级	节点到根节点最长路径的边的总和
Path	路径	一个节点和另一个节点之间经过的边和 Node 的序列

 

 

 

 

 

2.二叉树

2.1二叉树的基本概念

二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两个互不相交的、分别称为根结点左子树和右子树的二叉树组成。

二叉树是一个每个结点最多只能有两个分支的树，左边的分支称之为左子树，右边的分支称之为右子树。

（1）在风控二叉树，第i-1层的结点总数不超过，i>=1；
（2）深度为h-1的二叉树最多有-1个结点（h>=1），最少有h个结点
（3）对于任意一棵二叉树，如果叶节点为N0，而度数为2 的结点总数为N2，则N0=N2+1；
　　 每个度为1的结点有1条边，度为2的结点有两条边。所以总边数为1*n1+2*n2，总边数等于结点数减1，即  N-1 = 1*n1+2*n2。其中总结点数又等于度为1、度为2、度为0的结点数和，即 N = n1 + n2 + n0；联立可得N0=N2+1。

2.2二叉树的特点

1.每个结点最多有两个子树，所以二叉树中不存在度大于2的结点。
2.左子树和右子树是有顺序的，次序不能颠倒。即使树中只有一颗子树，也要区分是左子树还是右子树。

2.3二叉树的五种形态

1.空二叉树。
2.只有一个根结点。
3.根结点只有左子树。
4.根结点只有右子树。
5.根结点既有左子树，又有右子树。

2.4特殊二叉树

1）完全二叉树 ——若设二叉树的高度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子节点，并且叶子结点都是从左到右依次排布，这就是完全二叉树（堆就是完全二叉树）。

　　

2）满二叉树 ——除了叶结点外每一个结点都有左右子节点且叶子结点都处在最底层的二叉树。

　　

3）平衡二叉树 ——又被称为 AVL 树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

　　

4）二叉搜索树 ——又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一颗空树或是满足下列性质的二叉树：（右边>=根>=左边）
        1）若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值；
        2）若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
        3）左、右子树也分别为二叉排序树。

　　

5）红黑树 ——是每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质：
        1）节点是红色或黑色；
        2）根节点是黑色；
        3）所有叶子节点都是黑色；
        4）每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个
                连续为红色的结点）；
        5）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 （没有度为
                1的结点）。
        以上规则可以保证左右子树结点数差距不超过两倍~

　　

 

 

 2.5二叉树的性质

1.在二叉树的第i层上最多有2i-1个结点(i≥1)。
2.深度为k的二叉树最多有2k-1个结点(k≥1)。
3.对于任何一个二叉树，如果其叶子结点数为n0，度数为2的结点数为n2，那么n0=n2+1，也就是叶子结点数为度为2的结点数加1。
4.具有n个结点的完全二叉树深度为(log2n)+1。
5.对具有n个结点的完全二叉树，如果按照从上至下和从左至右的顺序对二叉树的所有结点从1开始编号，则对于任意的序号为i的结点有:
A. 如果i>1，那么序号为i的结点的双亲结点序号为i/2;
B. 如果i=1，那么序号为i的结点为根节点，无双亲结点;
C. 如果2i<=n，那么序号为i的结点的左孩子结点序号为2i;
D. 如果2i>n，那么序号为i的结点无左孩子;
E. 如果2i+1<=n，那么序号为i的结点右孩子序号为2i+1;
F. 如果2i+1>n，那么序号为i的结点无右孩子。

3.二叉搜索树的算法实现

比如有以下数据：

 

当我们想保证查找效率时，可以用顺序表存储，当我们想保证插入和删除效率时，我们可以用链式表存储，有没有一种存储方法可以同时兼顾顺序表和链式表的优点？

使用二叉树，便可兼顾查找效率和插入删除效率~

 

 

 

 

二叉树一般采用链式存储方式：每个结点包含两个指针域，指向两个孩子结点，还包含一个数据域，存储结点信息。

 

 

 

 

结点结构体定义：

typedef struct _BNode {
    int data;
    struct _BNode *lchild, *rchild;
}Bnode,*Btree;

3.1二叉搜索树插入结点

 
//二叉树插入结点
/*将插入结点e，与结点root结点进行比较，若小于则去到左子树，否则
去右子树进行比较，重复以上操作直到找到一个空位置放置该结点
*/
bool InsertBtree(Btree* root, Bnode* node) {
    Bnode* temp = NULL;
    Bnode* parent = NULL;
    if (!node) {            //如果插入结点为空，返回false
        return false;
    }else {                    //清空插入结点的左右子树
        node->lchild = NULL;
        node->rchild = NULL;
    }
 
    if (!(*root)) {            //如果根节点不存在，将插入结点作为根节点
        *root = node;
        return true;
    }else {                    
        temp = *root;
    }
 
    while (temp != NULL) {
        parent = temp;
        if (temp->data>node->data) {    //小于，继续向左
            temp = temp->lchild;
        }
        else {                            //大于，继续向右（不可以有相同的值）
            temp=temp->rchild;
        }  
        //while循环结束，pare