树数据结构教程5. C ++中的BST实现

在二进制搜索树上实施以下操作

1. 插入操作
2. 找到敏
3. 寻找最大
4. 有序遍历
5. 预购遍历
6. 订单遍历
7. 获取树的高度
8. 检查树是否是平衡树
9. 使用给定密钥删除节点
10. 查找给定的密钥

C ++解决方案

#include<iostream>
#include<vector>
#include<string>

using namespace std;


struct Node
{
    int data;
    Node *left;
    Node *right;
};

//global root declaration
Node *root;

Node* insert(int num, Node* root)
{
    if(root == NULL)
    {
        root = new Node;
        root->data = num;
        root->left = root->right = NULL;
    }
    else if(num < root->data)
        root->left = insert(num, root->left);

    else if(num > root->data)
        root->right = insert(num, root->right);
    return root;
}

Node* findMax(Node* root)
{
    if(root == NULL)
        return NULL;
    else if(root->right == NULL)
        return root;
    else
        return findMax(root->right);
}

Node* findMin(Node* root)
{
    if(root == NULL)
        return NULL;
    else if(root->left == NULL)
        return root;
    else
        return findMin(root->left);
}

void inorder(Node *root)
{
    if(root == NULL)
        return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

void preOrder(Node *root)
{
        if (!root)
                return;
        cout << root->data << " ";
        preOrder(root->left);
        preOrder(root->right);
}
void postOrder(Node *root)
{
        if (!root)
                return;
        postOrder(root->left);
        postOrder(root->right);
        cout << root->data << " ";
}

int getHeight(Node *root)
{
        if (!root)
                return 0;
        return 1 + max(getHeight(root->left) , getHeight(root->right));
}

bool isBalanced(Node *root)
{
        if (!root)
                return false;
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);

        if (abs(leftHeight - rightHeight) > 1)
                return false;
        return true;
}

Node* makeEmpty(Node *root)
{
    if(root == NULL)
        return NULL;
    {
        makeEmpty(root->left);
        makeEmpty(root->right);
        delete root;
    }
    return NULL;
}

Node* remove(Node* node, int key)
{
   Node* temp;
    if(node == NULL)
        return NULL;
    else if(key < node->data)
        node->left = remove(node->left, key);
    else if(key > node->data)
        node->right = remove(node->right, key);
    else if(node->left && node->right)
    {
        temp = findMin(node->right);
        node->data = temp->data;
        node->right = remove(node->right, node->data);
    }
    else
    {
        temp = node;
        if(node->left == NULL)
            node = node->right;
        else if(node->right == NULL)
            node = node->left;
        delete temp;
    }

    return node;
}

Node* find(Node *root, int key)
{
    if(root == NULL)
        return NULL;
    else if(key < root->data)
        return find(root->left, key);
    else if(key > root->data)
        return find(root->right, key);
    else
        return root;
}

int main()
{
    root = insert(10, root);
    root = insert(30, root);
    root = insert(20, root);
    root = insert(50, root);
    root = insert(60, root);
    root = insert(25, root);
    root = insert(15, root);

    cout<<"\nThe values displayed using inorder traversal = "<<endl;
    inorder(root); 

    cout<<"\nThe values displayed using preOrder traversal = "<<endl;
    preOrder(root); 

    cout<<"\nThe values displayed using postOrder traversal = "<<endl;
    postOrder(root); 

    Node *max_value = findMax(root);
    cout<<"\n\nThe maximum value is "<< max_value->data <<endl;
    
    Node *min_value = findMin(root);
    cout<<"\nThe minumim value is "<< min_value->data <<endl;

    cout<<"\nThe height of the tree is = "<< getHeight(root)<<endl;

    if(isBalanced(root))
    	cout<<"\nThe tree is balanced"<<endl;
    else
    	cout<<"\nThe tree not is balanced"<<endl;


    int key = 60;

    if(find(root, key) != NULL)
    	cout<<"\nThe key "<<key<<" is present\n"<<endl;
    else
      	cout<<"\nThe key "<<key<<" is not present\n"<<endl;

   	remove(root, key);
    cout<<"\nThe key  "<<key<<" has been deleted"<<endl;

    cout<<"\nThe values displayed using inorder traversal = "<<endl;
    inorder(root); 
    cout<<endl;

	return 0;
  	
}

输出：

The values displayed using inorder traversal =
10 15 20 25 30 50 60

The values displayed using preOrder traversal =
10 30 20 15 25 50 60

The values displayed using postOrder traversal =
15 25 20 60 50 30 10

The maximum value is 60

The minumim value is 10

The height of the tree is = 4

The tree not is balanced

The key 60 is present


The key  60 has been deleted

The values displayed using inorder traversal =
10 15 20 25 30 50

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：