二叉查找树（BST）及二叉树的遍历

雨点打透心脏的1/2处 2021-11-05 04:02 381阅读 0赞

# 二叉查找树（BST）及二叉树的遍历 #

### **一、二叉查找树（BST）** ###

**1、二叉查找树的特征**

二叉查找树（BST）也称为二叉搜索树或二叉排序树。二叉查找树的节点包含键值key。二叉查找树或者是一棵空树，否则要求：

1. 若它的左子树不为空，那么左子树上所有节点的key都小于根节点的key。

2. 若它的右子树不为空，那么右子树上所有节点的key都大于根节点的key。

. 它的左右子树也分别为二叉排序树。   
![这里写图片描述][70]

**2、二叉查找树的建立、查找、插入和删除**

**1）递归建立二叉查找树**

btree creat_tree(btree root, int val)
    {
        if (root == nullptr)//如果为空的二叉树,便将新的节点设定为根节点
        {
            root = new Binary_tree;
            root->data = val;
            root->left = nullptr;
            root->right = nullptr;
        }
        else if (root->data < val)//如果新值比节点值大，递归地建立右子树
            root->right = creat_tree(root->right, val);
        else if (root->data > val)//如果新值比节点值小，递归地建立左子树
            root->left = creat_tree(root->left, val);
        else
            exit(-1);
        return root;
    }

**（2）查找节点**

btree search_tree(btree ptr, int val)
    {
        while(1)
        {
            if(ptr == nullptr)//没找到就返回NULL
                return nullptr;
            if(ptr->data == val)//节点值等于查找值
                return ptr;
            else if(ptr->data > val)//查找值比节点值小，向左子树搜索
                ptr = ptr->left;
            else
                ptr = ptr->right;//查找值比节点值大，向右子树搜索
        }   
    }
    
    //查找值最小的节点
    btree findmin_tree(btree root)
    {
        if (root == nullptr)//首先判断是否为空树
            return nullptr;
        if (root->left == nullptr)
            return root;
        else
            return findmin_tree(root->left);//使用递归判断
    }
    
    //查找值最大的节点
    btree findmax_tree(btree root)
    {
        if (root != nullptr)//首先判断是否为空树
            while (root->right != nullptr)//通过循环判断
                root = root->right;
        return root;
    }

**（3）插入节点**

btree insert_tree(btree root, int val)
    {
        if (search_tree(root, val) == nullptr)
        {
            if (root == nullptr)
                creat_tree(root, val);//如果树为空，则创建树
            else if (val < root->data)
                //递归插入到左子树
                root->left = insert_tree(root->left, val);
            else if (val > root->data)
                //递归插入到右子树
                root->right = insert_tree(root->right, val);
        }
    }

**（4）删除节点**

![这里写图片描述][70 1]

btree remove_tree(btree root, int val)
    {
        btree bt = search_tree(root, val);
        if (bt != nullptr)
        {
            if (val < root->data)//只有左子树
                root->left = remove_tree(root->left, val);
            else if (val > root->data)//只有右子树
                root->right = remove_tree(root->right, val);
            //左右子树都有
            else if (root->left != nullptr && root->right != nullptr)
            {
                //把右子树的最小值复制到当前节点
                root->data = findmin_tree(root->right)->data;
                //把最小值节点删除
                root->right = remove_tree(root->right, root->data);
            }
            else
            {
                //只有左子树或者右子树
                root = (root->left != nullptr)? root->left : root->right;
            }
        }
    }

### **二、二叉树的遍历** ###

遍历二叉树，就是以某种方式逐个“访问”二叉树的每一个节点。“访问”是指对节点的进行某种操作，例如输出节点的值。根据访问树根的顺序，我们有三种方式遍历二叉树：

1. 前序遍历：树根->左子树->右子树

2. 中序遍历：左子树->树根->右子树

3. 后序遍历：左子树->右子树->树根

**1、前序遍历**

先访问根节点，再遍历左子树，最后遍历右子树；并且在遍历左右子树时，仍需先访问根节点，然后遍历左子树，最后遍历右子树。   
  例如下图中二叉树前序遍历节点访问顺序为ABDGHCEIF：   
![这里写图片描述][70 2]

**2、中序遍历**

先遍历左子树、然后访问根节点，最后遍历右子树；并且在遍历左右子树的时候。仍然是先遍历左子树，然后访问根节点，最后遍历右子树。   
  例如前图中二叉树中序遍历节点访问顺序为GDHBAEICF：   
![这里写图片描述][70 3]

**3、后序遍历**

先遍历左子树，然后遍历右子树，最后访问根节点；同样，在遍历左右子树的时候同样要先遍历左子树，然后遍历右子树，最后访问根节点。前图后序遍历结果如下。   
  例如前图中二叉树后序遍历节点访问顺序为GHDBIEFCA：   
![这里写图片描述][70 4]

**4、确定唯一的二叉树**

在二叉树的三种遍历方式中，如果有中序与前序的遍历结果或者中序与后序的遍历结果，即可从这些结果中得到唯一的二叉树。

确定唯一二叉树的方式：

1. 首先根据前序遍历的首元素或者后序遍历的尾元素，在中序遍历确定根节点。

. 随后根据该根节点在中序遍历中确定左右子树。

**三、前序、中序、后序遍历的递归和非递归实现**

**1、递归实现**

