备案控制台
探索云世界
开发者社区 云计算 文章 正文

二叉查找树

2015-06-27 801
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 二叉查找树，也称二叉排序树，二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树： 若左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若右子树不空，则右子树上所有结点的值均大于它的根结点的值； 左、右子树也分别为二叉排序树查找操作步骤：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树；若大于根结点

二叉查找树，也称二叉排序树，二叉搜索树。
它或者是一棵空树；或者是具有下列性质的二叉树：

  • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 左、右子树也分别为二叉排序树

查找操作

步骤：

  • 若根结点的关键字值等于查找的关键字，成功。
  • 否则，若小于根结点的关键字值，递归查左子树；若大于根结点的关键字值，递归查右子树。
  • 若子树为空，查找不成功。

插入操作

步骤：

  • 首先执行查找算法，找出被插结点的父亲结点。
  • 判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
  • 若二叉树为空，则首先单独生成根结点。
    注意：新插入的结点总是叶子结点。

删除操作

假设被删结点是*p，其双亲是*f，不失一般性，设*p是*f的左孩子，下面分三种情况讨论：

  • 若结点*p是叶子结点，则只需修改其双亲结点*f的指针即可。
  • 若结点*p只有左子树PL或者只有右子树PR，则只要使PL或PR 成为其双亲结点的左子树即可。
  • 若结点*p的左、右子树均非空，先找到*p的中序前趋结点*s（注意*s是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：
    • 令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。
    • 以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上。

C++实现代码：

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *parent;
    TreeNode(int x) : val(x), left(NULL), right(NULL), parent(NULL) {}
};

TreeNode* minNode(TreeNode *root)
{
//    if (root != NULL && root->left != NULL)
//    {
//        return minNode(root->left);
//    }
    while (root != NULL && root->left != NULL)
    {
        root = root->left;
    }

    return root;
}

TreeNode* maxNode(TreeNode *root)
{
    if (root != NULL && root->right != NULL)
    {
        return maxNode(root->right);
    }

    return root;
}

TreeNode* search(TreeNode *root, int value)
{
    if (root == NULL || root->val == value)
    {
        return root;
    }
    else if (root->val > value)
    {
        return search(root->left, value);
    }
    else if (root->val < value)
    {
        return search(root->right, value);
    }
}

void insertNode(TreeNode*& root, int value)
{
    if (search(root, value) != NULL)
    {
        return;
    }

    TreeNode *newnode = new TreeNode(value);
    TreeNode *temp = root;
    TreeNode *parentNode = NULL;
    if (root == NULL)
    {
        root = newnode; //新插入结点成为根结点
        return;
    }

    while (temp != NULL)
    {
        parentNode = temp;
        if (temp->val > value)
        {
            temp = temp->left;
        }
        else
        {
            temp = temp->right;
        }
    }

    if (value < parentNode->val)
    {
        parentNode->left = newnode;
    }
    else
    {
        parentNode->right = newnode;
    }
    newnode->parent = parentNode;
}

bool deleteNode(TreeNode*& root, int value)
{
    TreeNode *cur = search(root, value);
    TreeNode *temp;
    if (cur == NULL)
    {
        return false; //未找到结点
    }
    if (cur->left != NULL && cur->right != NULL)
    {
        TreeNode *max_node = maxNode(cur->left);
        cur->val = max_node->val;
        deleteNode(max_node, max_node->val);
    }
    else
    {
        if (cur->left == NULL && cur->right == NULL) //删除叶子结点
        {
            temp = NULL;
        }
        else if (cur->left == NULL) //要删除结点的左结点为空
        {
            temp = cur->right;
        }
        else if (cur->right == NULL) //要删除结点的右结点为空
        {
            temp = cur->left;
        }

        if (cur->parent == NULL)
        {
            root = temp;
            if (temp != NULL) temp->parent = NULL;
        }
        else
        {
            if (cur->parent->left == cur)
            {
                cur->parent->left = temp;
            }
            else
            {
                cur->parent->right = temp;
            }

            if (temp != NULL)
            {
                temp->parent = cur->parent;
            }

        }

        delete cur;
    }

    return true;
}

void preTraverse(TreeNode *root)
{
    if (root != NULL)
    {
        cout<<root->val<<" ";
        preTraverse(root->left);
        preTraverse(root->right);
    }
}

void inTraverse(TreeNode *root)
{
    if (root != NULL)
    {
        inTraverse(root->left);
        cout<<root->val<<" ";
        inTraverse(root->right);
    }
}

