二叉查找树查找算法
Ⅰ 二叉树查找树算法实现
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
typedef int ElemType;
typedef int Status;
typedef struct TElemType{
int key;
int num;
}TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status SearchBST(BiTree T,int key,BiTree f,BiTree &p){
if(!T) { p=f; return ERROR;}
else if(EQ(T->data.key,key)) { p=T; return OK; }
else if(LT(key,T->data.key))
return SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
Status SearchBST1(BiTree T,int key,BiTree f,BiTree &p){
if(!T) { p=f; return ERROR;}
else if(EQ(T->data.key,key)) {
printf("%d %d",p->data.key,p->data.num);
p=T; return OK; }
else if(LT(key,T->data.key))
return SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
Status InsertBST(BiTree &T,TElemType e){
BiTree s,p;
if(!SearchBST(T,e.key,NULL,p)){
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=s->rchild=NULL;
if(!p) T=s;
else if(LT(e.key,p->data.key)) p->lchild=s;
else p->rchild=s;
return OK;
}
}
Status Output(TElemType e){
printf("%d ",e.key);
printf("%d\n",e.num);
}
Status PreOrderTraver( BiTree T){//二叉树先序遍历
if(T==NULL) return ERROR;
else{
Output(T->data);
PreOrderTraver(T->lchild);
PreOrderTraver(T->rchild);}
return OK;
}
int main()
{
BiTree T,f=NULL,q;
TElemType a;
int i,n,b;
printf("请输入你要创建的二叉排序树的结点个数:\n");
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",a.key);
scanf("%d",a.num);
InsertBST(T,a);
}
printf("请输入你要查找的关键字: ");{
scanf("%d",b);
if(SearchBST1(T,b,f,q)) printf("查找成功！\n");
else printf("查找失败！\n");}
printf("二叉树的先序遍历:\n");
PreOrderTraver(T);
system("pause");
return 0;
}
这个就是！希望可以帮助你！
Ⅱ 二叉排序树的构造和查找方法是什么
二叉排序树的构造过程：按照给定序列，以此将结点插入二叉排序树中，在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。
插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；
当非空时，将待插结点关键字S->key和树根关键字t->key进行比较，
若s->key = t->key,则无须插入，若s->key< t->key,则插入到根的左子树中，
若s->key> t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，
如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。
说明：
① 每次插入的新结点都是二叉排序树上新的叶子结点。
② 由不同顺序的关键字序列，会得到不同二叉排序树。
③ 对于一个任意的关键字序列构造一棵二叉排序树，其实质上对关键字进行排序。
查找的过程类似，从根结点开始进行比较，小于根结点的在左子树上，大于根结点的在右子树上，以此查找下去，直到查找成功或不成功（比较到叶子结点）。
Ⅲ 数据结构与算法-二叉树(Binary Tree)
名词解释
节点: 每个元素
父子关系: 用来连线相邻节点之间的关系
父节点: A节点就是B节点的父节点
子节点: B节点就是A节点的子节点
兄弟节点: B、C、D这三个节点的父节点是同一个节点
根结点: 没有父节点的节点
叶子结点: 没有子节点的节点
节点的高度: 节点到叶子结点到最长路径(边数) (计数起点为0, 从下往上)
节点的深度: 根节点到这个节点经历过的边个数 (计数起点为0, 从上往下)
节点的层数: 节点到深度 + 1 (计数起点为1)
树的高度: 根节点的高度
特点
最常用的树数据结构
每个节点最多有两个子节点(左子节点、右子节点)
满二叉树: 叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点
完全二叉树: 叶子节点都在最底下两层，最后一层的叶子节点都 靠左排列 ，并且除了最后一层，其他层的节点个数都要达到最大
二叉树存储方式
数组顺序存储法
通过数组下标来顺序存储数据 (i表示当前节点深度,从0开始)
根节点: i = 1，左节点:2 * i，右节点: 2 * i + 1，父节点: i / 2
完全二叉树采用此方式节省内存空间
链式存储法
每个节点需要存储三分数据:当前节点数据、左节点指针、右节点指针,比较占用空间
遍历
常用方式
前序遍历: 树任意节点，先打印当前节点，再打印它的左子树，最后打印它的右子树
中序遍历: 树任意节点，先打印它的左子树，再打印当前节点，最后打印它的右子树
后序遍历: 树任意节点，先打印它的左子树，再打印它的右子树，最后打印当前节点
二叉树的前、中、后序遍历就是一个递归的过程
时间复杂度是O(n)
每个节点最多被访问两次，遍历操作的时间复杂度跟节点的个数n成正比
特点
二叉查找树为实现快速查找而生，支持快速查找一个数据、快速插入、快速删除一个数据
特殊结构: 其左子树每个节点的值 < 树的任意一个节点的值 < 其右子树每个节点的值
先取根节点，如果它等于要查找的数据，那就返回。
如果要查找的数据比根节点的值小，那就在左子树中递归查找；
如果要查找的数据比根节点的值大，那就在右子树中递归查找
一般插入的数据在叶子节点上，从根节点开始依次比较要插入的数据和节点的大小关系
如果插入数据比节点的数值大，并且节点的右子树为空，将新数据插到右子节点位置；
如果不为空，就再递归遍历右子树，查找插入位置。
如果插入数据比节点的数值小，并且节点的左子树为空，将新数据插到左子节点位置；
如果不为空，就再递归遍历左子树，查找插入位置。
针对要删除节点的子节点个数的不同，需分三种情况来处理
1.如果要删除的节点没有子节点，步骤如下: (如图中的删除节点55)
只需将父节点中指向要删除节点的指针置为null
2.如果要删除的节点只有一个子节点，步骤如下: (如图中删除节点13)
只需将父节点中指向要删除节点的指针，让它指向要删除节点的子节点即可
3.如果要删除的节点有两个子节点，步骤如下: (如图中的删除节点18)
首先，需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上；
然后，再删除掉这个最小节点，因为最小节点肯定没有左子节点
删除操作，有个优化方案: 就是单纯将要删除的节点标记为“已删除”，
这种方案删除操作就变简单很多，但是比较浪费内存空间
支持快速地查找最大节点和最小节点、前驱节点和后继节点
另外一种重要特性:
中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度为O(n)
因此，二叉查找树也叫作二叉排序树
以上几种操作都默认树中节点存储的都是数字，而且都是不存在键值相同的情况
实际应用场景中采用对象的某个字段作为键值来构建二叉查找树，其他字段称为卫星数据
如果存储的两个对象键值相同，两种解决方案
1.把值相同的数据都存储在同一个节点(采用链表或支持动态扩容的数组等数据结构)
2.每个节点只存储一个数据，把这个新插入的数据当作大于这个节点的值来处理，如下图:
查找操作
当查找数据时遇到值相同的节点，继续在右子树中查找，直到遇到叶子节点才停止。
这样就把键值等于要查找值的所有节点都查找出来
删除操作
先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除
对于同一组数据可构造不同二叉查找树。查找、插入、删除操作的执行效率都不一样
图最左边树，根节点的左右子树极度不平衡，退化成链表，查找时间复杂度为O(n)
最理想的情况，二叉查找树是一棵完全二叉树（或满二叉树）
时间复杂度都跟树的高度成正比，也就是O(height)
树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示
满二叉树: 下一层节点个数是上一层的2倍，第K层包含节点个数就是2^(K-1)
完全二叉树: 假设最大层数是L，总的节点个数n，它包含的节点个数在1个到2^(L-1)个之间
L的范围是[ , +1]，完全二叉树的高度小于等于
极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求
平衡二叉查找树: 树的高度接近logn，时间复杂度较稳定为O(logn)
1.排序对比
散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序
二叉查找树只需要中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列
2.性能稳定性对比
散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定
最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)
3.时间复杂度对比
散列表查找等操作时间复杂度是常量级，因存在哈希冲突，这个常量不一定比logn小
另外加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高
4.结构设计对比
散列表构造比较复杂，需要考虑:散列函数设计、冲突解决办法、扩容、缩容等
平衡二叉查找树只需要考虑平衡性，而且目前这个的解决方案较成熟、固定
5.空间复杂度
散列表: 避免过多散列冲突，装载因子不能太大，特别基于开放寻址法，否则浪费太多空间
Ⅳ 二叉排序树查找的二叉排序树查找的程序实现:
5. 二叉排序树的删除:
假设被删结点是*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的左（或右）链上。
6. 删除算法演示 :
7. 二叉排序树的查找:
在二叉排序树中进行查找的过程和二分查找类似，也是一个逐步缩小查找范围的过程。若查找成功，则是走了一条从根结点到待查结点的路径；若查找失败，则是走了一条根结点到某个叶子结点的路径。因此，查找过程中和关键字比较的次数不超过树的深度。
由于含有n个结点的二叉排序树不唯一，形态和深度可能不同。故含有n个结点的二叉排序树的平均查找长度和树的形态有关。
最好的情况是： 二叉排序树和二叉判定树形态相同。
最坏的情况是： 二叉排序树为单支树，这时的平均查找长度和顺序查找时相同。
最坏情况示例
就平均性能而言，二叉排序树上的查找和二分查找相差不大，并且二叉排序树上的插入和删除结点十分方便，无须大量移动结点。
Ⅳ 二叉树算法是什么
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。
二叉树的第i层至多有2^（i 1）个结点；深度为k的二叉树至多有2^k 1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。
二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
(5)二叉查找树查找算法扩展阅读：
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树算法有五种基本形态：
1、空二叉树——(a)
2、只有一个根结点的二叉树——(b);
3、右子树为空的二叉树——(c);
4、左子树为空的二叉树——(d);
5、完全二叉树——(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
Ⅵ C语言数据结构（二叉排序树的创建及查找算法）
int BSTInsert(BTNode *&T,int k)//修改此处，理由：引用型操作
Ⅶ 二叉树算法是什么
二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
性质
1、在二叉树中，第i层的结点总数不超过2^(i-1)。
2、深度为h的二叉树最多有2^h-1个结点（h>=1)，最少有h个结点。
3、对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1。
Ⅷ 二叉树查找法
是错误的
二叉树是一种很有用的非线性结构，具有以下两个特点：
①非空二叉树只有一个根结点；
②每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。
由以上特点可以看出，在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，而树结构中的每一个结点的度可以是任意的。另外，二叉树中的每个结点的子树被明显地分为左子树和右子树。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即为叶子结点。
（2）二叉树的基本性质
二叉树具有以下几个性质：
性质1：在二叉树的第k层上，最多有2k-1（k≥1）个结点；
性质2：深度为m的二叉树最多有2m-1个结点；
性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。
性质4：具有n个结点的二叉树，其深度至少为〔log2n〕+1，其中〔log2n〕表示取log2n的整数部分。
Ⅸ 二叉查找树算法
#include <iostream>using namespace std;typedef struct _node{ int data; struct _node *pLeftPtr; struct _node *pRightPtr;}BTreeNode;class BinarySearchTree{public: BinarySearchTree(); ~BinarySearchTree(); bool Create(int* pIntArray,int arrLength); bool Insert(int data); // 查找节点，searchLength为搜索长度，返回值为true表示指定的数据存在，否则不存在 bool Find(int data, int* searchLength); // 中序输出二叉树 void MidOutput(); // 释放内存 void Destroy(); void Delete(int data);protected: bool Insert(BTreeNode* pRoot, int data); bool Find(BTreeNode* pRoot,int data, int *searchLength); void Delete(BTreeNode* &pRoot, int data); void MidOutput(BTreeNode* pRoot); void Destroy(BTreeNode* pRoot);private: BTreeNode* m_pRoot; //二叉搜索树根节点};BinarySearchTree::BinarySearchTree(){ m_pRoot = NULL;}BinarySearchTree::~BinarySearchTree(){ Destroy();}bool BinarySearchTree::Create(int* pIntArray,int arrLength){ for(int i=0; i<arrLength; i++) { if(!Insert(*(pIntArray+i))) return false; } return true;}bool BinarySearchTree::Insert(BTreeNode* pRoot, int data){ BTreeNode* pNewNode = new BTreeNode; if(pNewNode == NULL) return false; pNewNode->data = data; pNewNode->pLeftPtr = NULL; pNewNode->pRightPtr = NULL; BTreeNode* pCurrentNode = pRoot; BTreeNode* pParentNode = pCurrentNode;// 保存父节点的指针 int flag = 0;// 标记插入节点的位置 if(pCurrentNode == NULL) { m_pRoot = pNewNode; }else{ while(pCurrentNode) { if(data < pCurrentNode->data) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pLeftPtr; flag = 0; }else if(data > pCurrentNode->data){ pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pRightPtr; flag = 1; } } if(flag == 0) { pParentNode->pLeftPtr = pNewNode; }else{ pParentNode->pRightPtr = pNewNode; } } return true; }bool BinarySearchTree::Insert(int data){ return Insert(m_pRoot,data);}bool BinarySearchTree::Find(BTreeNode* pRoot,int data, int *searchLength){ if(pRoot == NULL) { *searchLength = 0; return false; } BTreeNode* pCurrentNode = pRoot; static int length = 0; while(pCurrentNode != NULL) { if(data == pCurrentNode->data) { *searchLength = length; cout<<"数字"<<data<<"存在二叉树中,查找长度为: "<<endl<<length<<endl; return true; }else if(data < pCurrentNode->data) { length ++; pCurrentNode = pCurrentNode->pLeftPtr; }else{ length ++; pCurrentNode = pCurrentNode->pRightPtr; } } *searchLength = length; cout<<"数字"<<data<<"不在二叉树中,查找长度为: "<<endl<<length<<endl; length = 0; // 每次查找结束，重新赋值为0 return false;}bool BinarySearchTree::Find(int data, int* searchLength){ return Find(m_pRoot,data,searchLength);}void BinarySearchTree::Destroy(BTreeNode* pRoot){ BTreeNode* pCurrentNode = pRoot; if(pCurrentNode == NULL) return; Destroy(pCurrentNode->pLeftPtr); Destroy(pCurrentNode->pRightPtr); delete pCurrentNode; m_pRoot = NULL;}void BinarySearchTree::Destroy(){ Destroy(m_pRoot);}void BinarySearchTree::MidOutput(BTreeNode* pRoot){ if(pRoot) { MidOutput(pRoot->pLeftPtr); cout<<pRoot->data <<" "; MidOutput(pRoot->pRightPtr); }}void BinarySearchTree::MidOutput(){ MidOutput(m_pRoot);}void BinarySearchTree::Delete(int data){ Delete(m_pRoot,data);}void BinarySearchTree::Delete(BTreeNode* &pRoot, int data){ if(!pRoot) return; else if(data == pRoot->data){ if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr == NULL) // 叶子节点 { delete pRoot; pRoot = NULL; }else if(pRoot->pLeftPtr != NULL && pRoot->pRightPtr == NULL){ // 只有左子树 BTreeNode* pNode = pRoot->pLeftPtr; delete pRoot; pRoot = pNode; }else if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr != NULL){ // 只有右子树 BTreeNode* pNode = pRoot->pRightPtr; delete pRoot; pRoot = pNode; }else{ // 有左右子树 // 找到左子树的最大节点 BTreeNode* pCurrentNode = pRoot->pLeftPtr; BTreeNode* pParentNode = NULL; while(pCurrentNode->pRightPtr != NULL) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pRightPtr; } pRoot->data = pCurrentNode->data; if(pParentNode) { pParentNode->pRightPtr = pCurrentNode->pLeftPtr; }else{ pRoot->pLeftPtr= pCurrentNode->pLeftPtr; } delete pCurrentNode; } }else if(data < pRoot->data) Delete(pRoot->pLeftPtr, data); else Delete(pRoot->pRightPtr, data);}void main(){ int data[8]; cout<<"请输入整形数据, 数据用空格隔开, 回车键结束输入"<<endl; for(int i=0; i<8; i++) cin>>data[i]; // int data[8] = {13,15,6,20,14,5,7,18}; BinarySearchTree tree; tree.Create(data,sizeof(data)/sizeof(data[0])); cout<<"插入数据后的二叉树为: "<<endl; tree.MidOutput(); cout<<endl; int len_1=0; int len_2=0; tree.Find(14,&len_1); tree.Find(21,&len_2); tree.Delete(20); cout<<"删除数字20后的二叉树结果: "<<endl; tree.MidOutput(); cout<<endl; tree.Delete(15); cout<<"删除数字15后的二叉树结果: "<<endl; tree.MidOutput(); cout<<endl;}
Ⅹ 二叉树查找和二分查找是同一算法吗
两者的算法思路其实很像：比中间的小就在剩下的左边，大就在剩下的右边找
但是：
二叉树查找一般习惯是在链式存储上进行，为一个树形结构
二分查找一定在顺序存储上进行