《数据结构和算法》——线性查找和二叉排序树

luciferzf

线性索引查找：
当数据不是以顺序的方式存储时，我们无法对数据进行二分查找等高效的查找方式，所以我们采用了线性索引查找
1)稠密索引查找：对于数据量不是特别大的，我们可以对数据建立一个一一对应的索引表，我们多索引表进行排序后，我们就可以对索引表进行二分查找等较为高效的算法。
2)分块索引：将无序的数据分成多个小块，每个小块可以取一个特征量作为标志，如该块数据中的最大值，使块内数据无序，但是块间有序排列。我们可以对块进行高效查找，对块内进行顺序查找
3)倒排索引：将多个数据的关键字提取后，建立索引表，储存关键字出现的位置

二叉排序树：
对于乱序的数据，我们易于插入和删除，但是不易于查找，而二叉排序树则成功的做到了兼顾二者。我们首先选择一个根节点，创建时，我们使所有左子树上的节点小于根节点，使所有右子树上的节点大于根节点，即在储存数组时，把较根节点小的放在左子树上，较根节点大的放在右子树上。
1)查找：我们从根节点开始，不断地和目标数据进行比较，当节点数据小于目标数据时，再比较节点的右子树的数据和目标数据，反之则比较节点的左子树的数据和目标数据，直至找到或者节点的左子树或右子树为空，我们利用指针来储存位置，返回0和1来表示是否找到目标数据的位置
2)添加：从根节点开始，不断地将目标数据和节点数据进行比较，若目标数据较大，则移动指针至其右子树，反之则移动到其的左子树，直至节点左或右子树为空，将目标元素赋值到节点的左或右子树
3)删除：删除时除了被删除数据的删除，还需要将被删除节点的新数据进行补充；此时分为三个情况，当被删除节点为叶子时，直接删除该节点；当被删除节点只有左（右）子树时，将其左（右）子树连在该节点前驱；当被删除节点有左右子树时，我们用该节点的直接后继（左子树的最右边的叶子节点）去替换该节点，删除其直接后继。

附上二叉排序树的代码

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;

class node
{
public:
        int data;
        node *lchild = NULL, *rchild = NULL;
};
void Input(node *&r)
{
        int n;
        node *cp=NULL;
        cout << "input the numbers(end with -1):" << endl;
        cin >> n;
        while (n != -1)
        {
                if (r == NULL)
                {
                        r = new node;
                        cp = r;
                }
                else
                {
                        cp = r;
                        while (1)
                        {
                                if (n < cp->data)
                                {
                                        if (cp->lchild == NULL)
                                        {
                                                cp->lchild = new node;
                                                cp = cp->lchild;
                                                break;
                                        }
                                        cp = cp->lchild;
                                }
                                else
                                {
                                        if (cp->rchild == NULL)
                                        {
                                                cp->rchild = new node;
                                                cp = cp->rchild;
                                                break;
                                        }
                                        cp = cp->rchild;
                                }
                        }
                }
                cp->data = n;
                cin >> n;
        }
}

void AddNode(node *r)
{
        int key;
        cout << "input the number:";
        cin >> key;
        node *cp = r,*np=NULL;
        if (r == NULL)
        {
                cout << "wrong,no root" << endl;
        }
        while (1)
        {
                if (key >= cp->data)
                {
                        if (cp->rchild == NULL)
                        {
                                cp->rchild = new node;
                                cp->rchild->data = key;
                                return;
                        }
                        cp = cp->rchild;
                }
                else
                {
                        if (cp->lchild == NULL)
                        {
                                cp->lchild = new node;
                                cp->lchild->data = key;
                                return;
                        }
                        cp = cp->lchild;
                }
        }
        
        

}

void FindNode(node *r)
{
        int key;
        cout << "input the number:";
        cin >> key;
        node *cp = r;
        int flag = 0;
        while (cp != NULL)
        {
                if (cp->data == key)
                {
                        flag = 1;
                        break;
                }
                if (key < cp->data)
                {
                        cp = cp->lchild;
                }
                else
                {
                        cp = cp->rchild;
                }
        }
        if (!flag)
        {
                cout << "No such number" << endl;
        }
        else
        {
                cout << "YES" << endl;
        }
}

void DeleteNode2(node *p,node *pp,int dir)
{
        node *cp = p;

        if (cp->lchild == NULL)
        {
                if (dir)
                {
                        pp->rchild = cp->rchild;
                }
                else
                {
                        pp->lchild = cp->rchild;
                }
        }
    else if (cp->rchild == NULL)
        {
                if (dir)
                {
                        pp->rchild = cp->lchild;
                }
                else
                {
                        pp->lchild = cp->lchild;
                }
        }
        else
        {
                pp = cp;
                cp = cp->lchild;
                while (cp->rchild != NULL)
                {
                        pp = cp;
                        cp = cp->rchild;
                }
                node *d = NULL;
                p->data = cp->data;
                if (pp != p)
                {
                        pp->rchild = cp->lchild;
                        d = cp;
                }
                else
                {
                        pp->lchild = NULL;
                        d = cp;
                }

                delete d;
                
        }

}

void DeleteNode1(node *r)
{
        node *cp = r,*pp=r;
        int flag = 1,key;
        cout << "input the delete number:";
        cin >> key;
        int dir = 0;
        while (cp != NULL)
        {
                if (cp->data == key)
                {
                        DeleteNode2(cp,pp,dir);
                        break;
                }
                if (key < cp->data)
                {
                        dir = 0;
                        pp = cp;
                        cp = cp->lchild;
                }
                else
                {
                        dir = 1;
                        pp = cp;
                        cp = cp->rchild;
                }
        }
}

void print(node *cp)
{
        if (cp == NULL)
        {
                return;
        }
        cout << cp->data << " ";
        if (cp->lchild != NULL)
        {
                print(cp->lchild);
        }
        if (cp->rchild != NULL)
        {
                print(cp->rchild);
        }

}

int main()
{
        node *r=NULL,*cp=NULL;
        Input(r);//输入无序数据
        int choice = 1;
        cout << "1——>添加数据" << endl << "2——>删除数据" <<  endl << "3——>查找数据" <<endl<<"4——>打印数据表"<< endl;
        while (choice)
        {
                cout << "input your choice:";
                cin >> choice;
                switch (choice)
                {
                case 1:
                        AddNode(r);
                        break;
                case 2:
                        DeleteNode1(r);
                        break;
                case 3:
                        FindNode(r);
                        break;
                case 4:
                        cout << "the number is:";
                        print(r);
                        cout << endl;
                        break;
                case 0:
                        break;
                default:
                        cout << "Wrong Input!" << endl;
                        break;

                }
        }

        system("PAUSE");
}