精华内容
下载资源
问答
  • (2) 建立一棵二叉排序树,然后进行中序遍历,并实现动态查找。(输入零为空) 头文件:1.h #include <iostream> #include <malloc.h> #include <string.h> #define TRUE...

    (2) 建立一棵二叉排序树,然后进行中序遍历,并实现动态查找。(输入零为空)

    头文件:1.h

    #include <iostream>
    #include <malloc.h>
    #include <string.h>
    #define TRUE  1
    #define FALSE 0
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW    -2
    #define OK 1
    typedef int Status;
    using namespace std;
    

    头文件:2.h

    typedef int TElemType;
    typedef int KeyElemType;
    typedef struct BiTNode
    {
    	TElemType data;
    	BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    

    头文件:3.h

    #include "2.h"
    Status CreatBitree(BiTree &T)//先序建立二叉树
    {
    	TElemType ch;
    	cin >> ch;
    	if (ch == 0)
    	{
    		T = NULL;
    
    	}
    	else
    	{
    		T = (BiTNode *)malloc(sizeof(BiTNode));
    		if (!T)
    			return OVERFLOW;
    		T->data = ch;
    		CreatBitree(T->lchild);
    		CreatBitree(T->rchild);
    	}
    
    	return OK;
    }
    BiTree SearchBST(BiTree T, KeyElemType key)
    {
    	if ((!T) || T->data == key) return T;
    	else if (T->data < key) return SearchBST(T->rchild, key);
    	else if (T->data > key) return SearchBST(T->lchild, key);
    }
    

    源程序

    int main()
    {
    	BiTree T,D;
    	cout << "请输入一个二叉排序树:(输入0位空)";
    	CreatBitree(T);
    	KeyElemType key;
    	cout << "请输入查询的数目:";
    	cin >> key;
    	D = SearchBST(T, key);
    	if (D == NULL) cout << "查询失败" << endl;
    	else
    		cout << D->data;
    	system("pause");
    	
    }
    

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  •  输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整中结点指针的指向。 分析  二叉搜索的左孩子比父节点的值小,右孩子比父节点的值大,通过中序遍历即可...
    题目
    

      输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

    分析

      二叉搜索树的左孩子比父节点的值小,右孩子比父节点的值大,通过中序遍历即可得到一个排序的队列。在遍历的过程中调整节点指针的指向就可以将它转换成一个排序的双向链表了

      此前曾分析过二叉树的中序遍历的非递归方法。借此直接转化为求排序双向链表的方法

    代码

     1 TreeNode* BinaryTreeConvert2(TreeNode* root)
     2 {
     3     if (!root)
     4     {
     5         throw std::exception("this is an empty tree!");
     6     }
     7 
     8     stack<TreeNode*> s_tree;
     9     TreeNode* node=root,*pre_node=NULL,*head=NULL;
    10     while (node||!s_tree.empty())
    11     {
    12         while (node)
    13         {
    14             s_tree.push(node);
    15             node=node->pLeft;
    16         }
    17 
    18         node=s_tree.top();
    19         s_tree.pop();
    20 
    21         /*
    22          *将中序遍历的输出变为指针调整
    23         */
    24         //cout<<node->value<<endl;
    25         //指定双向链表的头节点
    26         if(!head)
    27             head=node;
    28 
    29         //前后指针
    30         node->pLeft=pre_node;
    31         if (pre_node)
    32         {
    33             pre_node->pRight=node;
    34         }
    35         //记录前一个节点
    36         pre_node=node;
    37 
    38 
    39         node=node->pRight;
    40     }
    41 
    42     return head;
    43 }

     

    创建一个新的双向链表

     1 DListNode* BinaryTreeConvert(TreeNode* root)
     2 {
     3     if (!root)
     4     {
     5         throw std::exception("this is an empty tree!");
     6     }
     7 
     8     stack<TreeNode*> s_tree;
     9     stack<DListNode*> s_list;
    10     TreeNode* node=root;
    11     DListNode *head=NULL,*tail=NULL;
    12     DListNode *list_node=NULL,*pre_node=NULL;
    13     while (node||!s_tree.empty())
    14     {
    15         while (node)
    16         {
    17             s_tree.push(node);
    18             node=node->pLeft;
    19         }
    20 
    21         node=s_tree.top();
    22         s_tree.pop();
    23 
    24         /*
    25          *将中序遍历的输出变为双向链表节点创建以及指针调整
    26         */
    27         //cout<<node->value<<endl;
    28         list_node=new DListNode();
    29         list_node->value=node->value;
    30         list_node->pNext=NULL;
    31         list_node->pPre=NULL;
    32 
    33         //指定双向链表的头节点
    34         if(!head)
    35             head=list_node;
    36 
    37         //前后指针
    38         list_node->pPre=pre_node;
    39         if (pre_node)
    40         {
    41             pre_node->pNext=list_node;
    42         }
    43 
    44         pre_node=list_node;
    45 
    46 
    47         node=node->pRight;
    48     }
    49 
    50     return head;
    51 }

     

    展开全文
  • 结构练习——排序二叉树的中序遍历 Problem Description 在结构中,有种特殊的二叉树叫做排序二叉树,直观的理解就是——(1).每个节点中包含有个关键值 (2).任意个节点的左子树(如果存在的话)的关键值...

    树结构练习——排序二叉树的中序遍历

    Problem Description

    在树结构中,有一种特殊的二叉树叫做排序二叉树,直观的理解就是——(1).每个节点中包含有一个关键值 (2).任意一个节点的左子树(如果存在的话)的关键值小于该节点的关键值 (3).任意一个节点的右子树(如果存在的话)的关键值大于该节点的关键值。现给定一组数据,请你对这组数据按给定顺序建立一棵排序二叉树,并输出其中序遍历的结果。

    Input

    输入包含多组数据,每组数据格式如下。
    第一行包含一个整数n,为关键值的个数,关键值用整数表示。(n<=1000)
    第二行包含n个整数,保证每个整数在int范围之内。

    Output

    为给定的数据建立排序二叉树,并输出其中序遍历结果,每个输出占一行。

    Sample Input

    1
    2
    2
    1 20

    Sample Output

    2
    1 20

    这道题的题意:顺序给出一棵排序二叉树,求中序遍历结果。

    排序二叉树的定义是:
    (1).每个节点中包含有一个关键值 。
    (2).任意一个节点的左子树(如果存在的话)的关键值小于该节点的关键值 。
    (3).任意一个节点的右子树(如果存在的话)的关键值大于该节点的关键值。

    根据定义就可以很容易创造出一棵排序二叉树。

    给出代码:

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
        int date;
        struct node *l,*r;
    } tree;     //树的结构
    
    tree *creat( tree *p, int key );  // 创建排序二叉树
    void show_mid(tree *root);        // 二叉树进行中序遍历
    
    int a[10001]; //因为这次数据是数字,不是字符串,所以有数字之间的空格问题和行末的回撤问题,
    int k;        // 所以在中序遍历时不是直接输出,而是存入a的数组,方便之后输出。
                  //  k 为二叉树的节点总数。
    int main()
    {
        int n,i,key;
        tree *root;
        while ( ~scanf("%d",&n) ) {
            root = NULL; k = 0;
            for ( i=0; i<n; i++ ) {   // 每次输入一个值,依次插入树中。
                scanf("%d",&key);
                root = creat(root,key);
            }
            
            show_mid(root);
            for ( i=0; i<k-1; i++ ) {
                printf("%d ",a[i]);
            }
            printf("%d\n",a[k-1]);
    
        }
    
        return 0;
    }
    
    tree *creat( tree *p, int key )   // 当p节点空时直接插入,当p非空时运用递归插入到左树或右树。
    {
        if ( p==NULL ) {
            p = (tree *)malloc(sizeof(tree));
            p->date = key;
            p -> l = p -> r = NULL;
        } else if ( key>p->date ) {
            p->r = creat(p->r,key);
        } else {
            p->l = creat(p->l,key);
        }
    
        return p;
    }
    
    void show_mid(tree *root)
    {
        if ( root ) {
            show_mid(root->l);
            a[k++] = root->date;
            show_mid(root->r);
        }
    }
    
    
    /***************************************************
    User name: rj180323石旭
    Result: Accepted
    Take time: 0ms
    Take Memory: 168KB
    Submit time: 2019-01-23 08:34:27
    ****************************************************/
    
    展开全文
  • 输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整中结点指针的指向。 分析思路: 题目描述如下图所示: (容器法)首先看到下图的数字排序,明显就是一个...

    题目描述

    输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

    分析思路:

    题目描述如下图所示:

    (容器法)首先看到下图的数字排序,明显就是一个中序遍历的结果,那么只需要对二叉搜索树做中序遍历,将遍历结果的每个节点保存进一个容器中,然后对容器中的每一个值,也就是二叉树的每一个节点按照规则重新链接好

    链接规则如下:

    从左往右,当前节点的右节点是当前在容器中的位置的下一位

    从右往左,当前节点的做节点是当前在容器中的位置的前一位

    示意图:

    def Convert(root):
        
        if not root:
            return None
    
        # 第一步使用中序遍历,保存节点
        def MidOrder(root):
            if not root:
                return
            MidOrder(root.left)
            orderNode.append(root)
            MidOrder(root.right)
    
        orderNode = []
        MidOrder(root)
    
        # 重新构造链接
        cur = orderNode[0]
        Length = len(orderNode)
        for i in range(Length - 1):
            # 从左到右构造链接
            orderNode[i].right = orderNode[i + 1]
            # 从右往左构造链接
            orderNode[Length - 1 - i].left = orderNode[Length - i - 2]
    
        return cur

    测试:

    class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    
    
    root = TreeNode(10)
    a = TreeNode(6)
    b = TreeNode(14)
    c = TreeNode(4)
    d = TreeNode(8)
    e = TreeNode(12)
    f = TreeNode(16)
    
    root.left = a
    root.right = b
    a.left = c
    a.right = d
    b.left = e
    b.right = f
    
    Node = Convert(root)
    tmp = Node
    while tmp:
        print(tmp.val)
        tmp = tmp.right
    
    

     

    展开全文
  • 输入组关键字,排列成一棵二叉排序树,最后中序遍历其结果
  • 1) 以回车为输入结束标志,输入数列L,生成一棵二叉排序树T; 2) 对二叉排序树T作中序遍历,输出结果; 3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点, 并作中序遍历(执行操作2);否则输出信息“无x...
  • 将整数序列(7-2-4-6-3-1-5)按所示顺序构建一棵二叉排序树a(亦称二叉搜索树),之后将整数8按照二叉排序树规则插入树a中,请问插入之后的树a中序遍历结果是____。 正确答案: A 你的答案: A (正确) 1-...
  • 二叉排序树中序遍历(非递归不用栈队列) 找到这树的中序遍历的第个节点 相当于找这课二叉树的最小值 BstNode* First(BstNode* ptr)//找到这树的中序遍历的第个节点 { while (ptr != nullptr &&...
  • 二叉排序树或者是一棵空树,或者是一颗具有以下特性的非空二叉树: 若左子树非空,则左子树上所有结点的值都小于根节点的值。 若右子树非空,则左子树上所有结点的值都大于根节点的值。 左、右子树也分别是一颗...
  • * 二叉排序树BST的插入和中序遍历 * 排序树的中序遍历输出序列是递增的 **/ #include<iostream> using namespace std; #define DataType int #define test_length 12 DataType test_data[test_length]={5,...
  • 二叉排序树中序遍历

    千次阅读 2017-08-10 08:41:53
    排序二叉树的中序遍历 Problem Description 在结构中,有种特殊的二叉树叫做排序二叉树,直观的理解就是——(1).每个节点中包含有个关键值 (2).任意个节点的左子树(如果存在的话)的关键值小于该节点...
  • Problem:给出n个int数,对其构造一棵二叉排序树,并打印其先序遍历、中序遍历、后序遍历的一维数组。 (华中科技大学保研机试真题) #include &lt;stdio.h&gt; #include &lt;string.h&gt; ...
  • 一棵BST定义为: 节点的左子树中的值要严格小于该节点的值。节点的右子中的值要严格大于该节点的值。左右子树也必须是二叉查找。一个节点的也是二叉查找。 样例 一个例子: 2 / \ 1 4 / \ 3 5 上述...
  • 输入一棵二叉搜索,将该二叉搜索转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索为例: 我们希望将这个二叉...
  • ?对给定的整数序列,建立一棵二叉排序树,并按中序遍历输出树中结点。用C语言编一程序怎么实现?
  • 二叉排序树或者是一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值; ...
  • 给你root1 和 root2这两棵二叉搜索。 请你返回个列表,其中包含两棵中的所有整数并按 升序 排序。. 示例 1: 输入:root1 = [2,1,4], root2 = [1,0,3] 输出:[0,1,1,2,3,4] 示例 2: 输入:root1 = [0,-...
  • 给你 root1 和 root2 这两棵二叉搜索。 请你返回个列表,其中包含 两棵 中的所有整数并按 升序 排序。. 示例 1: 输入:root1 = [2,1,4], root2 = [1,0,3] 输出:[0,1,1,2,3,4] 示例 2: 输入:root1 = [0,-...
  • Think: 1知识点:判断两棵二叉排序树是否相同 2判断依据: (1):根节点相同 ...(1):相同元素而插入顺序不同的二叉排序树中序遍历有序唯一,故不能通过判断元素插入顺序不同的两棵二叉排序树是否
  • 给定一棵二叉搜索,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。 解题思路: 我们知道二叉搜索中序遍历就是排序好的数列。所以我们只需中序遍历到...
  • 二叉搜索树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根节点的值; 若它的右子树不空,则右子树...
  • 建立一棵二叉排序树

    千次阅读 多人点赞 2019-06-03 23:53:28
    二叉排序树(也称二叉查找树),或者是一棵空的二叉树,或者是具有下列性质的二叉树: ⑴ 若它的左子树不空,则左子树上所有结点的值均小于根结点的值; ⑵ 若它的右子树不空,则右子树上所有结点的值均大于根结点的...
  • 给定一棵二叉搜索,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。 思路: 二叉搜索中序遍历是非递减排序的,所以第k小就是中序遍历结果中第k个元素 ...
  • 给定一个插入序列就可以唯一确定一棵二叉搜索。然而,一棵给定的二叉搜索却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索,都得到一样的结果。于是对于输入的...
  • 给定一棵二叉搜索,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。 思路 二叉搜索的特点是:左子树的值比根节点小,右字数的值比根节点要大(不排除等于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,362
精华内容 544
关键字:

中序遍历一棵二叉排序树