二叉树-二叉搜索树的添加，删除和搜索

在计算机科学中，二叉树是每个节点最多具有两个子树的树结构. 通常，子树称为“左子树”（左子树）和“右子树”（右子树）. 二进制树通常用于实现二进制搜索树和二进制堆（二进制堆是完整的二进制树（二进制树）或近似完整的二进制树（二进制树）. 二进制堆有两种类型: 最大堆和最小堆）.

二叉树的每个节点最多具有两个子树（没有节点的度数大于2）. 二叉树的子树分为左和右，顺序不能颠倒. 二叉树的第i层最多具有2个^ {i-1}个节点；深度为k的二叉树最多具有2 ^ k-1个节点；对于任何二叉树T，如果终端节点数为n_0，则度为2的节点数为n_2，则n_0 = n_2 +1. 一棵深度为k且2 ^ k-1个节点的树称为a完整的二叉树；一棵深度为k和n个节点的树，当且仅当其每个节点位于深度为k的树中时，当序列号为1到n的节点相对应时，它们被称为完整二叉树.

完整的二叉树-如果二叉树的高度为h，则除第h层外，每层中的节点数（1〜h-1）达到最大值. 在第h层中有叶子节点，叶子的节点从左到右排列，这是一个完整的二叉树. 完整的二叉树-除叶节点外，每个节点都有左右子叶，叶节点位于二叉树的底部. 平衡二叉树平衡二叉树也称为AVL树（与AVL算法不同）. 它是一个二进制排序树，具有以下属性: 它是一个空树或左右子树之间的高度差绝对值不超过1，左右两个子树是平衡的二叉树.

二进制排序树也称为二进制搜索树，也称为二进制搜索树. 如下图所示

二进制排序树是具有以下属性的空树或二进制树:

如果左子树不为空，则左子树中所有节点的值小于其根节点的值;如果右子树不为空，则右子树中所有节点的值大于或等于其根节点的值;左和右子树也是二进制排序树；没有节点具有相等的键值.

二叉搜索树是满足以下条件的二叉树: 1.左子树上的所有节点值均小于根节点值，2右子树上的所有节点值均不小于根节点值小于根节点的值3，左，右子树该树也满足上述两个条件.

如果B树的所有非叶节点的左右子树的数量保持相同（平衡），则B树的搜索性能接近二元搜索；但是它比连续内存空间二进制搜索的优势在于，更改B树结构（插入和删除节点）不需要移动很大一部分内存数据，甚至不需要固定开销；

但是，在多次插入和删除之后，B树可能会导致不同的结构:

右侧也是B树，但是其搜索性能已经是线性的；相同的关键字集可能导致不同的树结构索引；因此二叉排序树查找算法，使用B树时还应考虑将B树保持尽可能远. 结构，避免右边的结构，这就是所谓的“平衡”问题；

实际的B树基于具有平衡算法的原始B树，即“平衡二叉树”；如何保持B树节点的均匀分布是平衡二叉树的关键. 平衡算法是一种在B树中插入和删除节点的策略；

如果二叉树的根节点的键值等于搜索到的键，则成功. 否则，如果它小于根节点的键值二叉排序树查找算法，则递归检查左子树. 如果它大于根节点的键值，则递归检查右子树. 如树为空，则搜索失败.

pnode search_BST(pnode p, int x)
{
    bool solve = false;
    while(p && !solve){
        if(x == p->val){
            solve = true;    
        }    
        else if(x < p->val){
            p = p->lchild;    
        }
        else{
            p = p->rchild;    
        }
    }
    if(p == NULL){
        cout << "没有找到" << x << endl;    
    } 
    return p;
}

如果当前的二进制搜索树为空，则插入的元素为根节点. 如果插入的元素值小于根节点值，则将元素插入到左子树中. 值，该元素将插入到右侧子树中.

struct node
{
    int val;
    pnode lchild;
    pnode rchild;
};
pnode BT = NULL;
//递归方法插入节点 
pnode insert(pnode root, int x)
{
    pnode p = (pnode)malloc(LEN);
    p->val = x;
    p->lchild = NULL;
    p->rchild = NULL;
    if(root == NULL){
        root = p;    
    }    
    else if(x < root->val){
        root->lchild = insert(root->lchild, x);    
    }
    else{
        root->rchild = insert(root->rchild, x);    
    }
    return root;
}
//非递归方法插入节点 
void insert_BST(pnode q, int x)
{
    pnode p = (pnode)malloc(LEN);
    p->val = x;
    p->lchild = NULL;
    p->rchild = NULL;
    if(q == NULL){
        BT = p;
        return ;    
    }        
    while(q->lchild != p && q->rchild != p){
        if(x < q->val){
            if(q->lchild){
                q = q->lchild;    
            }    
            else{
                q->lchild = p;
            }        
        }    
        else{
            if(q->rchild){
                q = q->rchild;    
            }    
            else{
                q->rchild = p;    
            }
        }
    }
    return;
}

有三种情况需要处理:

p是叶节点，直接删除该节点，然后修改其父节点的指针（请注意，存在根节点而不是根节点），如图a所示. p是单个分支节点（即，只有左或右子树）. 将p的子树连接到p的父节点并删除p； （请注意，存在根节点而不是根节点）；如图b所示. p的左右子树不为空. 找到p的后继y，因为y一定没有左子树，所以您可以删除y，并使y的父节点成为y的右子树的父节点，并用y的值替换p的值；或第二种方法是找到p x的前身x必须没有右子树，因此您可以删除x并将x的父节点设为y的左子树的父节点. 如图c.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-167956-1.html