二叉查找树C++实现

二分查找树特点:(1)若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)任意节点的左、右子树

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

二叉查找树C++实现此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

二分查找树特点:

(1) 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

(2) 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

(3) 任意节点的左、右子树也分别为二叉查找树。

(4) 没有键值相等的节点(no duplicate nodes)。

前序遍历:中左右

中序遍历:左中右

序遍历:左右中

二叉查找树的重点在于如何找节点的前驱节点和后继节点

二叉查找树C++实现
二叉查找树C++实现

#pragma once
#include <iostream>
using namespace std;

template <class T>
class BSTNode
{
public:
    T key;
    BSTNode *parent;
    BSTNode *left;
    BSTNode *right;

    BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):key(value),parent(p),left(l),right(r)
    {

    }
};

template <class T>
class BSTree
{
private:
    BSTNode<T> *mRoot;

public:
    BSTree():mRoot(NULL){}
    ~BSTree(){}

    // 前序排序
    void preOrder()
    {
        preOrder(mRoot);
    }
    void inOrder()
    {
        inOrder(mRoot);
    }
    void postOrder()
    {
        postOrder(mRoot);
    }
    // 查找二叉树中键值为key的节点
    BSTNode<T>* SearchKey(const T key)
    {
        return SearchKey(mRoot, key);
    }
    BSTNode<T>* minKey()
    {
        return minKey(mRoot);
    }
    BSTNode<T>* maxKey()
    {
        return maxKey(mRoot);
    }
    // 插入节点
    void insert( T key)
    {
        BSTNode<T> *z = new BSTNode<T>(key, NULL, NULL, NULL);

        if (z == NULL)
        {
            return;
        }
        insert(mRoot, z);
    }

private:
    // 前序排序
    void preOrder(BSTNode<T> *tree) const
    {
        if (tree != NULL)
        {
            cout << tree->key << " ";
            preOrder(tree->left);
            preOrder(tree->right);
        }
    }

    // 中序排序
    void inOrder(BSTNode<T> *tree) const
    {
        if (tree != NULL)
        {
            preOrder(tree->left);
            cout << tree->key << " ";
            preOrder(tree->right);
        }
    }

    // 后序排序
    void postOrder(BSTNode<T> *tree) const
    {
        if (tree != NULL)
        {
            preOrder(tree->left);
            preOrder(tree->right);
            cout << tree->key << " ";
        }
    }
    BSTNode<T>* SearchKey(BSTNode<T>* pNode, const T key) const
    {
        // 递归查找
        /*if (pNode = NULL || key == pNode->key)
        {
            return pNode;
        }
        else if (key > pNode->key)
        {
            return SearchKey(pNode->right);
        }
        else
        {
            return SearchKey(pNode->left);
        }*/

        // 非递归查找
        BSTNode<T>* x = pNode;
        while (x != NULL)
        {
            if (key > x->key)
            {
                x = x->right;
            }
            else if (key < x->key)
            {
                x = x->left;
            }
            else
            {
                return x;
            }
        }

        return NULL;
    }
    // 将节点插入到二叉树中
    void insert(BSTNode<T>* &tree, BSTNode<T> *Node)
    {
        BSTNode<T> *y = NULL;
        BSTNode<T> *x = tree;  
        while (NULL != x)
        {
            y = x;
            if (Node->key > x->key)
            {
                x = x->right;
            }
            else
            {
                x = x->left;
            }
        }

        Node->parent = y;       // 这到后面两句为关键代码
        if (NULL == y)
        {
            tree = Node;
        }
        else if (Node->key > y->key)
        {
            y->right = Node;
        }
        else
        {
            y->left = Node;
        }
    }
    // 查找最小节点
    BSTNode<T>* minKey(BSTNode<T>* pNode) const 
    {
        while (pNode != NULL)
        {
            pNode = pNode->left;
        }

        return pNode;
    }
    BSTNode<T>* maxKey(BSTNode<T>* pNode) const
    {
        while (pNode != NULL)
        {
            pNode = pNode->right;
        }

        return pNode;
    }
    // 找节点(x)的后继节点。即查找二叉树中数值大于该节点的最小值
    BSTNode<T>* Successor(BSTNode<T>* x)
    {
        // 分三种情况
        // 1. x有右孩子,找到以右孩子为根的子树的最小节点
        // 2. x没有右孩子,当x为左孩子,则x的父节点为后继节点
        // 2. x没有右孩子,当x为右孩子,则找x的最低父节点,并且该父节点具有左孩子
        if (x->right != NULL)
        {
            return minKey(x->right);
        }
        BSTNode<T>* y = x->parent;
        while ((NULL != y) &&(x == y->right))
        {
            x= y;
            y = y->parent;
        }

        return y;
    }
    // 找结点(x)的前驱结点。即查找"二叉树中数据值小于该结点"的"最大结点"
    BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x)
    {
        // 如果x存在左孩子,则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
        if (x->left != NULL)
            return maxKey(x->left);

        // 如果x没有左孩子。则x有以下两种可能:
        // (01) x是"一个右孩子",则"x的前驱结点"为 "它的父结点"。
        // (01) x是"一个左孩子",则查找"x的最低的父结点,并且该父结点要具有右孩子",找到的这个"最低的父结点"就是"x的前驱结点"。
        BSTNode<T>* y = x->parent;
        while ((y!=NULL) && (x==y->left))
        {
            x = y;
            y = y->parent;
        }

        return y;
    }
                                        
    // 删除二叉树中的节点,并返回被删除的节点
    //BSTNode<T>* RemoveNode(BSTNode<T>* &tree, BSTNode<T>* pNode)
    //{
    //    BSTNode<T>* x = tree;

    //    while (NULL != x && pNode->key != x->key)
    //    {
    //        if (pNode->key > x->key)
    //        {
    //            x = x->right;
    //        }
    //        else if (pNode->key < x->key)
    //        {
    //            x = x->left;
    //        }
    //    }

    //    // 找到或x为空

    //}
};

