算法学习之路|二叉查找树

好吧，要搞红黑树，还是从二叉树开始慢慢搞起吧！

1.初识二叉树

struct node{
    typename data;//数据域（下文用整型为例），当然如果数据不止一个的话，那就用结构体啦 
    node* lchild;//指向子树的指针
    node* rchlid; 
};

//2.建立根节点 

node* root =NULL;

//3.生成一个新的节点（往二叉树中插入的时候会用到，模块化编程啦）

node* newNode(int v){//v是插入的新节点的数据域，这里用int，也可能是结构体 
    node* Node=new node;
    Node->data=v;//节点的数据域为v 
    Node->lchild=Node->rchlid=NULL;//初始状态下的新节点没有左右孩子，对指针赋值为NULL 
    return Node; //返回新节点的地址 
} 

//4.二叉树的查找和数据域的修改

 void search(node* root,int x,int newdata){
     if(root=NULL){
         return ;//空树or子树为空（即递归边界） 
    }
    if(root->data==x){
        root->data=newdata;//找到数据域为x的结点，把它修改为newdata 
    }
    search(root->lchild,x,newdata);
    search(root->rchlid,x,newdata);
 }
 
 //5.二叉树的结点的插入
 
/*二叉树的插入位置和二叉树中的数据域的存放（即具体的二叉树的本身的性质，
 也就是具体问题） 有关，但一般插入位置只会有一个，否则问题本身就会出现
 不确定性，而插入位置就是数据域在二叉树中查找失败的位置。*/
void insert(node* &root,int x){//这里因为要把新结点接到二叉树上去（可以这么理解）
                            //即对二叉树的结构修改，所以要用引用&
    if(root==NULL){//空树，查找失败，也即是插入的位置（递归边界） 
        root=newNode(x);//newNode()函数，见上文
        return; 
    } 
    if(由于具体二叉树的性质，x应该插在左子树（这里用左子树为例）){
        insert(root->lchild,x);//往左子树搜索（递归式） 
    }
    else{
        insert(root->rchlid,x);
    } 
}

//6.二叉树的建立

node* Create(int data[],int n){
    node* root=NULL;//新建空跟节点root
    for(int i=0;i<n;i++){
        insert(root,data[i]);//将data[0]~data[n-1]插入二叉树中    
    }
    return root;//返回根结点 
} 

2.二叉树的遍历

 <li>无论哪一种遍历，左子树一定先于右子树.</li>
 <li>"先中后"是指根节点在遍历中的位置。比如：先序（也叫前序）遍历：<strong>根结点</strong>-&gt;左子树-&gt;右子树。</li>
 <li>所谓层次遍历，就是从上到下，从左往右一次访问（遍历）</li>

好了，直接看代码吧！

void preorder(node* root){
    if(root==NULL){
        return;//到达空树（递归边界）
    }
    //访问根结点root，例如将其数据域输出，当然啦，也可以是其他操作
    printf("%d\n",root->data);
    //访问左子树
    preorder(root->lchild);
    //访问右子树
    preorder（root->rchild);
}

//2.中序遍历
void inorder(node* root){
    if(root==NULL){
        return;//到达空树，递归边界
    }
    //访问左子树
    inorder(root->lchild);
    //访问根结点root，例如将其数据域输出
    printtf("%d\n",root->data);
    //访问右子树
    inorder(root->rchild);
}

//3.后序遍历
void postorder（node* root){
    if(root=NULL){
        return ;
    }
    postorder(root->lchild);
    postorder(root->rchild);
    printf("%d\n",root->data);
}

//4.层序遍历
struct node{
    int data;//数据域
    int  layer;//层次
    node* lchild;
    node* rchild;
};

void LayerOrder(node* root){
    queue<node*> q;//桥黑板！！队列里存放的是地址！
    root->layer=1;//根结点的层号为1
    q.push(root);//将根结点的地址入队
    while(!q.empty()){
        node* now=q.front()；//取出队首元素
        q.pop();
        printf("%d ",now->data);//访问队首元素
        if(now->lchild!=NULL){//如果左子树非空
            now->lchild->layer=now->layer+1;
            q.push(now->lchild);
        }
        if(now->rchild!=NULL){
            now->rchild->layer=now->layer+1;
            q.push(now-rlchild);
        }
    }
}

//question 1:已知二叉树的先序遍历和中序遍历，重建二叉树