void inorder(btree ptr)//中序（输出根节点次序）遍历（递归实现）
    {
        if (ptr != nullptr)
        {
            inorder(ptr->left);
            cout << ptr->data << " ";
            inorder(ptr->right);
        }
    }
    
    void preorder(btree ptr)//前序遍历（递归实现）
    {
        if (ptr != nullptr)
        {
            cout << ptr->data << " ";
            preorder(ptr->left);
            preorder(ptr->right);
        }
    }
    
    void postorder(btree ptr)//后序遍历（递归实现）
    {
        if (ptr != nullptr)
        {
            postorder(ptr->left);
            postorder(ptr->right);
            cout << ptr->data << " ";
        }
    }

**2、非递归实现（使用栈）**

//非递归中序遍历（左节点->根节点->右节点）思想：即用栈实现  
    // 因为中序遍历二叉树的特点，所以在当前节点cur不为空或栈不为空的条件下（在该条件下的原因：该条件说明  
    // 未遍历完二叉树），开始执行循环体，进行遍历：  
    //（1）从当前节点cur开始，以cur为循环条件，当cur不为空时，将cur入栈，然后以cur=cur->_left跟进，直至  
    //     将该二叉树的最左节点入栈后，入栈操作结束  
    //（2）取栈顶节点：先保存该节点（用top保存该节点的原因：还要考虑该节点的右孩子）并输出该节点的值，  
    //     然后执行栈的pop操作。  
    //（3）继续以top->_right为cur值，转（1）操作.  
    
    void inorder2(btree ptr)//中序遍历的非递归实现
    {
        stack<btree> st;
        while (ptr != nullptr || !st.empty())
        {
            while (ptr != nullptr)
            {
                st.push(ptr);
                ptr = ptr -> left;
            }
            btree tp = st.top();
            cout << tp -> data << " ";
            st.pop();
            ptr = tp -> right;
        }
    }
    
    //非递归先序遍历（根节点->左节点->右节点）思想：即用栈实现  
    //遍历二叉树的前提条件是：该二叉树不为空。在满足该条件的情况下，进行以下步骤：  
    //1.先将二叉树的根节点push进栈。  
    //2.在该栈不为空的条件下，执行一个循环（先用top保存栈顶元素，再对栈进行pop操作，因为栈具有后进先出的特点  
    //  ，所以先对top->_right进行判断是否入栈，再对top->_left进行判断是否入栈）。  
    //3.当栈为空时，先序遍历该二叉树结束。
    
    void preorder2(btree ptr)//前序遍历的非递归实现
    {
        stack<btree> st;
        if (ptr != nullptr)
        {
            st.push(ptr);
        }
        while (!st.empty())
        {       
            btree tp = st.top();
            st.pop();
            cout << tp -> data << " ";
            if (tp->right != nullptr)
                st.push(tp->right);
            if (tp->left != nullptr)
                st.push(tp->left);
        }
    }
    
    //非递归后序遍历（左节点->右节点->根节点）思想：即用栈实现  
    //（1）在当前节点cur不为空或栈不为空的条件下（在该条件下的原因：该条件说明未遍历完二叉树）。  
    //（2）从当前节点cur开始，以cur为循环条件，当cur不为空时，将cur入栈，然后以cur=cur->_left跟进，直至  
    //     将该二叉树的最左节点入栈后，入栈操作结束。取栈顶节点top：先保存该节点（用top保存该节点的原因：  
    //     还要考虑该节点的右孩子），  
    //（3）若top->_right==NULL || lastVisited == top->_right,则输出top->_value,执行栈的pop操作,并执行lastVisited = top(  
    //    用lastVisited保存最近一个所输出的节点，待到下一次同样的操作时，若lastVisited == top->_right，则  
    //    说明top的右节点已经访问过了，可以访问top了，否则会陷在cur = top->_right这步操作里）;  
    //（4）若条件（3）不满足，则继续以top->_right为cur值，转（1）操作.  
    void postorder2(btree ptr)//后序遍历的非递归实现
    {
        stack<btree> st;
        btree lastVisited  = nullptr;
        while (ptr != nullptr || !st.empty())
        {
            while (ptr != nullptr)
            {
                st.push(ptr);
                ptr = ptr -> left;
            }
            btree tp = st.top();
            if (tp->right == nullptr || lastVisited == tp->right)
            {   
                st.pop();
                cout << tp -> data << " ";
                lastVisited = tp;
            }
            else 
                ptr = tp->right;
        }
    }

**参考：**

[https://blog.csdn.net/xiaotan2011929/article/details/61427919][https_blog.csdn.net_xiaotan2011929_article_details_61427919]   
　　[http://www.cnblogs.com/QG-whz/p/5168620.html][http_www.cnblogs.com_QG-whz_p_5168620.html]

[70]: /images/20211104/c0087c6ceb504f7c94eb6fde89cfa764.png
[70 1]: /images/20211104/f5063aa11d23436f9974a7486402d93d.png
[70 2]: /images/20211104/6333651cf7c8437a85e9fcd392cc3b14.png
[70 3]: /images/20211104/1716a17bcf1b4c2dbb81d199990ffde0.png
[70 4]: /images/20211104/9e902a8a879a404abecc880e4ed3927a.png
[https_blog.csdn.net_xiaotan2011929_article_details_61427919]: https://blog.csdn.net/xiaotan2011929/article/details/61427919
[http_www.cnblogs.com_QG-whz_p_5168620.html]: http://www.cnblogs.com/QG-whz/p/5168620.html