void postTraverse(TreeNode *root)
{
    if (root != NULL)
    {
        postTraverse(root->left);
        postTraverse(root->right);
        cout<<root->val<<" ";
    }
}

int main()
{
    TreeNode *root = NULL;
    for (int i = 0; i < 20; i++)
    {
        insertNode(root, rand() % 100);
    }

    cout<<"先序遍历：";preTraverse(root);cout<<" END"<<endl;
    cout<<"中序遍历：";inTraverse(root);cout<<" END"<<endl;
    cout<<"后序遍历：";postTraverse(root);cout<<" END"<<endl;

    for (int  i = 0; i < 20; i++)
    {
        deleteNode(root, i);
    }
    cout<<"先序遍历：";preTraverse(root);cout<<" END"<<endl;

    TreeNode *temp = minNode(root);
    temp != NULL ? cout<<temp->val<<endl : cout<<"null"<<endl;
    temp = maxNode(root);
    temp != NULL ? cout<<temp->val<<endl : cout<<"null"<<endl;

    return 0;
}

Java实现代码：

package test;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode parent;
    TreeNode(int x){
        this.val = x;
    }
}

public class BinarySearchTree {
    TreeNode root;
    TreeNode maxElem(TreeNode node){
        while (node != null && node.right != null){
            node = node.right;
        }

        return node;
    }

    TreeNode minElem(TreeNode node){
        while (node != null && node.left != null){
            node = node.left;
        }

        return node;
    }

    TreeNode search(int key){
        TreeNode temp = root;
        while (temp != null && temp.val != key){
            if (temp.val > key){
                temp = temp.left;
            }else{
                temp = temp.right;
            }
        }

        return temp;
    }

    boolean insert(int key){
        if (search(key) != null){
            return false;
        }

        TreeNode newnode = new TreeNode(key);
        TreeNode temp = root;
        if (temp == null){
            this.root = newnode;
            return true;
        }

        TreeNode parentNode = null;
        while (temp != null){
            parentNode = temp;
            if (temp.val > key){
                temp = temp.left;
            }else{
                temp = temp.right;
            }
        }
        if (parentNode.val > key){
            parentNode.left = newnode;
        }else{
            parentNode.right = newnode;
        }
        newnode.parent = parentNode;

        return true;
    }

    boolean delete(int key){
        TreeNode cur = search(key);
        if (cur == null){
            return false;
        }

        TreeNode temp = null;
        if (cur.left != null && cur.right != null){
            TreeNode leftMax = maxElem(cur.left);
            cur.val = leftMax.val;
            delete(leftMax.val);
        }else if (cur.left == null && cur.right == null){
            temp = null;
        }else if (cur.left != null && cur.right == null){
            temp = cur.left;
        }else if (cur.left == null && cur.right != null){
            temp = cur.right;
        }

        if (cur.parent == null){
            this.root = temp;
            if (temp != null){
                temp.parent = null;
            }
        }
        else{
            if (cur.parent.left == cur){
                cur.parent.left = temp;
            }else{
                cur.parent.right = temp;
            }

            if (temp != null){
                temp.parent = cur.parent;
            }
        }

        return true;
    }

    void preTraverse(TreeNode node){
        if (node != null){
            System.out.print(node.val + " ");
            preTraverse(node.left);
            preTraverse(node.right);
        }
    }

    void inTraverse(TreeNode node){
        if (node != null){
            inTraverse(node.left);
            System.out.print(node.val + " ");
            inTraverse(node.right);
        }
    }

    void postTraverse(TreeNode node){
        if (node != null){
            postTraverse(node.left);
            postTraverse(node.right);
            System.out.print(node.val + " ");
        }
    }

    public static void main(String[] args){
        BinarySearchTree bst = new BinarySearchTree();
        for (int i = 0; i < 20; i++){
            bst.insert((int)(Math.random() * 100));
            //bst.insert(i);
        }
        System.out.print("前序遍历："); bst.preTraverse(bst.root); System.out.println();
        System.out.print("中序遍历："); bst.inTraverse(bst.root); System.out.println();
        System.out.print("后序遍历："); bst.postTraverse(bst.root); System.out.println();

        for (int i = 0; i < 20; i++){
            bst.delete(i);
        }
        System.out.print("前序遍历："); bst.preTraverse(bst.root); System.out.println();
        System.out.println("Max:" + bst.maxElem(bst.root).val);
        System.out.println("Min:" + bst.minElem(bst.root).val);
    }
}

