二叉排序树的创建删除中序输出&&平衡树

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef struct Node{

    Node *l, *r;

    int v;

    Node(){l = NULL; r = NULL;}

}*tree, Node;

tree build(tree p, int v){

    if(p == NULL){

        p = new Node();

        p->v = v;

        return p;

    }

    if(v < p->v)

        p->l = build(p->l, v);

    else if(v > p->v)

        p->r = build(p->r, v);

    else

        return p;

    return p;

}

void Delete(tree &T, int k){

    Node *p = T;

    Node *q, *s, *f;

    f = NULL;

    while(p){

        if(p->v == k){

            break;

        }

        f = p;

        if(k < p->v){

            p = p->l;

        }

        else{

            p = p->r;

        }

    }

    q = p;

    if(!p)return;

    if(p->l && p->r){

        p = p->l;

        while(p->r){

            s = p;

            p = p->r;

        }

        q->v = p->v;

        s->r = p->l;

        delete(p);

        return;

    }

    else if(p->l){

        q = p; p = p->l;

    }

    else{

        q = p; p = p->r;

    }

    //cout << "*" << endl;

    if(!f)T = p;

    else if(q == f->l)f->l = p;

    else f->r = p;

    delete(q);

}

void InOrder(tree p){

    if(p == NULL)return;

    InOrder(p->l);

    printf("%d ", p->v);

    InOrder(p->r);

}

int main(){

    int N;

    while(~scanf("%d", &N)){

        tree p;

        p = NULL;

        int v;

        for(int i = ; i < N; i++){

            scanf("%d", &v);

            p = build(p, v);

        }

        InOrder(p);

        int m;

        scanf("%d", &m);

        for(int i = ; i < m; i++){

            scanf("%d", &v);

            Delete(p, v);

            InOrder(p);

        }

    }

    return ;

}

1）对α的左儿子的左子树进行一次插入（左旋）

其中D是新插入的节点，红色节点K2是失去平衡的节点。需要对K1和K2进行左旋调整即将K1作为根，将K2作为K1的左子树，K1的右子树调整为K2的左子树。如下图所示

进行左旋变换

2）对α的右儿子的右子树进行一次插入（右旋）

将K2的右子树更改为K1的左子树，K1的左子树更改为K2即完成的右旋，如下图所示

进行右旋

3）对α的左儿子的右子树进行一次插入（左右双旋）

左右双旋这里的左右指的是对α的左儿子的右子树进行插入时需要旋转。先对K1和K2进行右旋（跟第四种情况类似），然后再对K3和K2进行左旋，最终实现平衡。如下图所示

进行一次右旋进行一次左旋

4）对α的右儿子的左子树进行一次插入（右左双旋）

右左双旋：先对K1和K2进行左旋，然后在对K2和K3进行右旋，最终实现平衡。如下图所示

进行一次左旋进行一次右旋

平衡树：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

struct TreeNode{

  int v;

  int H;

  struct TreeNode *l;

  struct TreeNode *r;     

};

typedef struct TreeNode *AvlTree, *Position;

AvlTree FreeTree(AvlTree T){

        if(T != NULL){

             FreeTree(T->l);

             FreeTree(T->r);

             delete(T);

        }

        return NULL;

}

int Height(Position p){

    if(p == NULL)

        return -;

    return p->H;

 }

void pushup(Position &K){

    K->H = max(Height(K->l), Height(K->r)) + ;

}

Position SingleRotateWithLeft(Position K2){

    Position K1 = K2->l;

    K2->l = K1->r;

    K1->r = K2;

    pushup(K1);

    pushup(K2);

    return K1;

}

Position SingleRotateWithRight(Position K2){

    Position K1 = K2->r;

    K2->r = K1->l;

    K1->l = K2;

    pushup(K1);

    pushup(K2);

    return K1;

}

Position DoubleRotateWithLeft(Position K3){

    K3->l = SingleRotateWithRight(K3->l);

    K3 = SingleRotateWithLeft(K3);

}

Position DoubleRotateWithRight(Position K3){

    K3->r = SingleRotateWithLeft(K3->r);

    K3 = SingleRotateWithRight(K3);

}

AvlTree insert(int x, AvlTree T){

        if(T == NULL){

             T = new TreeNode();

             T->v = x;

             T->H = ;

             T->l = T->r = NULL;

        }

        else if(x < T->v){

             T->l = insert(x, T->l);

             if(Height(T->l) - Height(T->r) == ){

                 if(x < T->l->v)

                     T = SingleRotateWithLeft(T);

                 else

                     T = DoubleRotateWithLeft(T);

             }

        }

        else if(x > T->v){

             T->r = insert(x, T->r);

             if(Height(T->r) - Height(T->l) == ){

                 if(x > T->r->v)

                     T = SingleRotateWithRight(T);

                 else

                     T = DoubleRotateWithRight(T);

             }

        }

        pushup(T);

        return T;

}

AvlTree Visit(int X, AvlTree T){

    if(T == NULL)

        return NULL;

    if(X < T->v)

        return Visit(X, T->l);

    if(X > T->v)

        return Visit(X, T->r);

    return T;

}

void PreVisit(AvlTree T){

    if(T == NULL)

        return;

    printf("%d ", T->v);

    PreVisit(T->l);

    PreVisit(T->r);

}

void InVisit(AvlTree T){

    if(T == NULL)

        return;

    InVisit(T->l);

    printf("%d ", T->v);

    InVisit(T->r);

}

int main(){

    AvlTree T = FreeTree(NULL);

   // puts("**");

   int i;

    for(i = ; i <= ; i++)

        T = insert(i, T);

    for(i = ; i >= ; i--)

        T = insert(i, T);

    T = insert(, T);

    T = insert(, T);

    printf("InOrder:  ");

    InVisit(T);

    printf("\nPreOrder: ");

    PreVisit(T);

    putchar('\n');

    return ;

}

参考博客：http://blog.csdn.net/zitong_ccnu/article/details/11097663#

巴特西

二叉排序树的创建删除中序输出&&平衡树

最新文章

热门文章