动态查找——二叉排序树

1.问题描述：

判别一棵二叉树是否为二叉排序树，如果是，在其上实现查找功能。

2.实验要求：

（1）以二叉链表为存储结构，创建二叉树；

（2）设计判别算法；

（3）输入所要查找表的数据；

（4）输出判别结果；

3.程序实现：

(1)代码：

#include using namespace std;int i = 0;typedef struct BitNode {    int data;    struct BitNode* lchild, * rchild;}BitNode, * BiTree;//二叉排序树的创建void insert(BitNode*& p, int a)//引用型，需要改变p的内容{if (p == NULL)//找到了空指针，存放关键字{p = new BitNode;p->data = a;p->lchild = NULL;p->rchild = NULL;}else if (p->data rchild, a);}else//否则左子树{insert(p->lchild, a);}}//利用数组依次输入二叉排序树的结点元素值void createBst(BitNode*& T, int a[], int n) {T = NULL;cout << "输入结点值：";int i;for (i = 0; i > a[i];insert(T, a[i]);}}//中序遍历void inOrderTraverse(BiTree T){if (T){inOrderTraverse(T->lchild);cout<data<rchild);}}//查找给定的元素void searchBst(BiTree T, int key) {//记录第几次查找到 ++i;if (T) {if (key == T->data) {cout<<"第"<<i<<"次查询\n";cout<<"查得："<data;}else if (key data)   //所查值lchild, key);else      //所查值>根值，右子树上进行查找searchBst(T->rchild, key);}}int main(){int a[100];BiTree T;int n; cout <> n;createBst(T, a, n);cout << "中序遍历结果：";inOrderTraverse(T);cout << endl;cout << "二叉排序树的判断：yes\n";//判断结果必定为yes，因为此代码在输入元素的同时就创建二叉排序树int b;cout <> b;searchBst(T, b);return 0;}

 (2)建立的模型及存储结构：

以二叉链表为存储结构直接创建二叉排序树。该程序未创建二叉树，再判断二叉树是否是二叉排序树。

若要先创建二叉树再判断，可以用如下方法：

（1）中序遍历二叉树的同时，用数组b记录每一次遍历的元素。然后判断数组b是否是升序，如果符合升序，则该二叉树为二叉排序树。

int i=0;int b[100];int t;~~~~~~~~~~void inOrderTraverse(BiTree T){if (T){inOrderTraverse(T->lchild);cout<data<data;i++;inOrderTraverse(T->rchild);}}void judge(b){   for(int j=0;jb[j+1])      {cout<<"NO"<<endl;t=0}}int main(){~~~~~void judge(b)if(!t)cout<<"YES"<<endl;~~~~~}

（2）比较二叉树每个结点是否符合左子树<根<右子树。

int SelectBinSortTree(BinTreeNode *T)//判断是否为二叉排序树{    if(T==0) return 1;    else if(T->Lchild&&T->Rchild)    { if(T->dataLchild->data||T->data>T->Rchild->data) return 0; else return(SelectBinSortTree(T->Lchild)&&SelectBinSortTree(T->Rchild));    }    else if(T->Lchild)    { if(T->dataLchild->data) return 0; else return(SelectBinSortTree(T->Lchild));    }    else if(T->Rchild)    { if(T->dataRchild->data) return 0; else return(SelectBinSortTree(T->Rchild));    }    return 1;}

4.测试与运行：

 (1)查找50:

 (2)查找40:

  5.思考题：

（1）若二叉排序树各个结点的值都不相同，试设计算法，按升序打印出该二叉树各个节点的值。

void inOrderTraverse(BiTree T){if (T){inOrderTraverse(T->lchild);cout<data<rchild);}}

（2）计算二叉排序树的平均查找长度。

查找成功的平均查找长度为：∑（本层高度*本层元素个数）/节点总数

查找不成功的平均查找长度：∑（本层高度*本层补上的叶子个数）/补上的叶子总数

 查找成功的平均查找长度为：（1+2*2+3*3）/6

查找不成功的平均查找长度：（2+3*6）/7

6.实验心得体会：

熟悉二叉排序树的创建，查找，删除，插入。知道如何定义节点结构。

typedef有取别名的作用，所以BitNode的意思是struct BitNode{...)，BiTree的意思是struct BitNode{...)*。

BiTree &T 是取指针地址的意思，如同int  &a，取a得地址一样。

BitNode *T  和  BiTree T 是定义结构指针变量。

参数BiTree &T也可用写成BitNode *(&T)

开发者涨薪指南 48位大咖的思考法则、工作方式、逻辑体系