Python实现代码：

from random import random
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.parent = None

class BinarySearchTree:   
    def __init__(self, root = None):
        self.root = root

    def minElem(self, node):
        temp = node
        while temp and temp.left:
            temp = temp.left
        return temp;

    def maxElem(self, node):
        temp = node
        while temp and temp.right:
            temp = temp.right
        return temp;

    def search(self, node, key):
        if not node:
            return None
        if node.val == key:
            return node
        elif node.val > key:
            return self.search(node.left, key)
        else:
            return self.search(node.right, key)

    def insert(self, key):
        if self.search(self.root, key):
            return
        newnode = TreeNode(key)
        if not self.root:
            self.root = newnode
            return
        parentNode = None
        temp = self.root
        while temp:
            parentNode = temp
            if temp.val > key:
                temp = temp.left
            else:
                temp = temp.right
        if parentNode.val > key:
            parentNode.left = newnode
        else:
            parentNode.right = newnode
        newnode.parent = parentNode

    def delete(self, key):
        cur = self.search(self.root, key)
        if not cur:
            return
        if cur.left and cur.right:
            leftMax = self.maxElem(cur.left)
            n = leftMax.val
            self.delete(leftMax)
            cur.val = n
        else:
            temp = None
            if cur.left:
                temp = cur.left
            elif cur.left:
                temp = cur.right

            if not cur.parent:
                self.root = temp
                temp.parent = None
            else:
                if cur.parent.left == cur:
                    cur.parent.left = temp
                else:
                    cur.parent.right = temp
                if temp:
                    temp.parent = cur.parent

    def preorderTraverse(self, node):
        if node:
            print(node.val,end = ' ')
            self.preorderTraverse(node.left)
            self.preorderTraverse(node.right)

bst = BinarySearchTree();
for i in range(0, 20):
    bst.insert(int(random()*100))
bst.preorderTraverse(bst.root)   
print()
for i in range(0, 20):
    bst.delete(i);
bst.preorderTraverse(bst.root)   
print('\nThe smallest element is %d.' % bst.minElem(bst.root).val)
print('The largest element is %d.' % bst.maxElem(bst.root).val)

没有父亲指针的C++实现代码：

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* search(TreeNode *root, int key)
{
    while (root != NULL)
    {
        if (root->val > key)
        {
            root = root->left;
        }
        else if (root->val < key)
        {
            root = root->right;
        }
        else
        {
            break;
        }
    }

    return root;
}

void insertNode(TreeNode*& root, int key)
{
    TreeNode *p = root;
    TreeNode *q;
    while (p != NULL)
    {
        if (p->val > key)
        {
            q = p;
            p = p->left;
        }
        else if (p->val < key)
        {
            q = p;
            p = p->right;
        }
        else
        {
            break;
        }
    }

    if (p != NULL)
    {
        return;
    }

    TreeNode *newnode = new TreeNode(key);
    if (root == NULL)
    {
        root = newnode;
        return;
    }

    if (q->val > key)
    {
        q->left = newnode;
    }
    else
    {
        q->right = newnode;
    }
}

void deleteNode(TreeNode*& root, int key)
{
    TreeNode *p = root;
    TreeNode *q;
    while (p != NULL)
    {
        if (p->val > key)
        {
            q = p;
            p = p->left;
        }
        else if (p->val < key)
        {
            q = p;
            p = p->right;
        }
        else
        {
            break;
        }
    }

    if (p == NULL)
    {
        return;
    }

    if (p->left != NULL && p->right != NULL)
    {
        TreeNode *s = p->left;
        TreeNode *t = p;
        while (s->right != NULL)
        {
            t = s;
            s = s->right;
        }

        p->val = s->val;
        if (t == p)
        {
            p->left = s->left;
        }
        else
        {
            t->right = s->left;
        }

        delete s;
    }
    else
    {
        TreeNode *temp;
        if (p->left == NULL && p->right == NULL)
        {
            temp = NULL;
        }
        else if (p->left == NULL)
        {
            temp = p->right;
        }
        else
        {
            temp = p->left;
        }

        if (p == root)
        {
            root = temp;
        }
        else
        {
            if (q->left == p)
            {
                q->left = temp;
            }
            else
            {
                q->right = temp;
            }
        }

        delete p;
    }
}