View Code

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120253.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • python输入方式大全

    python输入方式大全python输入方式总结写在开头:在学算法过程中想温习python结果发现连输入都不清楚我是菜鸡总结一下python的输入方式适用于各种网站的算法题目的输入格式单个输入 #单个输入n=input()#无参数默认返回字符串n=input(“有提示参数的输入”)#有提示性输入语句的输入,仍是以str类型返回n=int(input())#根据给定的类型输入,返回值类型intn=float(input())#根据给定的类型输入,返回

  • CPU C-state & cpuidle driver[通俗易懂]

    CPU C-state & cpuidle driver[通俗易懂]1.什么是C-states、C-mode?为了在CPU空闲时节约能源,可以命令CPU进入低功耗模式。C-state是intelCPU处于空闲时的一种状态,CPU有几种电源模式,它们统称为“c状态”或“c模式”低功耗模式最初是在486DX4处理器中引入的。到目前为止,已经引入了更多的功耗模式,并且对每种模式进行了增强,以使CPU在这些低功耗模式下消耗更少的功率。CPU的每个状态都使用不同的电量,并且对应用程序性能的影响也不同。每当CPU内核处于空闲状态时,内置的节能逻辑就会启动,并尝试将内核从当前

    2022年10月27日
  • easyui(一) 初始easyui「建议收藏」

    easyui(一) 初始easyui「建议收藏」分享使我快乐。哈哈~–WZY一、什么是easyui?学习一个东西,最重要的是知道它的定位(是干嘛的,基本的用法是什么,快速入门),其实easyui也非常简单,不要觉得很难。easyui就是一

  • startActivityForResult解析

    startActivityForResult解析startActivity用于页面间的正常跳转。startActivityForResult用于页面间的跳转并回传数据,比如商城类的App下单时会有选择地址,选择之后地址更新。1.先用startActivityForResult方式启动一个页面 btn=(Button)findViewById(R.id.btn);btn.setOnClickListen

  • 面试被问selenium自动化模型,你了解多少?

    面试被问selenium自动化模型,你了解多少?

  • Android开发 – 基本UI设计

    Android开发 – 基本UI设计文章目录Android开发-基本UI设计1.页面部分占用1/N的情况2.分割线的实现Android开发-基本UI设计本博客记录本人在安卓开发时候遇到的一些UI设计的问题以及解决方法记录来自Project-FoodList1.页面部分占用1/N的情况示例:完整界面 界面顶部要求顶部界面只占1/3解决方案使用线性布局,其属性android:orienta…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号