一起学习交流~

二叉搜索树(排序树)

算法 laomuji 11个月前 (10-18) 654次浏览 已收录 0个评论

一、插入和深度遍历

数组优点,查找修改
链表优点,增加删除
树优点,综合效果最好
链表每个节点是存放下一个节点的地址
二叉树每个节点存放左孩子和右孩子,左边存比自己小的,右边存比自己大的
最好情况只需要链表一半的时间,最差情况和链表一样

/*
    假设有一个二叉树建立顺序为5 3 1 9 8 2 7 4 6
           5
       3      9
    1    4   8
     2      7
           6
*/

二叉树的开始节点叫做根节点,根节点为5

记录这个根节点,通过根节点来对整个二叉树进行操作

定义一个结构体作为节点

//节点
struct Node
{
    int val;//值
    struct Node* left;//左孩子
    struct Node* right;//右孩子
};

创建两个变量,存放节点个数和根节点

int size;//节点个数
Node* root;//根节点

初始化这个二叉树时,初始化这两个变量

    size = 0;
    root = nullptr;

要插入的值若小于当前节点,就往左循环,大于当前节点,就往右循环

//增加数据,成功返回1,失败返回0
int add(int value)
{
    //如果根节点为null表示没有根节点,将该节点设定为根节点
    if (root == nullptr)
    {
        root = new Node{ value,nullptr,nullptr };
        return 1;
    }
    //新节点
    Node *temp = new Node{ value,nullptr,nullptr };
    //当前节点,用于循环
    Node* current = root;
    //循环树
    while (1)
    {
        if (current->val > value)//当前值大于需要插入的值
        {

            if (current->left == nullptr) 
            {
                current->left = temp;
                break;
            }
            current = current->left;

        }
        else if (current->val < value)//当前值小于需要插入的值
        {
            if (current->right == nullptr)
            {
                current->right = temp;
                break;
            }
            current = current->right;
        }
        else
        {
            //如果值已经出现,就返回0表示插入失败
            //若要可以出现重复的值
            //需要将每个节点的值作为一个链表
            //而不是一个简单的变量
            return 0;
        }
    }
    //终止循环表示插入成功
    size++;
}

递归对二叉树进行先序,中序,后序遍历很简单.只是将打印换位置

二叉树的开始节点叫做根节点,根节点为5
二叉树深度遍历的三种方式
preorder先序,根->左->右:
5 3 1 2 4 9 8 7 6
inorder中序,左->根->右:
1 2 3 4 5 6 7 8 9
postorder后序,左->右->根:
2 1 4 3 6 7 8 9 5
中序遍历一定是有序的
//先序遍历,递归
    void preorder()
    {
        cout << "先序遍历(递归):";
        m_preorder(root);
        cout << endl;
    }
    void m_preorder(Node*node)
    {
        if (node == nullptr)return;
        cout << node->val << " ";
        m_preorder(node->left);
        m_preorder(node->right);
    }
    //中序遍历,递归
    void inorder()
    {
        cout << "中序遍历(递归):";
        m_inorder(root);
        cout << endl;
    }
    void m_inorder(Node* node)
    {
        if (node == nullptr)return;
        m_inorder(node->left);
        cout << node->val << " ";
        m_inorder(node->right);
    }
    //后序遍历,递归
    void postorder()
    {
        cout << "后序遍历(递归):";
        m_postorder(root);
        cout << endl;
    }
    void m_postorder(Node* node)
    {
        if (node == nullptr)return;
        m_postorder(node->left);
        m_postorder(node->right);
        cout << node->val << " ";
    }

二、查找和队列实现广度遍历

