精华内容
下载资源
问答
  • 2021-10-15 21:58:02

    判断一棵树是否为二叉排序树

    思路

    • 二叉排序树的中序遍历是有序的,所以判断一棵排序树可以进行中序遍历并且在遍历过程中判断是否有序。
    • 为此设置一个全局变量记录上一个中序遍历节点的值,遍历过程中与全局变量比大小并更新全局变量的值。

    实现

    #include<stdio.h>
    
    typedef struct node
    {
    	int data;
    	struct node *lchild;
    	struct node *rchild;
    }BTNode;
    
    int num=-32767;	//定义最小的全局变量 
    
    //中序遍历思想,并且更新全局变量的值 
    int Judge(BTNode *&p)
    {
    	int i; 
    	if(p==NULL) return 1;	//空节点则返回
    	
    	i=Judge(p->lchild);		//遍历并判断左子树是否满足二叉排序 
    	if(i==0) return 0;
    	
    	if(p->data>num)		//如果符合二叉排序树,更新全局变量的值 
    		num=p->data;
    	else			 
    		return 0;
    	
    	return  Judge(p->rchild);//最后判断右子树是否满足 
    } 
    
    更多相关内容
  • 代码里有二叉排序树插入操作递归算法,二叉排序树插入操作非递归算法,二叉排序树删除操作,创建二叉排序树二叉排序树查找递归算法,二叉排序树查找非递归算法
  • 。题目 给定个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由...二叉排序树的插入函数 遍历两树,每次判断遍历的相同位置的相同节点的data数据是不是一样。不管用什么前序,中序,

    一。题目
    给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。

    二、思路
    刚看这道题目输入样例没看懂,后来发现是“包含若干组测试用例”。。。
    整个题思路很简单,主要是两个函数

    1. 二叉排序树的插入函数
    2. 遍历两棵树,每次判断遍历的相同位置的相同节点的data数据是不是一样。不管用什么前序,中序,后序,层次遍历,都可以。这里方便就用的是前序遍历。

    三、代码

    #include<iostream>
    using namespace std;
    typedef struct TNode {
    	int data;
    	struct TNode *left;
    	struct TNode *right;
    }TNode;
    
    void insert(TNode *&L,int a)//插入节点
     {
    	if (L == NULL) {
    		L = (TNode *)malloc(sizeof(TNode));
    		L->left = NULL;
    		L->right = NULL;
    		L->data = a;
    		return;
    	}
    	if (a < L->data) {
    		insert(L->left, a);
    	}
    	else
    		insert(L->right, a);
    }
    bool isSame(TNode *T1, TNode *T2)//遍历,判断是否相同
     {
    	bool is1=false,is2=false;
    	if (T1 != NULL && T2 != NULL) {
    		if (T1->data != T2->data)return false;
    		is1=isSame(T1->left, T2->left);
    		is2 = isSame(T1->right, T2->right);
    		if (!is1 || !is2)return false;
    		else return true;
    	}
    	if (T1 == NULL && T2 == NULL)return true;
    	return false;
    }
    
    int main() {
    	int N, L,a;
    	cin >> N;
    	while (N) {
    		cin >> L;
    		TNode *Ts;
    		Ts = (TNode *)malloc(sizeof(TNode));
    		Ts = NULL;
    		for (int i = 0; i < N; i++) {
    			cin >> a;
    			insert(Ts, a);
    		}
    		for (int i = 0; i < L; i++) {
    			TNode *t;
    			t= (TNode *)malloc(sizeof(TNode));
    			t = NULL;
    			for (int j = 0; j < N; j++) {
    				cin >> a;
    				insert(t, a);
    			}
    			if(isSame(Ts, t))cout<<"Yes"<<endl;
    			else cout << "No" << endl;
    		}
    		cin >> N;
    	}
    	return 0;
    }
    
    展开全文
  • 建立一棵二叉排序树

    千次阅读 多人点赞 2019-06-03 23:53:28
    二叉排序树(也称二叉查找树),或者是一棵空的二叉树,或者是具有下列性质的二叉树: ⑴ 若它的左子树不,则左子树上所有结点的值均小于根结点的值; ⑵ 若它的右子树不,则右子树上所有结点的值均大于根结点的...

    定义

    二叉排序树(也称二叉查找树),或者是一棵空的二叉树,或者是具有下列性质的二叉树:
    ⑴ 若它的左子树不空,则左子树上所有结点的值均小于根结点的值;
    ⑵ 若它的右子树不空,则右子树上所有结点的值均大于根结点的值;
    ⑶ 它的左右子树也都是二叉排序树。
    中序遍历二叉排序树可以得到一个按关键码的有序数列。

    建树

    脱胎于二叉树,区别是每个节点数据要进行比对,再进行插入,小插左,大插右,直接上代码,清楚明白。

    #include<bits/stdc++.h>
    using namespace std;
    #define N 100
    
    typedef  struct BiTNode
    {
        char data;
        struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    
    BiTree root=NULL;
    int n,k[N];
    
    void inOrder(BiTree T)//中序遍历 
    {
    
    	if(T!=NULL)
    	{
    	  inOrder(T->lchild);//左 
    	  printf("%d ",T->data);// 根 
    	  inOrder(T->rchild);//右 
    	}
    }
    
    void insert(int m)
    {
    	BiTree p1, p2;
    	if(root==NULL)
    	{
    	  	root=new BiTNode;
    	  	root->data=m;
    	  	root->lchild=root->rchild=NULL;
    	}
    	else
    	{
    		p1=root;
    		while(m!=p1->data)
    		{
    		    if((m<p1->data) && (p1->lchild!=NULL))
    		    {
    		    	p1=p1->lchild;
    			}
    		    else if((m>p1->data) && (p1->rchild!=NULL))
    		    {
    		    	p1=p1->rchild;
    			}
    		    else if((m<p1->data) && (p1->lchild==NULL))
    		    {
    		      	p2=new BiTNode;
    		      	p2->data=m;
    		      	p2->lchild=p2->rchild=NULL;
    		      	p1->lchild=p2;
    		      	return;
    		    }
    		    else if((m>p1->data) && (p1->rchild==NULL))
    		    {
    		      	p2=new BiTNode;
    		      	p2->data=m;
    		      	p2->lchild=p2->rchild=NULL;
    		      	p1->rchild=p2;
    		      	return;
    		    }
    		}
    	}
    }
    
    void create()
    {
    	cout<<"输入节点数量:";
    	cin>>n;
    	for(int i=0; i<n; i++)
    	{
    		cin>>k[i];
    	}
    	for(int i=0; i<n; i++)
    	{
    		insert(k[i]);
    	}
    }
    
    int main()
    {
    	create();
    	cout<<"中序遍历输出:"<<endl; 
    	inOrder(root);
    	return 0;
    }
    
    展开全文
  • 二叉排序树

    千次阅读 2021-08-22 22:25:22
    Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){ //在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素,若查找成功 //则指针p指向该数据元素结点,并返回TRUE,否则指针p指向查找路径...

     


     
     

      

    二叉排序树

      二叉排序树: 或者是一棵空树;或者是具有下列性质的二叉树:(1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)它的左、右子树也分别为二叉排序树。
    二叉排序树示例
     
     

    二叉排序树插入

    查询

      二叉排序树又称二叉查找树,根据上述定义的结构特点可见。即当二叉排序树不空时,首先将给定值和根结点的关键字比较,若相等,则查找成功,否则将依据给定值和根结点的关键字之间的大小关系,分别在左子树或右子树上继续进行查找。

    Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){
    	//在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素,若查找成功 
    	//则指针p指向该数据元素结点,并返回TRUE,否则指针p指向查找路径上访问的 
    	//最后一个结点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL 
    	if(!T){//查找不成功 
    		p = f;
    		return FALSE;
    	}
    	else if EQ(key, T->data.key){//查找成功 
    		p = T;
    		return TRUE;
    	}
    	else if LT(key, T->data.key)//在左子树中继续查找 
    		return SearchBST(T->lchild, key, T, p);
    	else	//在右子树中继续查找 
    		return SearchBST(T->rchild, key, T, p);
    }
    

     

    查找分析

    示例
    6 个记录的查找概率相等=1/6
    (a)树平均查找长度:ASL(a) = (1+2+2+3+3+3)/6 = 14/6
    (b)树平均查找长度:ASL(b) = (1+2+3+4+5+6)/6 = 21/6
    所以含有 n 个结点的二叉排序树的平均平均查找长度和树的形态有关。
    最差情况:二叉树排序树为单只树,平均查找长度与顺序查找相同 (n+1)/2
    最好情况:与折半查找的判断树相同,平均查找长度与 log2n 成正比

    P(n) ≤ 2(1+1/n)ln n
     

    插入

      树的结构不是一次生成的,而是在查找过程中,在树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点,并且是查找不成功是查找路径上访问的最后一个一节点的左孩子或右孩子。

    Status InsertBST(BiTree &T, ElemType e){
    	//当二叉排序树T中不存在关键字等于e.key的数据元素时,插入e并返回TRUE 
    	//否则返回FALSE 
    	if(!SearchBST(T, e.key, NULL, p)){//查找不成功 
    		s = (BiTree)malloc(sizeof(BiTNode));
    		s->data = e;	s->lchild = s->rchild = NULL;
    		if(!p)//被插结点*s为新的根结点 
    			T = s;
    		else if LT(e.key, p->data.key)//被插结点*s为左孩子 
    			p->lchild = s;
    		else//被插结点*s为右孩子 
    			p->rchild = s;
    		return TRUE;
    	}
    }
    

     

    建立

      从空树出发,经历一系列的查找插入操作之后,可生成一棵二叉树
      设查找序列为{45,24,53,45,12,24,90},生成二叉排序树过程如下:
    建树过程
      可以看出,中序遍历二叉排序树可得到一个关键字的有序序列。
     
     

    二叉排序树删除

      对于二叉排序树,删去树上一个结点相当于删去有序序列中的一个记录,只要在删除某个结点之后依旧保持二叉排序树的特殊即可。
      假设在二叉排序树上被删结点为 *p(指向结点的指针为 p),其双亲结点为 *f(结点指针为 f),且不失一般性,可设 *p 是 *f 的左孩子。
      下面分 3 种情况进行讨论:
      (1) 若 *p 结点为叶子结点,即 PL 和 PR 均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。
      (2) 若 *p 结点只有左子树 PL 或者只有右子树 PR,此时只要令 PL 或 PR 直接成为其双亲结点 *f 的左子树即可。显然,作此修改也不破坏二叉排序树的特性。
      (3) 若 *p 结点的左子树和右子树均不空。显然,此时不能如上简单处理。从下图中(b)可知,在删去 *p 结点之前,中序遍历该二叉树得到的序列为{…CLC…QLQSLSPPRF…},在删去 *p 之后,为保存其他元素之间的相对位置不变,可以有两种做法:其一是令 *p 的左子树为 *f 的左子树,而 *p 的右子树为 *s 的右子树,如下图©;其二是令 *p 的直接前驱(或直接后继)替代 *p,然后再从二叉排序树中删去它的直接前驱(或直接后继)。如下图(d)所示,当以直接前驱 *s 替代 *p 时,由于 *s 只要左子树 SL,则在删去 *s 之后,只要令 SL 为 *s 的双亲 *q 的右子树即可。
    在这里插入图片描述

    Status DeleteBST(BiTree &T, KeyType key){
    	//若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点 
    	//并返回TRUE;否则返回FALSE 
    	if(!T)//不存在关键字等于key的数据元素 
    		return FALSE;
    	else{
    		if(EQ(key, T->data.key))//找到关键字等于key的数据元素 
    			return Delete(T);
    		else if(LT(key, T->data.key))
    			return Delete(T->lchild, key);
    		else
    			return Delete(T->rchild, key);
    	}
    }
    
    Status Delete(BiTree &p){
    	//从二叉排序树中删除结点p,并重接它的左或右子树 
    	if(!p->rchild){//右子树空则只需重接它的左子树 
    		q = p;
    		p = p->lchild;
    		free(q);
    	}
    	else if(!p->lchild){//只需重接它的右子树 
    		q = p;
    		p = p->rchild;
    		free(q);
    	}
    	else{//左右子树均不空 
    		q = p;
    		s = p->lchild;
    		while(s->rchild){//转左,然后向右到尽头 
    			q = s;
    			s = s->rchild;
    		}
    		p->data = s->data;//s指向被删结点的“前驱” 
    		if(q != p)//重接*q的右子树 
    			q->rchild = s->lchild;
    		else//重接*q的左子树 
    			q->lchild = s->lchild;
    		delete s;
    	}
    	return TRUE;
    }
    

     
     

    展开全文
  • 二叉排序树详解

    千次阅读 2022-04-01 16:49:31
    摘要:本篇笔记专门介绍二叉排序树,重点讲解了二叉排序树的特性,以及二叉排序树各方面的基本实现。
  • 《数据结构》实验报告班级:姓名:学号:E-mail:日期:◎实验题目: 建立二叉排序树...、需求分析1、本程序,输入组数据,然后建立一棵二叉排序树存储这些元素,再中序遍历输出检验树建立是否正确,中序遍历输出的...
  • 二叉排序树1、定义2、性质3、操作3.1 查找 ...(3)其左右子树本身又各是一棵二叉排序树。 \quad \quad总结起来就是根据结点的值有:左子树<根结点<右子树 \quad \quad如下图就是一棵二叉排序树: \quad
  • 二叉排序树(BST)

    2021-06-18 17:00:35
    二叉排序树(也称二叉查找树)。 性质:左子树结点值 < 根结点值 < 右子树结点值 所以对二叉排序树进行中序遍历,可以得到个递增的xu'l
  • 1二叉排序树 二叉排序树:BST( Binary Sort( Search)Tree,又称二叉查找树(Binary Search Tree),亦称二叉搜索树。对于二叉排序树的任何个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前...
  • 【数据结构】二叉排序树(C语言版)前言二叉排序树的定义二、二叉排序树的性质三、二叉排序树的操作二叉排序树常用存储结构二叉排序树的查找(递归实现)查找"二叉树T"键值为 key 的节点(非递归实现)查找"二叉树...
  • 二叉排序树,又称二叉查找树(BST(Binary Sort/Search Tree) )或者是一棵空树,或者是具有下列特性的二叉树: (1)若左子树非空,则左子树上所有结点的值均小于根结点的值。 (2)若右子树非空,则右子树删所有...
  • 树与二叉树——二叉排序树

    千次阅读 2019-04-15 09:19:15
    1.二叉排序树的定义 二叉排序树1)或者是一棵空树。 2)或者是具有下列性质的二叉树: [1]若它的左子树不,则左子树上所有的结点的值都小于它的根节点的值; [2]若它的右子树不,则右子树上所有的结点的...
  • 二叉排序树总结

    2022-03-17 19:25:19
    二叉排序树或者是一棵空树,或者是具有下列性质的二叉树: 左子树上所有结点的值均小于根结点的值; 右子树的所有结点的值均大于根结点的值; 他的左右子树也分别都是二叉排序树二叉排序树的查找过程 首先和根...
  • //插入到右子树中 } 二叉搜索树的生成 二叉排序树的生成,是从树开始,每插入个关键字,就调用次插入算法将它插入到当前已生成的二叉排序树中。 BSTNode *CreatBST(KeyType A[],int n) //返回树根指针 { ...
  • 什么是二叉排序树(BST) 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。在一般情况下,查询效率比链表结构要高。 要求:对于二叉树的任何个非叶子结点,要求左子结点...
  • 树-二叉排序树的构建

    2022-04-01 17:32:36
    二叉排序树介绍 二叉排序树:对于二叉排序树的任何个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。 特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点 、...
  • 删除二叉排序树中个节点 假设被删结点是p,其双亲是f,设p是f的左孩子,三种情况 若结点p是叶子结点,则只需修改其双亲结点f的指针即可。 若结点*p只有左子树PL或者只有右子树PR,则只要使PL或PR 成为其双亲...
  • 题目:设计个算法,求出指定节点在给定二叉排序树中的层次 分析: 我们可以根据二叉排序树的性质,从根节点一直向下查找,每查找次,层次便加一 typedef struct node { int data; node *left, *right; }...
  • C语言实现二叉排序树

    2022-03-02 17:39:50
    C语言实现二叉排序树
  • 它或则是树,或者是带有以下性质的二叉树:构造二叉排序树的目的,并不是为了顺序,而是为了提升查找和插入删除关键字的速度。以下程序在DEV C++安装运行通过。#include#include/*二叉树的二叉链表结点结构...
  • 二叉排序树的建立

    千次阅读 2022-05-08 21:30:59
    1) 将第个要创建的元素插入成为根节点。 2) 将元素值与结点值比较,如果元素值大于结点值,将此元素送往结点的右儿子结点,如果右儿子结点不是的,需要重复比较,否则创建结点将元素值插入。 3)如果元素值小于...
  • 我们在上篇博客讲解了二叉树,这次我们来实现二叉树的...  二叉排序树个重要特点是中序遍历是个递增序列。示例代码上传至: https://github.com/chenyufeng1991/BinarySearchTree 。  (1)节点的构造
  • 文章目录数据结构C++——二叉排序树一、前言二、二叉排序树的相关概念三、树表的查找①二叉排序树的存储表示②二叉排序树的递归查找③二叉排序树的插入④二叉排序树的创建⑤二叉排序树的删除四、完整测试代码五、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,965
精华内容 17,586
关键字:

一棵空的二叉排序树中