//当前先序序列的区间为[preL,preR],中序序列区间为[inL,inR],返回根节点的地址
node* create(int preL,int preR,int inL,int inR){
    if(preL>preR){
        return NULL;//先序序列的长度小于等于0时，直接返回；
    }
    node* root=new node;//新建一个新的结点，用来存放当前二叉树的根结点
    root->data=pre[preL];//新结点的数据域为根结点的值（注意，pre的最左边就是根结点！）
    int k;
    for(k=inL;k<=inR;k++){
        if(in[k]==pre[preL]){//在中序序列中找到in[k]==pre[L]的结点
            break;
        }
    }
    int numLeft=k-inL;//左子树的节点个数
    //左子树的先序序列区间为[preL+1,preL+numLeft],中序区间为[inL,k-1];\
    //返回左子树的根结点地址，赋值给root的左指针
    root->lchild=create(preL+1,preL+numLeft,inL,k-1);

    //右子树的先序区间为[preL+numLeft+1,preR],中序区间为[k+1,inR]
    //返回右子树的根结点地址，赋值给root的右指针
    root->rchild=create(preL+numLeft+1,preR,k+1,inR);

    return root;//注意，一定要返回根结点地址
}

看完代码，这里有几点要特别说明一下：

 <li>一个二叉树的先序遍历，序列的第一个一定是根结点。</li>
 <li>对于中序遍历的结果，假设为一个数组，只要知道根结点的位置，就可以通过根结点在中序遍历序列中的位置区分出做左子树和右子树。</li>
 <li>后序遍历的最后一个结点一定是根结点。</li>
 <li>无论是知道先序遍历还是知道后序遍历，都必须知道中序遍历才能唯一确定一个树</li>
 <li>对于完全二叉树（简单说就是只有最下面一层结点缺少，而且从左往右连续存在结点），从上到下，从左到右从一开始进行顺序编号。任何一个节点（设编号为x)，其左孩子的编号一定是2x,右孩子的编号一定是2x+1。也就是说，可以建立一个大小为2的k次方的数组来储存信息（k为树的高度）。该数组的存放顺序恰好为层次遍历的顺序。桥黑板！！判断某个结点是否为叶结点的标志为：该结点（记下标为root)的左子结点的编号root*2是否大于总结点个数n。判断某个结点是否为空结点的标志为：该结点下标root大于结点总个数n。</li>

3.从二叉树的遍历迅速掌握树的遍历

//比如可以开一个指针数组来存放子结点的地址。不过这里推荐使用
//静态写法，也就是用数组下标来代替所谓的地址。
struct node {
    typename data;//数据域啦
    int child[maxn];//指针域，存放所有子节点的下标（也就是地址）
}Node[maxn];//结点数组，maxn为结点上限个数

//举例，新建结点
int index=0;//当前最多结点的个数，即位置
int newNode(int v){
    Node[index].data=v;//数据域为v;
    Node[index].child.chear();//清空子结点
    return index++;//返回结点的下标，并且令index自增
}
//小结：二叉树既然是树的特殊化，那也就意味着二叉树的性质和树非常相似。
//树不区分左右孩子，对树的遍历，循环一遍子结点child[]数组即可，是不是很简单！

4.平衡二叉查找树（AVL树）

AVL树是啥？怕你听不懂，我就用一句话解释下：

AVL树是一棵加了“平衡“（左子树和右子树的高度之差不超过1）插件的二叉查找树（BST,Binary Searcch Tree）。

二叉查找树是啥？也怕你听不懂，就用一句话概括下：

BST树上每一个节点的左子节点的数据域小于或等于其数据域，右子节点的数据域大于其数据域。

好了，介绍完了！直接上代码：

 1、左子树和右子树的高度之差称为平衡因子
 2、只要能随时保持每个结点的高度不超过1，AVL树的高度就能始终保持O(logn)级别
 3、由于到得到每个结点的平衡因子，因此需要在树的结构中加入height变量用来记录
 以当前结点为根结点的子树的高度
 */
 struct node{
     int v,height;//v为结点的权值，height为当前子树的高度
     node *lchild,*rchild;//左右孩子结点的地址
 };