二叉树的查找思想类似于二分查找,往左往右就行,实现起来非常简单

   //在二叉树中查找数据,存在返回1,不存在返回0
    int isIn(int value)
    {
        Node* temp = root;
        while (temp!=nullptr)
        {
            if (temp->val < value)temp = temp->right;
            else if (temp->val > value)temp = temp->left;
            else return 1;
        }
        return 0;
    }
    //获取二叉树最大元素,获取成功返回1,失败返回0
    //获取成功则把value的值设定为max
    int getMax(int *value)
    {
        //如果根节点为null 那么就没有最大值
        if (root == nullptr)return 0;
        Node* temp = root;
        int max = 0;
        //因为右边是比当前节点大的,所以一直往右就是最大的
        while (temp->right!=nullptr)
        {
            temp = temp->right;
        }
        *value = temp->val;
        return 1;
    }
    //获取二叉树最小元素,获取成功返回1,失败返回0
    //获取成功则把value的值设定为min
    int getMin(int *value)
    {
        //如果根节点为null 那么就没有最小值
        if (root == nullptr)return 0;
        Node* temp = root;
        int max = 0;
        //因为左边是比当前节点小的,所以一直往左就是最小的
        while (temp->left != nullptr)
        {
            temp = temp->left;
        }
        *value = temp->val;
        return 1;
    }

接下来利用队列实现广度遍历

首先入队根节点

当队列不为空

循环出队,再把不为空的左右孩子放入队列

//广度遍历
vector<int>breadth()
{
    queue<Node*>queueNode;//用于存放节点
    vector<int>rVector;//用于返回先序遍历的数据
    if (root != nullptr)queueNode.push(root);//压入根节点
    //循环出队
    while (queueNode.size() > 0)
    {
        //先出队
        Node* temp = queueNode.front();
        queueNode.pop();
        rVector.push_back(temp->val);

        //把左孩子右孩子放入队列
        if (temp->left != nullptr)queueNode.push(temp->left);
        if (temp->right != nullptr)queueNode.push(temp->right);
    }
    return rVector;
}

三、栈实现深度遍历

用栈来实现稍微有点难理解

我画了两个图,看懂原理了应该就好写了

   //非递归实现先序遍历
    vector<int> preorderNoRecursion()
    {
        stack<Node*>stackNode;//用于存放节点
        Node* currentNode = root;//用于循环
        vector<int>rVector;//用于返回先序遍历的数据
        //currentNode用于向左遍历,stackNode用于出栈
        while (currentNode != nullptr || stackNode.size() > 0)
        {
            //向左
            while (currentNode != nullptr)
            {
                //将值压入返回的数组
                rVector.push_back(currentNode->val);
                //将节点压入
                stackNode.push(currentNode->right);
                //循环
                currentNode = currentNode->left;
            }

            //向右
            if (stackNode.size() > 0)
            {
                currentNode = stackNode.top();
                stackNode.pop();
            }
        }
        return rVector;
    }
    //非递归实现中序遍历
    vector<int> inorderNoRecursion()
    {
        stack<Node*>stackNode;//用于存放节点
        Node* currentNode = root;//用于循环
        vector<int>rVector;//用于返回先序遍历的数据
        //currentNode用于向左遍历,stackNode用于出栈
        while (currentNode != nullptr || stackNode.size() > 0)
        {
            while (currentNode != nullptr)
            {
                stackNode.push(currentNode);
                currentNode = currentNode->left;
            }
            if (stackNode.size() > 0)
            {
                Node* temp = stackNode.top();
                stackNode.pop();
                rVector.push_back(temp->val);
                currentNode = temp->right;
            }
        }
        return rVector;
    }
    //非递归实现后序遍历
    vector<int> postorderNoRecursion()
    {
        stack<Node*>stackNode;//用于存放节点
        Node* currentNode = root;//用于循环
        vector<int>rVector;//用于返回先序遍历的数据
        Node* lastNode = nullptr;//记录上次出栈的节点
        //currentNode用于向左遍历,stackNode用于出栈
        while (currentNode != nullptr || stackNode.size() > 0)
        {
            while (currentNode != nullptr)
            {
                stackNode.push(currentNode);
                if (currentNode->right != nullptr)stackNode.push(currentNode->right);
                currentNode = currentNode->left;
            }
            if (stackNode.size() > 0)
            {
                Node* temp = stackNode.top();
                stackNode.pop();
                if ((temp->left == nullptr && temp->right == nullptr) || (temp->left == lastNode || temp->right == lastNode))
                {
                    //两种情况出
                    //1.左边为空且右边为空,表示到了最下方
                    //2.上次出的是孩子节点,表示不需要循环
                    rVector.push_back(temp->val);
                }
                else
                {
                    //对数据进行循环
                    currentNode = temp;
                }
                //将上次节点设定为当前节点
                lastNode = temp;
            }
        }
        return rVector;
    }

