首页 > 二叉树：二叉搜索树的创建和插入

二叉树：二叉搜索树的创建和插入

二叉搜索树又名二叉排序树。

大概简略的思维导图如下，方便记忆特性

在这里插入图片描述

基本二叉搜索树创建过程如下

/*数据结构如下*/
typedef struct tree
{ int data;struct tree *left = NULL;struct tree *right = NULL;
}Tree,*TreeNode;/*Node 为二叉树根节点，insert为插入的节点*/
void create_tree(TreeNode *node, Tree *insert) { if ((*node) -> data > insert -> data) { if ((*node) -> left) { create_tree(&(*node) ->left,insert);} else { (*node) -> left = insert;}} else { if ((*node)  -> right) { create_tree(&(*node) ->right, insert);} else { (*node)  -> right = insert;}}
}

查找某一数值是否存在的过程如下:

bool search(Tree *node, int val) { if (node -> data == val) { return true;} if (node -> data > val) { if (node -> left) { return search(node -> left, val);} else { return false;}} else { if (node -> right) { return search(node -> right, val);} else { return false;}}
}

测试代码如下:

#include 
#include 
#include 
#include 
#include 
#include using namespace std;typedef struct tree
{ int data;struct tree *left = NULL;struct tree *right = NULL;
}Tree,*TreeNode;void create_tree(TreeNode *node, Tree *insert) { if ((*node) -> data > insert -> data) { if ((*node) -> left) { create_tree(&(*node) ->left,insert);} else { (*node) -> left = insert;}} else { if ((*node)  -> right) { create_tree(&(*node) ->right, insert);} else { (*node)  -> right = insert;}}
}void preOrder(Tree *node, int layer) { if (node == NULL) { return;}for (int i = 0;i < layer; ++i) { cout << "----";}cout << node -> data << endl;preOrder(node -> left,layer + 1);preOrder(node -> right, layer + 1);
}bool search(Tree *node, int val) { if (node -> data == val) { return true;} if (node -> data > val) { if (node -> left) { return search(node -> left, val);} else { return false;}} else { if (node -> right) { return search(node -> right, val);} else { return false;}}
}int main(int argc, char const *argv[])
{ Tree *node;TreeNode root;root = (Tree *)malloc(sizeof(tree));root -> data = 8;root -> left = NULL;root -> right = NULL;int n;int tmp;cin >> n;for (int i = 0;i < n; ++i) { node = (Tree *)malloc(sizeof(tree));cin >> tmp;node -> data = tmp;create_tree(&root, node);}cout << "preOrder" << endl;preOrder(root,0);string s = (search(root, 10)==1)?"success":"failed";cout << "
search 10 in tree "<< s << endl;return 0;
}

输出如下：

#输入
5
3 1 19 2 9
#输出
preOrder
8
----3
--------1
------------2
----19
--------9search 10 in tree failed#输入
5
3 1 10 2 9  
#输出  
preOrder
8
----3
--------1
------------2
----10
--------9search 10 in tree success

更多相关：

  • 二叉树：二叉搜索树的编码和解码

    二叉搜索树的编码和解码描述： 编码：即将一个二叉搜索树编码，节点数值转换为字符串 解码：即将一个字符串解码，数值转换为对应的二叉搜索树的节点 过程导图如下： 针对性编码实现如下: /*数字转字符串*/ void change_num_to_string(int val, string &tmp) {string buf;whil...

  • Linux安装Nodejs

    Linux安装Nodejs 　　 　　　阿里云镜像： https://npm.taobao.org/mirrors/node/ 选择所需版本，进行下载。 　　　我这边下载的是：https://npm.taobao.org/mirrors/node/v8.2.1/node-v8.2.1-linux-x64.tar.gz  　　　 　　　...

  • Hadoop自学笔记（二）HDFS简单介绍

    1. HDFS Architecture 一种Master-Slave结构。包括Name Node, Secondary Name Node,Data Node Job Tracker, Task Tracker。JobTrackers: 控制全部的Task Trackers 。这两个Tracker将会在MapReduce课程里...

  • Sublime Text3配置Node.js开发环境

    下载Nodejs插件，下载zip压缩包后解压链接: http://pan.baidu.com/s/1hsBk60k 密码: jrcv打开Sublime Text3，点击菜单“首选项（N）” =>“浏览插件（B）”打开“Packages”文件夹，并将第1部的Nodejs文件夹剪切进来打开文件“Nodejs.sublime-build”，...

  • L3-010. 是否完全二叉搜索树

    L3-010. 是否完全二叉搜索树 时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越 将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。 输入格...

  • 完全二叉树的JAVA实现（以及非递归遍历方法）

     一个用于实现初始化指定个数的完全二叉树，以及两个非递归的深度优先遍历，和广度优先遍历 package fifth;  import java.util.Random;  public class Tool{     public static Random rand= new Random(); }  --------------...

  • 相机标定 matlab opencv ROS三种方法标定步骤（2）

    #include #include #include #include #include #include #include

  • 剑指offer：面试题20. 表示数值的字符串

    题目：表示数值的字符串 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"0123"及"-1E-16"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。 解题： 数值错误的形式有多种多样，但是正确的...

  • 数字太大了，计算加法、减法会报错，结果不正确？怎么办？用JavaScript实现大数据（超过20位的数字）相加减运算。

    加法伺候  //超过20位数值相加---------------------------------------- function bigNumAdd(a, b) {if (!(typeof a === "string" && typeof b === "string")) return console.log("传入参数必...

  • Python中使用中文正则表达式匹配指定的中文字符串

    业务场景： 从中文字句中匹配出指定的中文子字符串 .这样的情况我在工作中遇到非常多, 特梳理总结如下. 难点: 处理GBK和utf8之类的字符编码, 同时正则匹配Pattern中包含汉字,要汉字正常发挥作用,必须非常谨慎.推荐最好统一为utf8编码,如果不是这种最优情况,也有酌情处理. 往往一个具有普适性的正则表达式会简化程...

  • Linux 下获取本机所有网卡 以及 网卡对应ip 列表

    简单record 一下 #include // 'struct sockaddr_in' #include #include // 'struct ifreq' and 'struct if_nameindex' #include #inc...

©2024 11GX.COM