首页 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
资讯 业界资讯 软件杂谈 编程开发 网站建设 网络观查 搜索引擎 移动应用 网站运营 网络地图
开发 移动开发 Web前端 架构设计 编程语言 互联网 数据库 系统运维 云计算 开发杂谈
[编程语言] [算法]二叉查找树
[算法]二叉查找树

【简介】


二叉查找树是一种数据结构,它支持多种动态集合操作。
在二叉查找树上执行的基本操作的时间与树的高度成正比。对于一棵含有n个节点的完全二叉树,这些操作的最坏情况运行时间为O(n)。


【结构体】


一棵二叉查找树按二叉树结构来组织的。
// 二叉查找树节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

【性质】


设x为二叉查找树上的一个节点。
如果y是x的左子树中的一个节点,则y->val 小于等于 x->val。
如果y是x的右子树中的一个节点,则y->val 大于等于 x->val。

【输出】


根据二叉查找树的性质,我们可以用中序递归遍历算法按排列顺序输出树中的所有关键字。
// 中序遍历输出二叉查找树
void InOrder(TreeNode* root){
    if(root == NULL){
        return;
    }//if
    InOrder(root->left);
    cout<<root->val<<endl;
    InOrder(root->right);
}

【插入】


// 插入
void TreeInsert(TreeNode*& root,int val){
    // 创建新节点
    TreeNode* node = new TreeNode(val);
    // 空树
    if(root == NULL){
        root = node;
        return;
    }//if
    TreeNode *pre = NULL;
    TreeNode *p = root;
    // 寻找插入位置
    while(p){
        // 父节点
        pre = p;
        // 沿左子树方向下降
        if(val < p->val){
            p = p->left;
        }//if
        // 沿右子树方向下降
        else{
            p = p->right;
        }//else
    }//while
    // 左子结点处插入
    if(val < pre->val){
        pre->left = node;
    }//if
    // 右子结点处插入
    else{
        pre->right = node;
    }//else
}

TreeInsert从根节点开始,并沿树下降。
指针p跟踪了这条路径,而pre始终指向p的父节点。初始化后while循环是这两个指针沿树下降,根据val和p->val的比较结果,可以决定向左还是向右转。
直到p成为NULL为止。这个NULL所占的位置就是我们像插入的位置。
其特点是:树的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字等于给定值的节点时再进行插入。
新插入的结点一定是一个新添加的叶子节点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

【查找】

【递归算法】

返回指向包含关键字val的节点(如果存在的)的指针,否则返回NULL
// 查找
TreeNode* TreeSearch(TreeNode* root,int val){
    if(root == NULL || root->val == val){
        return root;
    }//if
    // 左子树查找
    if(val < root->val){
        return TreeSearch(root->left,val);
    }//if
    // 右子树查找
    else{
        return TreeSearch(root->right,val);
    }//else
}

如果root是一棵空树,搜索失败,直接返回NULL。
如果root不是空树:
对碰到的每一个节点p,都要进行比较val和p->val,如果两个关键字相同,则查找结束。
如果val小于p->val,则继续查找p的左子树,如果val大于等于p->val,则继续查找p的右子树。
【非递归算法】

// 非递归查找
TreeNode* TreeSearch2(TreeNode* root,int val){
    if(root == NULL || root->val == val){
        return root;
    }//if
    TreeNode *p = root;
    while(p && val != p->val){
        // 左子树查找
        if(val < p->val){
            p = p->left;
        }//if
        // 右子树查找
        else{
            p = p->right;
        }//else
    }//while
    return p;
}

【最大元素】


要查找二叉树中具有最大关键字的元素,只要从根节点开始,沿着各节点的right指针查找下去,直到遇到NULL为止。
// 最大元素
TreeNode* TreeMaxNum(TreeNode *root){
    TreeNode *p = root;
    while(p->right){
        p = p->right;
    }//while
    return p;
}

【最小元素】


要查找二叉树中具有最小关键字的元素,只要从根节点开始,沿着各节点的left指针查找下去,直到遇到NULL为止。
// 最小元素
TreeNode* TreeMinNum(TreeNode *root){
    TreeNode *p = root;
    while(p->left){
        p = p->left;
    }//while
    return p;
}



 此文从网络中自动搜索生成,不代表本网站赞成被搜索网站的内容或立场    查看原文
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年7日历
2018-7-20 14:41:40
 
  网站联系 软件世界网-www.sjsjw.com ©2014 蜀ICP备06016416号 三峰网旗下网站