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

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

    分析

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

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

    代码

     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 }

     

    展开全文
  • 题目描述输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整中结点指针的指向。解题思路及代码方法一使用一个数组存储中序遍历这棵二叉搜索的结果,那么我们就...

    453a4d2d144c2f798a0ad288fa287d06.png

    题目描述

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

    b0ca49315f8ad94dd9044f2be23cc330.png

    解题思路及代码

    方法一

    使用一个数组存储中序遍历这棵二叉搜索树的结果,那么我们就可以得到一个从左到右递增的序列。接着我们对这个序列从头到尾建立结点前后的连接关系(左指针指向前一个,右指针指向后一个)。

    代码如下:

    public 

    方法二

    边中序遍历二叉搜索树边修改指针。

    代码如下:

    private 

    图示:

    81ab4ae1bdc068dbd92192e02d26245f.png
    展开全文
  • 建立一棵二叉排序树

    千次阅读 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;
    }
    
    展开全文
  • 给定一个插入序列就可以唯一确定一棵二叉搜索。然而,一棵给定的二叉搜索可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索,都得到一样的结果。于是对于输入的...

    一。题目
    给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{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;
    }
    
    展开全文
  • (2)在(1)的基础上,请编写个函数(int LeafCount(Binary_tree BT)),求此二叉树的叶子结点个数。 有关的数据结构已描述如下:
  • 今天给大家分享的是二叉排序树的应用,判断一个二叉树是否为一棵二叉排序树。 二叉排序树的特点大家都知道,左子树根结点值&lt;根结点&lt;右子树根结点值,并且中序遍历二叉排序树时,得到的序列是一个严格...
  • 判断一棵树是否为二叉排序树

    千次阅读 多人点赞 2017-11-23 19:18:08
    概要由于二叉排序树的中序遍历时得到的一定是个个升序序列,我们可以根据这性质,利用中序遍历进行判定。算法1)设置全局变量max为无穷小。 2)若树为空,则返回true。 3)否则递归判断左子树是否为二叉排序树...
  • 二叉排序树(BST)的定义为:二叉排序树或者是空树,或者是满足下列性质的二叉树: ... 结论:若按中序遍历一棵二叉排序树,所得到的结点序列是一个递增序列。 BST可以用二叉链表来存储: BS...
  • 二叉排序树的一个重要性质:中序遍历一棵二叉 树时可以得到一个结点值递增的有序序列。 对于需要经常进行插入、 删除和查找运算的表,采用二叉排序树比较好 查找: 若二叉排序树为空,则查找失败,返回空指针。 若...
  • 输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整中结点指针的指向。 思路: 可以知道,二叉搜索中序遍历得到一个排好序的输出 在中序遍历中 将当前结点的...
  • 二叉排序树

    2019-12-16 19:52:13
    定义 二叉排序树(也称二叉查找树):或者是一棵空...中序遍历二叉排序树可以得到一个按关键码有序的序列 二叉排序树的插入 分析:若二叉排序树为空树,则新插入的结点为新的根结点; 否则,如果插入的值比根节点值...
  • (3)左右子树分别为一棵二叉排序树。 根据二叉排序树的定义,左子树结点值<根结点值<右子树结点值,则对二叉排序树进行中序遍历可以得到一个递增的有序序列。如果有相同的值,可以将该节点放在左子节点或右...
  • 二叉排序树详解

    2018-08-13 16:58:06
    二叉排序树的介绍 二叉排序树为一颗二叉树,或者为空,或者满足如下条件: 如果它的左子树不为空,...中序遍历二叉排序树便可得到一个有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造...
  • 1.简介 二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树: ...中序遍历二叉排序树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树...
  • 1、二叉排序树 二叉排序树(也称二叉查找树): 或者是一棵空的二叉树,或者是具有下列性质的二叉树: ...2、中序遍历二叉排序树可以得到一个按关键码有序的序列 3、 #include <iostream> using namespac...
  • 左子树和右子树又各是一棵二叉排序树。 在二叉排序树中,若按中序遍历可以得到由小到大的有序序列,如图2.41中的二叉排序树,中序遍历可得到有序序列{2,3,4,8,9,9,10,13,15,18,21}。 (2)二叉排序树的生成 二叉...
  • 二叉排序树(二叉查找树) 二叉排序树或者是一棵空树,或者是具有下列性质:...中序遍历二叉排序树时,可以得到一个有序的序列。 构造一颗二叉排序树的目的,并不是为了排序,而是为了提高查找和插入删除关键字的速度。
  • java实现二叉排序树

    2017-05-28 12:49:15
    1.什么是二叉排序树 ...左右子树又各是一棵二叉排序树。 基于二叉排序树的性质我们可以得到的一点是,如果我们输出二叉排序树的中序遍历序列,则这个序列的值是依次递增的顺序。 如果对二叉树不清楚,那么可以看
  •   3)左、右子树本身也分别是一棵二叉排序树   左子树结点值 < 根结点值 < 右子树结点值,对二叉排序树进行中序遍历可以得到一个递增的有序序列。   查找   二叉排序树的查找是从根结点开始,沿...
  • 输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整中结点指针的指向。 很惭愧这道题我看了一上午也没看懂这到底是怎么写的。总感觉这个程序结束的莫名其妙。 错点...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 124
精华内容 49
关键字:

中序遍历一棵二叉排序树可以得到