精华内容
下载资源
问答
  • 算法思想: 二叉排序树的中序遍历是有序(从小到大的)的我们只要按照二叉树中序输出的递归代码模板每次输出是与上次输出的进行比较即可 注意:二叉树中序递归模板见----->传送门 int JudgeBST(BSTree *root){...

    算法思想: 二叉排序树的中序遍历是有序(从小到大的)的我们只要按照二叉树中序输出的递归代码模板每次输出是与上一次输出的进行比较即可
    注意:二叉树中序递归模板见----->传送门

    int JudgeBST(BSTree *root){
    
    	if(root==NULL){   //空树是二叉排序树
    		return 1;
    	}
    
    	int a=JudgeBST(root->lchild); //判断左子树是否是二叉排序树
    		
    	if(root->data<=pre||a==0){ //左子树不是二叉排序树 
    		return 0; //如果其中的一颗子树不是二叉排序树那么 这个0就是一直被向上抛出到最上面的出口
    	}else{
    		pre=root->data;
    	}
    	int b=JudgeBST(root->rchild);//判断右子树是否是二叉排序树
    
    	return b;//这里的直接返回的原因是走到了这里左子树肯定是二叉排序树了对于整颗子树是不是二叉排序树只需要知道他的右子树是不是就行 所以直接返回结果就可以判断是不是二叉排序树了
    }
    
    

    对于递归代码不要想的太多只需要考虑“大局”,以及其中的一个子问题或者说临界点就行了不然就会陷进去浪费时间。

    展开全文
  • * 判断一个序列是否二叉排序树中的一个合法的查找序列 * 实验目的: * 掌握二叉排序树查找过程及其算法设计 * 实验内容: * 设计程序,构造一颗二叉排序树bt,判断一个序列a是否是 * 二叉排序树bt中的一个合法的查找...

    /**
    *    实验题目:
    *        判断一个序列是否是二叉排序树中的一个合法的查找序列
    *    实验目的:
    *        掌握二叉排序树查找过程及其算法设计
    *    实验内容:
    *        设计程序,构造一颗二叉排序树bt,判断一个序列a是否是
    *    二叉排序树bt中的一个合法的查找序列。
    */

    #include <stdio.h>
    #include <stdbool.h>
    #include <malloc.h>

    #define MAX_SIZE 100

    typedef int key_type;           // 定义关键字类型
    typedef char info_type;
    typedef struct node {           // 记录类型
        key_type key;               // 关键字项
        info_type data;             // 其他数据域
        struct node *lchild;        // 左孩子指针
        struct node *rchild;        // 右孩子指针
    }BSTNode;

    /*----------------以括号表示法输出二叉排序树bt------------------*/
    void disp_bst(BSTNode *bt);         // 函数声明

    bool insert_bst(BSTNode *&bt, key_type key) // 在以bt为根结点的BST中插入一个关键字为key的结点
    {
        if(bt == NULL)      // 原树为空,新插入的记录为根结点
        {
            bt = (BSTNode *)malloc(sizeof(BSTNode));
            bt->key = key;
            bt->lchild = bt->rchild = NULL;
            return true;
        }
        else if(key == bt->key)
            return false;
        else if(key < bt->key)
            return insert_bst(bt->lchild, key);     // 插入到bt结点的左子树中
        else
            return insert_bst(bt->rchild, key);     // 插入到bt结点的右子树中
    }

    /*----------------由数组a中的关键字建立一颗二叉排序树------------------*/
    BSTNode *create_bst(key_type a[], int n)
    {
        BSTNode *bt = NULL;         // 初始时bt为空树
        int i = 0;

        while(i < n)
        {
            if(insert_bst(bt, a[i]) == 1)       // 将a[i]插入二叉排序树bst中
            {
                printf("     第%d步,插入%d:", i + 1, a[i]);
                disp_bst(bt);
                printf("\n");
                i++;
            }
        }

        return bt;
    }


    /*----------------以括号表示法输出二叉排序树bt------------------*/
    void disp_bst(BSTNode *bt)
    {
        if(bt != NULL)
        {
            printf("%d", bt->key);
            if(bt->lchild != NULL || bt->rchild != NULL)
            {
                printf("(");                //  有孩子结点时才输出(
                disp_bst(bt->lchild);       //  递归处理左子树
                if(bt->rchild != NULL)
                    printf(",");            //  有右孩子结点时才输出,
                disp_bst(bt->rchild);       //  递归处理右子树
                printf(")");                //  有孩子结点时才输出)
            }
        }
    }

    key_type predt = -32767;                            // predt为全局变量,保存当前结点中序前驱的值,初值为-∞
    /*----------------判断bt是否为BST------------------*/
    bool judge_bst(BSTNode *bt)
    {
        bool b1, b2;

        if(bt == NULL)
            return true;
        else
        {
            b1 = judge_bst(bt->lchild);
            if(b1 == false || predt >= bt->key)
                return false;
            b2 = judge_bst(bt->rchild);
            return b2;
        }
    }

    /*----------------销毁一颗BST------------------*/
    void destroy_bst(BSTNode *bt)
    {
        if(bt != NULL)
        {
            destroy_bst(bt->lchild);
            destroy_bst(bt->rchild);
            free(bt);
        }
    }

    /*----------------以非递归方式输出从根结点到查找到的结点的路径------------------*/
    void search_bst1(BSTNode *bt, key_type key, key_type path[], int i)
    {
        int j;

        if(bt == NULL)
            return;
        else if(key == bt->key)     // 找到关键字为key的结点
        {
            path[i + 1] = bt->key;  // 输出其路径
            for(j = 0; j <= i + 1; j++)
            {
                printf("%3d", path[j]);
            }
            printf("\n");
        }
        else
        {
            path[i + 1] = bt->key;
            if(key < bt->key)
                search_bst1(bt->lchild, key, path, i + 1);      // 在左子树中递归查找
            else
                search_bst1(bt->rchild, key, path, i + 1);      // 在右子树中递归查找
        }
    }

    /*----------------以递归方式输出从根结点到查找到的结点的路径------------------*/
    int search_bst2(BSTNode *bt, key_type key)
    {
        if(bt == NULL)
            return 0;
        else if(key == bt->key)                 // 找到关键字为key的结点
        {
            printf("%3d", bt->key);             // 输出关键字
            return 1;
        }
        else if(key < bt->key)
        {
            search_bst2(bt->lchild, key);       // 在左子树中递归查找
        }
        else
        {
            search_bst2(bt->rchild, key);       // 在右子树中递归查找
        }
        printf("%3d", bt->key);                 // 输出关键字
    }

    /*----------------被删除的结点p有左、右子树,r指向其左孩子------------------*/
    void delete_node1(BSTNode *p, BSTNode *&r)      // 指针的引用
    {
        BSTNode *q;

        if(r->rchild != NULL)                       // 递归找结点r的最右下结点
        {
            delete_node1(p, r->rchild);
        }
        else                                        // 找到最右下结点r(它没有右子树)
        {
            p->key = r->key;                        // 将结点r的值存放到结点p中(结点值替代)
            p->data = r->data;
            q = r;                                  // 删除结点r
            r = r->lchild;                          // 即用结点r的左孩子替代它
            free(q);                                // 释放结点r的空间
        }
    }

    /*----------------从二叉排序树中删除p结点------------------*/
    void delete_node(BSTNode *&p)
    {
        BSTNode *q;

        if(p->rchild == NULL)                               // p结点没有右子树的情况
        {
            q = p;
            p = p->lchild;
            free(q);
        }
        else if(p->lchild == NULL)                          // p结点没有左子树的情况
        {
            q = p;
            p = p->rchild;
            free(q);
        }
        else
            delete_node1(p, p->lchild);                     // p结点既有左子树又有右子树的情况
    }

    /*----------------在bt中删除关键字为key的结点------------------*/
    bool delete_bst(BSTNode *&bt, key_type key)
    {
        if(bt == NULL)                                      // 空树删除失败
            return false;
        else
        {
            if(key < bt->key)
                return delete_bst(bt->lchild, key);         // 递归在左子树中删除关键字为key的结点
            else if(key > bt->key)
                return delete_bst(bt->rchild, key);         // 递归在右子树中删除关键字为key的结点
            else                                            // key = bt->key的情况
            {
                delete_node(bt);                            // 调用函数delete_node删除bt结点
                return true;
            }
        }
    }

    /*---------------判断a是否为bt中的一个合法查找序列---------------*/
    static bool find_seq(BSTNode *bt, int a[], int n)
    {
        int i = 0;
        BSTNode *p = bt;

        while(i < n && p != NULL)
        {
            if(i == n - 1 && a[i] == p->key)                //  a查找完毕,返回true
                return true;
            if(p->key != a[i])                              //  若不等,表示a不是查找序列,返回false
                return false;
            i++;                                            //  查找序列指向下一个关键字
            if(a[i] < p->key)
                p = p->lchild;                              //  在左子树中查找
            else if(a[i] > p->key)
                p = p->rchild;                              //  在右子树中查找
        }

        return false;
    }

    int main(int argc, char *argv[])
    {
        BSTNode *bt;
        key_type keys[] = {5, 2, 3, 4, 1, 6, 8, 7, 9};      //  关键字序列
        int m = 9;                                          //  关键字序列长度
        int n = 4;

        printf("(1)构造二叉排序树bt\n");
        bt = create_bst(keys, m);                           //  创建二叉排序树
        printf("(2)输出BST:");
        disp_bst(bt);                                       //  5(2(1,3(,4)),6(,8(7,9)))
        printf("\n");
        key_type a[] = {5, 6, 7, 9};
        printf("(3)关键字序列:");
        for(int i = 0; i < n; i++)
        {
            printf("%2d", a[i]);
        }
        if(find_seq(bt, a, n))
            printf("是一个查找序列\n");
        else
            printf("不是一个查找序列\n");

        printf("(4)销毁bt\n");
        destroy_bst(bt);

        return 0;
    }
    测试结果:

    (1)构造二叉排序树bt
         第1步,插入5:5
         第2步,插入2:5(2)
         第3步,插入3:5(2(,3))
         第4步,插入4:5(2(,3(,4)))
         第5步,插入1:5(2(1,3(,4)))
         第6步,插入6:5(2(1,3(,4)),6)
         第7步,插入8:5(2(1,3(,4)),6(,8))
         第8步,插入7:5(2(1,3(,4)),6(,8(7)))
         第9步,插入9:5(2(1,3(,4)),6(,8(7,9)))
    (2)输出BST:5(2(1,3(,4)),6(,8(7,9)))
    (3)关键字序列: 5 6 7 9不是一个查找序列
    (4)销毁bt

    展开全文
  • 判断一颗二叉树是否二叉排序树

    千次阅读 2019-09-08 11:13:53
    设计一个算法,判断给出的二叉树是否二叉排序树,假设二叉排序树已经存储在二叉链表的存储结构中,树节点的个数为n,节点值为int类型 2. 思路如下: ① 判断一颗二叉树是否二叉排序树的方法有好几种,其中最...

    1. 问题描述:

    设计一个算法,判断给出的二叉树是否是二叉排序树,假设二叉排序树已经存储在二叉链表的存储结构中,树节点的个数为n,节点值为int类型

    2. 思路如下:

    ① 判断一颗二叉树是否是二叉排序树的方法有好几种,其中最简单的方法是对给定的二叉树进行中序遍历,假如二叉树是二叉排序树那么中序遍历的结果一定是递增的,假如不是那么就不是二叉排序树

    ② 基于上面的想法我们可以使用中序遍历的方法,使用一个全局变量来记录递归遍历的根节点的值,在遍历过程中遇到叶子节点那么可以直接返回1(为二叉排序树),全局变量实际上记录的是上一次递归过程中的根节点的值,往下是对右子树进行递归遍历,所以在递归完根节点的的左子树之后那么判断上一次递归过程中的根节点与当前节点的值,而当前节点的值恰恰是上一次递归过程中右子树的节点的值,所以判断一下假如发现当前的全局变量的值大于了当前节点的值(上一次根节点的右子树)那么肯定不是二叉排序树直接返回0

    ③ 为了简单测试一下二叉树是否是二叉排序树那么可以简单手动创建一颗二叉树通过改变其中的值来检测算法是否正确,我们再一开始创建出一颗二叉树之后对其进行遍历判断创建的二叉树是否成功这样才可以进行接下来判断是否是二叉排序树

    ④ 在创建节点的过程中我们对于节点中没有孩子的节点的指针通通赋值为NULL,这样程序才不会出错

    ⑤ 下面是具体的C++代码:

    #include<iostream>
    #include<malloc.h>
    //创建一颗二叉树 
    /*
    			  6
    		 3        9
    	  1     4   7  10 		
    		2	  5		
    */
    using namespace std;
    typedef struct BSTode{
    	BSTode *left;
    	BSTode *right;
    	int data;	
    }BSTNode; 
    BSTNode *root;
    int predt = -10000;
    int judgeBST(BSTode *bt){
    	int b1, b2;
    	if(bt == NULL){
    		return 1;
    	}
    	else{
    		b1 = judgeBST(bt->left);
    		if(b1 == 0 || predt > bt->data) return 0;
    		predt = bt->data;
    		b2 = judgeBST(bt->right);
    		return b2;
    	}
    }
    //先序遍历
    void preOrder(BSTNode *p){
    	if(p != NULL){
    		cout << p->data << " ";
    		preOrder(p->left);
    		preOrder(p->right);
    	}
    } 
    
    int main(void){
    	root = (BSTode*)(malloc(sizeof(BSTode)));
    	root->data = 6;
    	
    	BSTode *l = (BSTode*)(malloc(sizeof(BSTode)));
    	l->data = 3;
    	
    	BSTode *r = (BSTode*)(malloc(sizeof(BSTode)));
    	r->data = 9;
    	
    	BSTode *ll = (BSTode*)(malloc(sizeof(BSTode)));
    	ll->data = 1;
    	
    	BSTode *lr = (BSTode*)(malloc(sizeof(BSTode)));
    	lr->data = 4;
    	
    	BSTode *rl = (BSTode*)(malloc(sizeof(BSTode)));
    	rl->data = 7;
    	
    	BSTode *rr = (BSTode*)(malloc(sizeof(BSTode)));
    	rr->data = 10;
    	
    	BSTode *llr = (BSTode*)(malloc(sizeof(BSTode)));
    	llr->data = 2;
    	
    	BSTode *lrr = (BSTode*)(malloc(sizeof(BSTode)));
    	lrr->data = 5;
    	
    	root->left = l;
    	root->right = r;
    	l->left = ll;
    	l->right = lr;
    	r->left = rl;
    	r->right = rr;
    	
    	ll->right = llr;
    	ll->left = NULL;
    	lr->left = NULL;
    	lr->right = lrr;
    	
    	rl->left = NULL;
    	rl->right = NULL;
    	rr->left = NULL;
    	rr->right = NULL;
    	
    	llr->left = NULL;
    	llr->right = NULL;
    	lrr->left = NULL;
    	lrr->right = NULL;
    	preOrder(root);
    	cout << endl << judgeBST(root) << endl;
    	return 0;
    } 

     

    展开全文
  • 数据结构–用递归的方法判断一个树是否二叉排序树 【代码】: #include<iostream> #include<malloc.h> #define OVERFLOW -2 using namespace std; typedef struct BiTNode { int data; int number...

    数据结构–用递归的方法判断一个树是否是二叉排序树

    【代码】:
    
    #include<iostream>
    #include<malloc.h>
    #define OVERFLOW -2
    using namespace std;
    
    typedef struct BiTNode
    {
        int data;
        int number;
        struct BiTNode *parent,* lChild, * rChild;
    } BiTNode,*BiTree;
    
    int number = 0;
    int yor = 0;
    int maxData;
    int isBST = 1;
    int yesOrNo[] = { 1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,0 };
    
    //int numData[] = { 12,5,11,67,55,45,57,72 };
    int numData[] = { 12,10,11,67,55,51,77,82 };
    BiTree treeParent = NULL;
    
    int OperationBiTree(BiTree &BT)
    {
        BT = (BiTree)malloc(sizeof(BiTNode));
        if (!BT)
        {
            cout << "空间分配失败" << endl;
            exit(OVERFLOW);
        }
        BT->number = number;
        number++;
        BT->data = numData[BT->number];
        BT->lChild = NULL;
        BT->rChild = NULL;
        BT->parent = treeParent;
        return 1;
    }
    
    void PreOrderCreatBiTree(BiTree &BT)
    {
    
        OperationBiTree(BT);
        treeParent = BT;
        if (yesOrNo[yor++])
            PreOrderCreatBiTree(BT->lChild);
        treeParent = BT;
        if (yesOrNo[yor++])
            PreOrderCreatBiTree(BT->rChild);
    
    }
    
    void VisitBiTree(BiTree BT)
    {
        cout << "当前结点的编号为:" << BT->number<<", 数据为:" << BT->data << ",\n";
    
    }
    
    void InOrderBiTree(BiTree BT)
    {
        if (BT)
        {
            InOrderBiTree(BT->lChild);
            VisitBiTree(BT);
            if (maxData < BT->data)
            {
                maxData = BT->data;
            }
            else
                isBST = 0;
            InOrderBiTree(BT->rChild);
        }
    }
    
    int main()
    {
        BiTree BT;
        PreOrderCreatBiTree(BT);
        BiTree p = BT;
        while (p&&p->lChild)
        {
            p = p->lChild;
        }
        maxData = p->data - 1;
    
        cout << "\n******【中序遍历二叉树】******\n";
        InOrderBiTree(BT);
    
        if (isBST)
            cout << "这个二叉树是二叉排序树.\n";
        else
            cout << "这个二叉树不是二叉排序树.\n";
    
    }
    
    

    【结果】

    在这里插入图片描述

    展开全文
  • 判断一树是否二叉排序树

    千次阅读 多人点赞 2017-11-23 19:18:08
    概要由于二叉排序树的中序遍历时得到的一定是个一个升序序列,我们可以根据这一性质,利用中序遍历进行判定。算法1)设置全局变量max为无穷小。 2)若树为空,则返回true。 3)否则递归判断左子树是否二叉排序树...
  • 以下用递归的方法来解决: bool IsBSTree(BiTree T) { ...T) { //若传入的是空,则返回false。 return false; } else if (T-&gt;lchild == NULL &amp;&amp; T-&gt;rchild == NULL) { //若...
  • 判断某个树是否二叉排序树或者镜像二叉排序树的前序序列 #include <iostream> #include <vector> using namespace std; bool flag = true; bool flag1 = true; bool flag2 = true; typedef struct ...
  • 判断一棵二叉树是否二叉排序树

    千次阅读 2013-10-04 16:04:48
    判断一棵二叉树是否二叉排序树,可以通过中序遍历来检查,为此要设置一个指针pr指示二叉树中当前结点的中序直接前驱,每访问一个结点,就比较当前访问结点的关键值是否大于ptr所指结点的关键字值,如果遍历了所有...
  • 判断给定的二叉树是否二叉排序树 根据二叉排序树的定义,左子树结点值 < 根结点值 < 右子树结点值,所以对二叉排序树进行中序遍历(LNR),可以得到一个递增的有序序列。因此,对给定的二叉树进行中序遍历,...
  • 判断一棵树是否二叉排序树 二叉排序树的性质:如果按照中序遍历的方式遍历二叉排序树的话,遍历的数字是呈递增趋势的。我们根据这个思路去判断是否为二叉排序树。 思路: ①建树 ②设立一个变量去记录当前已经遍历...
  • 今天给大家分享的是二叉排序树的应用,判断一个二叉树是否为一棵二叉排序树二叉排序树的特点大家都知道,左子树根结点值&lt;根结点&lt;右子树根结点值,并且中序遍历二叉排序树时,得到的序列是一个严格...
  • 判断一棵二叉树是否二叉排序树

    万次阅读 多人点赞 2017-10-16 19:22:02
    二叉排序树或者是棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值; ...
  • 判断一个数字序列是否二叉排序树的后续遍历,其实就是一个递归,算法很短
  • 输入棵树,判断这棵树是否为二叉搜索树。首先要知道什么是排序二叉树,二叉排序树是这样定义的,二叉排序树或者是棵空树,或者是具有下列性质的二叉树:  (1)若左子树不空,则左子树上所有结点的值均小于它...
  • 输入一个整数组,判断该数组是不是二叉搜索的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 链接: http://www.nowcoder.com/practice/a861533d45854474ac7
  • 给定一个二叉树,判断是否一个有效的二叉搜索一个二叉搜索具有如下特征: 节点的左子树只包含小于当前节点的。 节点的右子只包含大于当前节点的。 所有左子树和右子自身必须也是二叉搜索。...
  • 输入一个整数组,判断该数组是不是二叉搜索的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 输入: 每个测试案例包括2行: 第一行为1个整数n(1 第二行包含n个整数...
  • 判断一个序列是否为该二叉排序树中的一个合法的查找序列 #include #include typedef struct node { int data; struct node *lchild,*rchild; } BSTNode; int *A; //全局变量A BSTNode* CreateBS
  • 二叉排序树(BST)的中序遍历是一个顺序序列。 直接判断法:直接判断法关键在于不能只判断左右根节点之间的关系。这样会造成局部二叉排序树的情况,**是错误的!!!**也就是说,左子树的右节点不仅要大于它的根节点...
  • 代码比较拉垮,但思路应该是最好理解的 思路 判断当前结点是否符合“左结点数据<中(当前结点数据)<右结点数据”的大小顺序;... //终止条件(空数是二叉排序树) if (root == NULL) return true; //.
  • 判断给定的二叉树是否二叉排序树

    万次阅读 多人点赞 2018-11-12 21:19:49
    判断给定的二叉树是否二叉排序树
  • #include<stdio.h>...、创建二叉排序树: s 和 p 的先后关系要注意,p 最后会为 NULL。 //创建二叉排序树 PNode CreateBiTree(int a[],int n){ int i,j,k,flag; PNode p,q,s,t; if(n<=0

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,242
精华内容 12,096
关键字:

判断一个数是否是二叉排序树