树形查找（二叉查找树）

树形查找（二叉查找树）

树形查找

​​介绍​​​​树的定义​​​​二叉排序树的插入​​​​二叉排序树的创建​​​​树形查找​​​​后续​​

介绍

我们在平时的查找算法中，最多的往往是顺序查找和折半查找，而对树形查找往往一知半解，本文主要介绍二叉排序树的创建，插入和查找。

树的定义

树是一种数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： 每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。 而如果一棵树他的每个节点最多含有两个子树的树称为二叉树。 二叉树的程序定义一般如下：

typedef char Elemtype ;typedef struct BiNode{ Elemtype data; struct BiNode *lchild,*rchild;}*BiTree;

二叉排序树的插入

添加一个值为k的节点到树T上。

int BST_inser(BiTree T,Elemtype k){ if(T==NULL) { T=(BiTree)malloc(sizeof(BiNode)); T->data=k; T->lchild=NULL; T->rchild=NULL; return 1;//插入成功 } else if(T->data==k) { return 0; } else if(T->data>k) { return BST_inser( T=T->lchild,k); } else { return BST_inser(T=T->rchild,k); }}

二叉排序树的创建

二叉排序树的创建其实就是创建一个空树，然后将一组数据依次存放到这个树种。

void Creat_BST(BiTree &T,Elemtype a[],int n){ T=NULL;//初始时T为空树 int i=0; while(i

树形查找

二叉排序树的查找其实非常简单，就是将值k从排序树的根节点，依次往下差，当k大于当前比对的T节点值的时候，查找此节点T的右孩子，当k小于当前比对的T节点值的时候，查找此节点T的左孩子，当等于此节点的值的时候，返回此节点。

BiNode *Bst_search(BiTree T,Elemtype k){ while(T!=NULL&&T->data!=k) { if(kdata) T=T->lchild; else T=T->rchild; } return T;}

后续

如果想了解更多物联网、智能家居项目知识，可以关注我的​​项目实战​​​专栏和​​软硬结合​​专栏。

编写不易，感谢支持。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。