二叉搜索树

╰+哭是因爲堅強的太久メ 2022-08-14 01:50 221阅读 0赞

搜索树数据结构支持许多动态集合操作，包括SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE等。因此，我们使用一棵搜索树既可以作为一个字典又可以作为一个优先队列。

//二叉排序树
    
    #include <iostream>
    #include <stdlib.h>
    
    using namespace std;
    
    typedef int KeyType;
    typedef struct _BSTNODE_
    {
       KeyType key;
       _BSTNODE_ * lChild;
       _BSTNODE_ * rChild;
    }BstNode;
    
    typedef BstNode * BSTree;
    
    void insertBST(BSTree *T, KeyType key)
    {
        BstNode *f, *p = *T;
        //指针类型做形参的时候，也会从内存中拷贝一份该形参的值，但不是一个地址，虽然在这里插入了树节点，但插入的位置
        //不是我们想要的位置，所以在遍历的时候会发现树为空，所以这里是BSTree *T，而不是BSTree T
        cout<<"插入函数中T的地址："<<T<<endl;
        while(p)
        {
            if(p->key == key)
            {
                return ;//树种存在该值，直接返回
            }
            else
            {
                f = p;
                p = (p->key > key) ? p->lChild : p->rChild;//如果当前输入的值小于节点值，就给p赋值为左孩子地址
            }
        }
        //到此为止已经确定要插入的节点位置了,目前确定的是父节点，他的左右孩子都为空，下面插入的时候还要判断
        //创建新节点
        p = (BstNode *)malloc(sizeof(BstNode));
        p->key = key;
        p->lChild = p->rChild = NULL; //创建完毕
    
        //判断根节点是否为空
        if(*T == NULL)
        {
            *T = p;//就把当前插入的当作根节点
        }
        else
        {
            if(f->key > key)
            {
                f->lChild = p;
            }
            else
            {
                f->rChild = p;
            }
        }
    }
    
    
    BSTree CreateBST()
    {
        BSTree T = NULL;
        cout<<"T的地址："<<&T<<endl;
        KeyType key;
        cin>>key;
        while(key)
        {
            insertBST(&T,key);
            cin>>key;
        }
    
        return T;
    }
    
    void midList(BSTree T)//中序遍历
    {
        if(T != NULL)
        {
            midList(T->lChild);
            cout<<T->key<<" ";
            midList(T->rChild);
        }
    }
    int main()
    {
        BSTree T = NULL;
        T = CreateBST();
        midList(T);
        return 0;
    }