//生成一个新的权值为v的结点
node* newNode(int v){
    node* Node=new node;//申请一个node型变量的地址空间
    Node->v=v;
    Node->height=1;//结点的初始高度因为只有它自己一个结点，所以为1
    Node->lchild=Node->rchild=NULL;//初始状态下左右孩子都为NULL
    return Node;//返回新的结点的地址
}

//获取以root为根结点的子树的当前高度height
//注：root结点是任意一个结点，仔细理解！
int getHeight(node* root){
    if(root==NULL)return 0;//空结点的高度为1,记住啊是空结点（NULL)！
    return root->height;
}

//计算结点root的平衡因子
int getBalanceFactor(node* root){
    //即左子树高度减右子树高度
    return getBalanceFactor(root->lchild)-getBalanceFactor(root->rchild);
}

/*注：为啥不直接记录结点的平衡因子，却记录高度，因为没有办法通过当前结点的子树的
平衡因子计算得到该结点的平衡因子，而要借助子树的高度间接求出。
显然的的是，结点root所在子树的height等于其左右子树height的较大值加1。*/

//更新结点root的height
void updateHeight(node* root)
{
     //max(左子树的height，右子树的height)+1（为啥要加一啊，艾玛，它(root)自己不算高度啊
     root->height=max(getBalanceFactor(root->lchild),getBalanceFactor(root->rchild))+1;
}

//好了，上面介绍了AVL树的基本概念了，下面来上基本操作和核心编程

//查找操作
//时间复杂度只有O(logn),因为树的高度控制在O(logn）级别了嘛！
void search(node* root,int x){//查找数据域为x的结点
    if(root==NULL){//空树，查找失败
    printf("search failed\n");
    return;
    }
    if(x==root->v){//查找成功，访问之（再次说明，访问就是对数据域操作，因题而异）
        printf("%d\n",root->v);
    }
    else if(x<root->v){//二叉查找树的性质，见上文！
    //如果x比根结点的数据域小，说明x在左子树
        search(root->lchild,x);
    }
    else {
        search(root->rchild,x);
    }
}

//左旋（Left Rotation)
//不知道是啥？百度去，这里只给代码！希望能看懂
void L(node* &root){//只要是涉及树结构的改变都要用引用！不理解，就记着！
    node* tem=root->rchild;//root指向结点A，tem指向结点B
    root->rchild=tem->lchild;
    tem->lchild=root;
    updateHeight(root);//更新结点root的高度
    updateHeight(tem);
    root=tem;
}
//右旋
void R(node* &root){
    node* tem=root->lchild;
    root->lchild=tem->rchild;
    tem->rchild=root;
    updateHeight(root);
    updateHeight(tem);
    root=tem;
}

/*AVL树的核心操作:现已经有一棵平衡二叉树，在往其中插入一个结点时，
一定会有结点的平衡因子发生变化，此时可能会有节点的平衡因子大1（但平
衡因子只可能是2或-2，为什么？一次插入一个，每次都及时调整啊！不懂找
块豆腐撞撞去！），也就是失衡啦！ 显然，只有在从根结点到该插入结点的
路径上才可能发生平衡因子变化，因此只需对这条路径上失衡的结点进行调整
。桥黑板！！只要把最靠近插入结点的失衡结点调整到正常，路径上所有节点
就都会平衡*/

//插入权值为v的结点
void insert(node* &root,int v){
    if(root==NULL){//到达空结点，也就是到达要插入的点
        root=newNode(v);
        return;
    }
    if(v<root->v){
        insert(root->lchild,v);
        updateHeight(root);//更新树高！
        if(getBalanceFactor(root)==2){
            if(getBalanceFactor(root->lchild)==1){
                R(root);
            }
            else if(getBalanceFactor(root->lchild)==-1){
                L(root->lchild);//把它变为上一种情况
                R(root);
            }
        }
    }
    else{
        insert(root->rchild,v);
        updateHeight(root);
        if(getBalanceFactor(root)==-2){
            if(getBalanceFactor(root->rchild)==-1){
                L(root);
            }
            else if(getBalanceFactor(root->rchild)==1){
                R(root->rchild);
                L(root);
            }
        }
    }
}

//终于到最后了
//AVL树的建立
node* Create(int data[],int n){
    node* root=NULL;//新建空根结点root
    for(int i=0;i<n;i++){
        insert(root,data[i]);//将data[0]~data[n-1]插入到AVL树中
    }
    return root;
}

5.红黑树~可怕！

目前就对红黑树理解到这里，至于代码。。