数据结构与算法-二叉排序树的插入

﹏ヽ暗。殇╰゛Y 2022-05-28 00:43 212阅读 0赞

**二叉排序树的插入思想：**  
判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。  
若二叉树为空。则首先单独生成根结点。  
注意：新插入的结点总是叶子结点。

**节点的构造：**

struct BinaryTreeNode {
        int val;
        BinaryTreeNode *left;
        BinaryTreeNode *right;
        BinaryTreeNode(int x) : val(x), left(NULL), right(NULL) {} // 构造函数， 初始化节点
    };

**插入程序：**

BinaryTreeNode* Insert(BinaryTreeNode* BST, int x){
        if(!BST){
            BST = new BinaryTreeNode(x);
        }
        else{
            if(x < BST->val)
                BST->left = Insert(BST->left, x);
            else if(x > BST->val)
                BST->right = Insert(BST->right, x);
        }
        return BST;
    }

**全部程序：**

#include <iostream>
    
    using namespace std;
    
    struct BinaryTreeNode {
        int val;
        BinaryTreeNode *left;
        BinaryTreeNode *right;
        BinaryTreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    // 中序遍历二叉排序树
    void InOrderTraversal_Recurrence(BinaryTreeNode *root){
        stack< BinaryTreeNode* > s;
        BinaryTreeNode *p=root;
        while(p!=NULL||!s.empty()){
            while(p!=NULL){
                s.push(p);
                p=p->left;
            }
            if(!s.empty()){
                p=s.top();
                cout<< p->val <<" ";
                s.pop();
                p=p->right;
            }
        }
    }
    
    // 插入
    BinaryTreeNode* Insert(BinaryTreeNode* BST, int x){
        if(!BST){
            BST = new BinaryTreeNode(x);
        }
        else{
            if(x < BST->val)
                BST->left = Insert(BST->left, x);
            else if(x > BST->val)
                BST->right = Insert(BST->right, x);
        }
        return BST;
    }
    
    int main(){
        BinaryTreeNode a(8);
        BinaryTreeNode b(3);
        BinaryTreeNode c(10);
        BinaryTreeNode d(1);
        BinaryTreeNode e(6);
        BinaryTreeNode f(15);
        a.left = &b;
        a.right = &c;
        b.left = &d;
        b.right = &e;
        c.right = &f;
    
        Insert(&a, 11);
        InOrderTraversal_Recurrence(&a);
        return 0;
    }