后序遍历稍微有点难理解,有两种情况,自己多研究一下吧

四、删除节点(难点)

二叉树删除是难点,要考虑三种情况,还是先画图

   //获取节点最大的值
    Node* getMax(Node*node) {
        while (node->right!=nullptr)
        {
            node = node->right;
        }
        return node;
    }

    //二叉树删除,成功返回1
    int remove(int value)
    {
        int isDelete = 0;
        root = removeNode(value, root, isDelete);
        if (isDelete)size--;
        return isDelete;
    }
    struct Node* removeNode(int value, struct Node* node,int& isDelete)
    {
        if (node == nullptr)return node;
        if (isDelete == 1)return node;
        struct Node* rNode = node;
        //如果当前节点是需要删除的节点
        if (node->val == value)
        {
            //1.若要删除的是叶子节点
            if (node->left == nullptr && node->right == nullptr)
            {
                delete node;
                rNode = nullptr;
            }
            //2.若要删除的节点只有左孩子或右孩子
            //只有左孩子
            else if (node->left != nullptr && node->right == nullptr)
            {
                rNode = node->left;
                delete node;
            }
            //只有右孩子
            else if (node->left == nullptr && node->right != nullptr)
            {
                rNode = node->right;
                delete node;
            }
            //3.既有左孩子也有右孩子
            else if (node->left != nullptr && node->right != nullptr)
            {
                Node* leftMax = getMax(node->left);
                //现在 leftMax为左孩子中最大的
                //把leftMax复制到当前
                node->val = leftMax->val;

                //再把leftMax删掉即可
                node->left = removeNode(leftMax->val, node->left,isDelete);
                rNode = node;

            }
            isDelete = 1;
            return rNode;
        }
        //除了等于 那么就只有小于和大于了
        if (value < node->val) node->left = removeNode(value, node->left,isDelete);
        else node->right = removeNode(value, node->right, isDelete);
        return node;
    }

五、最小公共祖先

这个不怎么难,我使用了数组来解决,操作起来很容易

先上图

   //获取最小公共祖先,不存在返回0,存在返回1并赋值给ancestor
    int getLeastCommonAncestor(int value1, int value2,int* ancestor)
    {
        Node* rootNode;
        vector<Node*>vec1;//存rootNode到value1
        vector<Node*>vec2;//存rootNode到value2
        //对rootNode到value1的路径进行存储
        rootNode = root;
        while (rootNode != nullptr)
        {
            vec1.push_back(rootNode);
            if (rootNode->val < value1)rootNode = rootNode->right;
            else if (rootNode->val > value1)rootNode = rootNode->left;
            else break;//找到了就终止循环
        }
        //对rootNode到value2的路径进行存储
        rootNode = root;
        while (rootNode != nullptr)
        {
            vec2.push_back(rootNode);
            if (rootNode->val < value2)rootNode = rootNode->right;
            else if (rootNode->val > value2)rootNode = rootNode->left;
            else break;//找到了就终止循环
        }
        //因为最后一个相等的是公共祖先,所以从右边开始
        for (int i = vec1.size() - 1; i >= 0; i--)
        {
            for (int j = vec2.size() - 1; j >= 0; j--)
            {
                if (vec1[i] == vec2[j])
                {
                    *ancestor = vec1[i]->val;
                    return 1;
                }
            }
        }
        return 0;
    }
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论