精华内容
下载资源
问答
  • 编写一个采用二叉链式结构做存储结构的二叉排序树建立和查找算法
  • 二叉排序树建立及中序遍历,数据结构作业
  • 《数据结构》实验报告班级:姓名:学号:E-mail:日期:◎实验题目: 建立二叉排序树...一、需求分析1、本程序中,输入一组数据,然后建立一棵二叉排序树存储这些元素,再中序遍历输出检验树建立是否正确,中序遍历输出的...

    《数据结构》实验报告

    班级:姓名:学号:E-mail:日期:

    ◎实验题目: 建立二叉排序树,并中序遍历输出,输入一个关键字进行查找。 ◎实验目的:熟悉并掌握二叉排序树的建立及遍历输出以及非递归查找。

    ◎实验内容:输入一组数据,建立二叉排序树,并中序遍历输出,输入一个关键字进行查找。

    一、需求分析

    1、本程序中,输入一组数据,然后建立一棵二叉排序树存储这些元素,再中序遍历输出检验树建立是否正确,中序遍历输出的次序应为从小到大排列,然后输入一个关键字查找,输出查找成功与否。

    2、演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入相应数据。

    3、程序所能达到的功能:建立二叉排序树,并中序遍历输出,输入一个关键字进行查找。

    4、测试数据:

    输入待排序的数据:10 15 20 5 10 30 9 7 13 45 2 -1(-1是输入结束标志) 中序遍历二叉树输出为:2 5 7 9 10 10 13 15 20 30 45

    输入要查找的元素:7

    输出:查找成功

    二 概要设计

    为了实现上述操作,应以二叉链表为存储结构,中序非递归遍历时以栈为中间存储结构。 该程序有四个函数分别为:主函数,插入函数,输出函数,查找函数。主函数通过调用其他三个函数实现上述功能。

    三 详细设计

    1、定义节点类型

    typedef struct node

    {

    int data;

    struct node *lc;

    struct node *rc;

    }BiTNode,*BiTree;

    2、主函数

    定义二叉排序树根节点bt,以及整形变量,x待插入数据变量,k查找关键字变量。二叉排序树 建立读取输入的数据存入x中,如果不是结束标志-1就调用插入函数将x插入到二叉排序树中,否则就执行后续操作。然后调用输出函数中序输出二叉排序树。二叉排序树 建立输出待查找的数据存入k中。调用查找函数进行查找。根据返回的指针判断查找成功与否。

    3、插入函数

    定义指向待插入节点指针q以及指向当前节点指针p,以及整形变量i用于判断插入成功与否。

    q指向新申请节点,并将待插入数据存入数据项中。当树为空时,直接将节点插入到根节点。否则待插入节点与根节点进行比较:如果小于根节点,沿左孩子链进行比较,否则沿右孩子链进行比较。直到终端插入该节点。

    4、中序遍历函数

    当前结点等于根结点.

    初始化栈。

    当栈不空或者当前结点不空时while循环:

    当p不空时进栈,然后沿左孩子路径访问,直至p为空;

    此时让p等于栈顶指针,输出p的数据域的值;

    当输出了父结点后沿右孩子路径访问。

    5、查找函数

    定义指向当前节点指针p,并使p指向根节点。当p不空且还未查找到关键字与根节点进行比较。若大于根节点沿右孩子链查找,否则沿左孩子链进行查找。返回指针p。

    四 使用说明、测试分析及结果

    1、测试结果

    输入待排序的数据:10 15 20 5 10 30 9 7 13 45 2 -1(-1是输入结束标志) 中序遍历二叉树输出为:2 5 7 9 10 10 13 15 20 30 45

    输入要查找的元素:7

    输出:查找成功

    符合预期设想

    3.运行界面

    五、实验总结

    在进行这次试验前,我首先写了实验预习报告,用了大概半小时时间写出了解决此问题的大体算法,并且用了半小时时间把具体的设计写了出来,要用了一个小时进行了调试。在进行测试的时候,发现查找的元素不在二叉树中出来的结果是查找成功,最后检查发现时判断条件的时候把等于打成了赋值。做了这么多实验我的细心程度还是达不到期望值。这是我以后实验中特别要注意的地方。 教师评语:

    实验成绩:

    指导教师签名:

    本文来自电脑杂谈,转载请注明本文网址:

    http://www.pc-fly.com/a/jisuanjixue/article-25005-1.html

    展开全文
  • 代码里有二叉排序树插入操作递归算法,二叉排序树插入操作非递归算法,二叉排序树删除操作,创建二叉排序树二叉排序树查找递归算法,二叉排序树查找非递归算法
  • 二叉排序树又称二叉查找树。本文主要对二叉排序树的实现与基本操作进行详细介绍,以下代码实现了:1、二叉树的构建;2、二叉树的中、前、后、层序遍历;3、二叉树中结点的最大距离。下面就跟着小编一起来看下吧
  • 二叉排序树

    2018-12-19 17:14:07
    任意给定一组数据, 设计一个算法, 建立一棵二叉排序树, 对它进行查找、 插入、删除等操作。
  • /*生成二叉排序树*/ } fclose(fp); inorder(bst); /*输出二叉排序树*/ putchar(' '); scanf("%d",&i); /*输入需要查找的数字*/ if (ser(bst,i)) printf("YES"); /*如果找到,则输出yes,否则输出no*/ else printf(...

    //---------------------------------------------------------------------------

    #include

    #include

    typedef struct np{

    int dat;

    struct np *left,*right;

    } node;

    node *create(void)

    {

    return (malloc(sizeof(node)));

    }

    node *t(node *a,int d)

    {

    if (a==NULL) {

    a=create();

    a->left =a->right =NULL;

    a->dat=d;

    }

    else if (d>=a->dat) {

    a->right =t(a->right,d);

    }

    else if (ddat) {

    a->left =t(a->left ,d);

    }

    return a;

    }

    void inorder(node *r)

    {

    if (r!=NULL) {

    inorder(r->left );

    printf("%d ",r->dat );

    inorder(r->right );

    }

    }

    int ser(node *so,int a)

    {

    if (so==NULL)

    return 0;

    else if (so->dat==a)

    return 1;

    else if (a>so->dat)

    return ser(so->right,a);

    else if (adat)

    return ser(so->left ,a);

    }

    int main(int argc, char* argv[])

    {

    node *bst=NULL;

    FILE *fp;

    int i;

    fp=fopen("c:\dat。

    txt","r"); /*假设数据文件是c:dat。

    txt*/

    while (!feof(fp)){

    fscanf(fp,"%d",&i);

    bst=t(bst,i); /*生成二叉排序树*/

    }

    fclose(fp);

    inorder(bst); /*输出二叉排序树*/

    putchar('

    ');

    scanf("%d",&i); /*输入需要查找的数字*/

    if (ser(bst,i)) printf("YES"); /*如果找到,则输出yes,否则输出no*/

    else printf("NO");

    return 0;

    }

    //---------------------------------------------------------------------------。

    全部

    展开全文
  • #include#include"fatal.h"structTreeNode;typedefstruct TreeNode *Position;typedefstruct TreeNode *SearchTree;typedefintElementType;SearchTree MakeEmpty(SearchTree T);Position Find(ElementType X,SearchT...

    #include#include"fatal.h"

    structTreeNode;

    typedefstruct TreeNode *Position;

    typedefstruct TreeNode *SearchTree;

    typedefintElementType;

    SearchTree MakeEmpty(SearchTree T);

    Position Find(ElementType X,SearchTree T);

    Position FindMin(SearchTree T);

    Position FindMax(SearchTree T);

    SearchTree Insert(ElementType X,SearchTree T);

    SearchTree Delete(ElementType X,SearchTree T);

    ElementType Retrieve(Position P);structTreeNode

    {

    ElementType Element;

    SearchTree left;

    SearchTree right;

    };

    SearchTree MakeEmpty(SearchTree T)

    {if(T!=NULL)

    {

    MakeEmpty(T->left);

    MakeEmpty(T->right);

    free(T);

    }returnNULL;

    }

    Position Find(ElementType X,SearchTree T)

    {if(T==NULL)returnNULL;if(XElement)return Find(X,T->left);else if(X>T->Element)return Find(X,T->right);else

    returnT;

    }

    Position FindMin(SearchTree T)

    {if(T==NULL)returnNULL;if(T->left==NULL)returnT;else

    return FindMin(T->left);

    }

    Position FindMax(SearchTree T)

    {if(T==NULL)returnNULL;else if(T->right==NULL)returnT;else

    return FindMax(T->right);

    }

    SearchTree Insert(ElementType X,SearchTree T)

    {if(T==NULL)

    {

    T=malloc(sizeof(structTreeNode));if(T==NULL)

    FatalError("Out of space!!!");else{

    T->Element=X;

    T->left=T->right=NULL;

    }

    }else if(XElement)

    T->left=Insert(X,T->left);else if(X>T->Element)

    T->right=Insert(X,T->right);returnT;

    }

    SearchTree Delete(ElementType X,SearchTree T)

    {

    Position TmpCell;if(T==NULL)

    Error("Error not found");else if(XElement)

    T->left=Delete(X,T->left);else if(X>T->Element)

    T->right=Delete(X,T->right);else if(T->left&&T->right)

    {

    TmpCell=FindMin(T->right);

    T->Element=TmpCell->Element;

    T->right=Delete(X,T->right);

    }else{

    TmpCell=T;if(T->left==NULL)

    T=T->right;else if(T->right=NULL)

    T=T->left;

    free(TmpCell);

    }returnT;

    }

    ElementType Retrieve(Position P)

    {if(P==NULL)return -1;else

    return P->Element;

    }

    展开全文
  • 数据结构之二叉排序树建立

    万次阅读 多人点赞 2018-06-12 18:57:15
    一、普通二叉树的建立 提到二叉树的建立,就不得不提一下“递归”,建立二叉树所采用的思想就是递归。递归基本形式: void recursion() { if(递归结束条件) { 表达式 } else { 表达式; recursion(); ...

    一、普通二叉树的建立

        提到二叉树的建立,就不得不提一下“递归”,建立二叉树所采用的思想就是递归。

    递归基本形式:  

    void recursion()
    {
    	if(递归结束条件)
    	{
    		表达式
    	}
    	else
    	{
    		表达式;
    		recursion();
    	}
    }

        有了递归思想后,我们如何建立二叉树呢?比如建立如图的二叉树:


    问题:发现此二叉树并不是完全二叉树,有的只有右孩子没有左孩子,这样的话,可以在输入时人为的假定一个虚拟的空孩子比如用65535表示空结点,具体如下:

    代码实现:

    /*****************普通二叉树的建立与遍历************/
    void CreateBiTree(tNode *T)     /*二叉树的建立*/
    {
    	int ch;
    	scanf("%d", &ch);
    	if(0 == ch)
    		*T = NULL;
    	else
    	{
    		*T = (tNode)malloc(sizeof(node));
    		if(!*T)
    			exit(OVERFLOW);
    		(*T)->data = ch;  
    		CreateBiTree(&(*T)->lchild);  //构造左子树
    		CreateBiTree(&(*T)->rchild);    //构造右子树
    	}		
    }

    二、二叉排序树的建立

        二叉排序树的建立比普通二叉树多了一点就是在建立的过程中需要对插入进来的数据进行大小的判断,但是就是因为多了这么一点,所以不能在递归的过程中去输入数据并插入,而是应该先输入数据,再将数据插入。

        插入的过程中要将数据与树的根结点的值开始比较知道找到合适的位置插入,所以在插入数据的这一部分代码中可以使用递归算法。

                          

    实现代码:

    void creatBT(tNode *tree)   
    {
    	*tree = (tNode)malloc(sizeof(node));  //这已经给他的左右孩子分配了内存地址,所以要将他的左右孩子只想NULL
    	(*tree)->lchild = NULL;
    	(*tree)->rchild = NULL;
    	
    	int c ;
    	scanf("%d",&c);
    	
    	if((*tree) != NULL && 65535 != c)   //以65535为结束标志
    		(*tree)->data = c;   //创建根节点
    		
    
    	while(65535 != c)
    	{
    		scanf("%d",&c);
    		if((*tree) != NULL && 65535 != c)	
    			insertChild(tree, c);
    	}
    
    }
    
    //写一个函数专门插入子孩子,采用递归,从根节点开始寻找合适的插入点
    void insertChild(tNode *tree, int c)
    {
    	if(c < (*tree)->data)  
    	{
    		if( (*tree)->lchild == NULL )   //如果没有左孩子,直接将值赋给左孩子
    		{
    			(*tree)->lchild = (tNode)malloc(sizeof(node));  //这已经给他的左右孩子分配了内存地址,所以要将他的左右孩子只想NULL
    			((*tree)->lchild)->lchild = NULL;
    			((*tree)->lchild)->rchild = NULL;
    
    			(*tree)->lchild->data = c;
    		}
    			
    	
    		else
    		{
    			insertChild(&((*tree)->lchild),c);		
    		}
    	}
    	
    	else
    	{
    		if( (*tree)->rchild == NULL )   //如果没有左孩子,直接将值赋给左孩子
    		{
    			(*tree)->rchild = (tNode)malloc(sizeof(node));   //这已经给他的左右孩子分配了内存地址,所以要将他的左右孩子只想NULL
    			((*tree)->rchild)->lchild = NULL;
    			((*tree)->rchild)->rchild = NULL;
    
    			(*tree)->rchild->data = c;
    		}
    			
    			
    		else
    		{
    			insertChild(&((*tree)->rchild),c);		
    		}
    	}
    }

    展开全文
  • 接着我们来从头建立一颗二叉搜索 1. 设计二叉搜索类 这里我们先定义节点类,并设计它的构造方法 这里让二叉搜索类的泛型T 继承 Comparable接口(接口是可以被继承的),目的是为了实现一些比较的算法 然...
  • 6.2_二叉排序树.cpp

    2019-10-29 19:19:22
    3、 建立二叉排序树和在二叉排序树上查找指定结点,如果查找成功打印出位置和比较次数,如果查找失败,则打印查找失败信息。 4、 修改3的程序,如果查找失败,则将结点插入到二叉排序树上。 5、 修改3的程序,如果...
  • 生成二叉排序树就是在一个空树中不断地执行 二叉排序树插入操作。 二叉排序树插入操作算法思想如下: 因此,二叉排序树生成算法为: //二叉排序树的插入操作 void InsertBST_Real(BSTree& T, keytype key) { ...
  • 二叉排序树建立(JAVA实现)

    千次阅读 多人点赞 2016-12-01 11:17:25
    最近看了一下二叉排序树建立,自己写了一段代码,用来建立二叉排序树,给定一个数组,对这个数组中的数字进行建立二叉排序树。分两种情况:  1 数组中的数字是随机的,也就是说没有顺序 eg : int a [ ] = {3,1,2,...
  • /*声明新类型的结构*/ typedef treenode *b_tree; /*声明二叉树的链表*/ b_tree insert_node(b_tree root,int node) /*插入二叉树的结点*/ {b_tree newnode; b_tree currentnode; b_tree parentnode; newnode=(b_...
  • 二叉树 非递归 先中后序遍历 通讯录 数据结构作业
  • 二叉排序树的创建和节点删除

    千次阅读 2019-10-17 20:49:56
    二叉排序树-BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。 例如对于一批数据 (7, 3, 10, 12, 5, 1, 9) 对应的二叉排序...
  • (1)因为二叉排序树的中序遍历是一个有序递增序列,可以对已经建立的二叉树进行中序遍历,如果满足则判断是 三、二叉排序树的创建(creat、insert) 树结点的结构体: struct tree{ int data; struc...
  • //3.2,如果该节点的右子的最小节点有一个右子节点, // 则先将这个右子的最小节点上位到该节点的位置, // 然后将这个右子的最小节点的右子节点上位到这个右子的最小节点的位置; //写不下去了,就这吧......
  • 二叉排序树的基本算法实现

    千次阅读 2019-12-28 11:15:27
    二叉排序树的基本算法实现 实验目的: 用二叉链表存储方式存储二叉排序树,并实现以下相关算法 1、创建二叉排序树 2、在二叉排序树上实现查询、插入和删除算法 3、对二叉排序树进行中序遍历以判断目标2是否完成 ...
  • 在分析treemap时,分析到了红黑树,而红黑树是由二叉排序树变体产生的,因此学习二叉排序树是常用树的基础;本篇文章主要分析二叉排序树的构建 ,及原理解析,遍历方式。
  • 二叉排序树插入

    2013-08-25 16:06:09
    二叉排序树插入
  • 二叉排序树图解

    千次阅读 2019-08-13 23:14:19
  • 二叉排序树相关操作

    2013-08-03 21:13:42
    二叉排序树的相关操作 有删除,插入,查找,遍历(递归与非递归)等操作!
  • 建立二叉排序树

    2021-01-11 23:02:19
    编写算法,输入一组整数,以9999为结束标志,将这些数据建立二叉排序树。输出中序排序序列检验是否为二叉排序树,并且在二叉排序树内查找值。 #include<iostream> using namespace std; struct BiNode { int ...
  • 二叉排序树建立(插入)出现相同值的处理 什么是二叉排序树(二叉搜索树) 二叉排序树(二叉搜索树)(Binary Sort Tree)或者是一颗空树;或者是具有下列性质的二叉树: (1)若左子树不为空,则左子树上所有结点的值...
  • 算法思想: 二叉排序树的中序遍历是有序(从小到大的)的我们只要按照二叉树中序输出的递归代码模板每次输出是与上一次输出的进行比较即可 注意:二叉树中序递归模板见----->传送门 int JudgeBST(BSTree *root){...
  • 本程序实现了二叉排序树建立,插入和删除结点等操作,经调试无误
  • 二叉排序树的判定

    2021-06-01 22:13:02
    试写一个判别给定二叉树是否为二叉排序树的算法。以前序遍历序列和中序遍历序列给出该二叉树的结点,并创建该二叉树。然后再进行判断。请注意,树中结点关键字可能相同。 【样例输入1】 6 4 5 8 6 9 0 4 5 6 6 8 9 0...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,894
精华内容 10,757
关键字:

二叉排序树的建立