void preorderTraverse(TreeNode *root)
{
    if (root != NULL)
    {
        cout<<root->val<<" ";
        preorderTraverse(root->left);
        preorderTraverse(root->right);
    }
}

int main()
{
    TreeNode *root = NULL;
    for (int i = 0; i < 20; i++)
    {
        insertNode(root, rand() % 50);
    }
    preorderTraverse(root); cout<<endl;

    for (int i = 0; i < 20; i++)
    {
        deleteNode(root, i);
    }
    preorderTraverse(root); cout<<endl;
}
楚兴
目录
相关文章
极客李华
|
3月前
|
C++
平衡二叉树(C++)
平衡二叉树(C++)
极客李华
17 1
Rayce.
|
8月前
|
算法
平衡二叉树(AVL树)
平衡二叉树(AVL树)
Rayce.
50 0
游客cflknejh75ig6
|
9月前
|
存储
数据结构-各种树（二叉树、二叉查找树、平衡二叉树、红黑树、B树、B+树）
数据结构-各种树（二叉树、二叉查找树、平衡二叉树、红黑树、B树、B+树）
游客cflknejh75ig6
54 0
云与尘呀？
|
11月前
平衡二叉树的实现
平衡二叉树的实现
云与尘呀？
59 0
huihuizi
|
存储
红黑树、平衡二叉查找树
红黑树、平衡二叉查找树 平衡二叉查找树 非常常用的查找结构，各操作的时间复杂度与树的高度成正比
huihuizi
76 0
红黑树、平衡二叉查找树
这人是个程序员
|
存储 算法 Linux
【红黑树】【一种自平衡二叉查找树】
【红黑树】【一种自平衡二叉查找树】
这人是个程序员
80 0
神奇的程序员
|
存储
二叉查找树的认识
二叉查找树的认识
神奇的程序员
66 2
二叉查找树的认识
愿天堂没有BUG（公众号同名）
二叉树、平衡二叉树AVL、红黑树、B树、B+树
B树的阶数等于叶节点最大关键字数量+1（因为关键字两边都有指向子节点的指针-分叉） 在m阶(m叉)B树中除根结点外，任何节点至少[m/2]个分叉，即至少[m/2]-1个关键字， [ ]代表向上取整。 节点内的关键字采用顺序查找或二分查找。 因为关键字太少会导致树变高，降低查找效率。另外就是保证同级子树的高度相同-平衡。
愿天堂没有BUG（公众号同名）
82 0
AAAAAAAA
110.平衡二叉树
110.平衡二叉树
AAAAAAAA
91 0
110.平衡二叉树
一个处女座的程序猿
|
算法 C语言
Algorithm：树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
Algorithm：树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现
一个处女座的程序猿
2000 0
Algorithm：树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C 语言实现

热门文章

最新文章

  • 1
    疑犯追踪第一季/全集Person Of Interest迅雷下载
  • 2
    【直播系列之一】1篇文章看懂峰值带宽、流量、转码、连麦、截图五大直播计费方式
  • 3
    理解事务的4种隔离级别
  • 4
    阿里云网站域名备案流程全过程讲解(图文)
  • 5
    在服务器的raid1中安装windows server系统（踩坑记录）
  • 6
    如何用Vue实现简易的富文本编辑器，并支持Markdown语法
  • 7
    怎么才能快速提高小程序留存率！
  • 8
    程序员请放下浮躁的心
  • 9
    如何解决域中普通用户只限于10台客户机加入域的数量问题
  • 10
    博客园模板 样式优化
  • 1
    未来技术纵横谈：区块链、物联网与虚拟现实的融合与创新
    74
  • 2
    软件体系结构 - 缓存技术（9）缓存穿透
    65
  • 3
    提升Android应用性能的实用技巧
    62
  • 4
    工具变量法(两阶段最小二乘法2SLS)线性模型分析人均食品消费时间序列数据和回归诊断（下）
    72
  • 5
    软件体系结构 - 缓存技术（8）缓存雪崩
    68
  • 6
    软件体系结构 - 缓存技术（7）Redis持久化方法
    73
  • 7
    Python用KShape对时间序列进行聚类和肘方法确定最优聚类数k可视化
    68
  • 8
    软件体系结构 - 缓存技术（6）淘汰策略
    77
  • 9
    基于R语言股票市场收益的统计可视化分析
    88
  • 10
    软件体系结构 - 数据分片（2）一致性哈希分片
    77

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）