排序二叉树问题!
准备一棵排序二叉树(题目的意思不是叫你去实现排序二叉树,应该是有现成的代码和其中包含的数据可以直接使用)
读入指令数量
读入指令字符串列表
分析指令字符串列表,得到指令和对应的操作数
逐个执行指令。当碰到查询指令时,输出查询结果。
你哪里不懂? 不会一点都不懂吧.....
二叉排序树又叫二叉查找树。它的定义:
1、若根结点的左子树非空,则左子树上所有结点的关键字值均小于等于根结点的关键字值。
2、若根结点的右子树非空,则右子树上所有结点的关键字值均大于等于根结点的关键字值。
3、根结点的左、右子树也分别为二叉排序树。
中序遍历后得到一个有序的序列;
下面是实现的程序
/************************************************************************/
/* 题目:控制台下二叉排序树的建立,中序遍历 */
/* 时间:2010-3-11 上午10时9分 */
/* coder:huifeng00 */
/************************************************************************/
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef struct node
{
int element;
struct node* left;
struct node* right;
}Node,*NodePtr;
void insertNode(NodePtr *head,int data)//插入节点,注意这用了指向指针的指针,很有意思
{
if (*head==NULL)
{
*head=new Node;
(*head)->element=data;
(*head)->left=NULL;
(*head)->right=NULL;
}
else
{
if (data<=(*head)->element)
{
insertNode(&((*head)->left),data);
}
else
{
insertNode(&((*head)->right),data);
}
}
}
NodePtr creatTree()//构造二叉排序树,控制台下输入整数,0表示结束输入
{
NodePtr head=NULL;
int data;
scanf("%d",&data);
while(data!=0)
{
insertNode(&head,data);
scanf("%d",&data);
}
return head;
}
void printTree(NodePtr head)//中序遍历二叉排序树,得到有序序列
{
if(head!=NULL)
{
printTree(head->left);
printf("%d ",head->element);
printTree(head->right);
}
}
int main()
{
NodePtr head;
printf("请输入一串整数,空格隔开,0表示输入结束\n");
head=creatTree();
printf("中序遍历二叉排序树\n");
printTree(head);
printf("\n");
return 0;
}
运行结果,可以查看
http://hi.baidu.com/huifeng00/blog/item/d6b9c837d0997180a61e129d.html
1.排序二叉树的特点是左子树所有的节点值均小于根节点值,右子树的节点值均大于根节点值,从而进行中序遍历的结果就是一个有序序列
2.有很多方式建立该顺序序列的排序二叉树,例如:
4
3 5
1 9
等~~~~
一棵二叉树的先序遍历序列为ABCDEF,中序遍历结果为CBAEDF,则后序遍历...
9考虑A的左子树。根据二叉树的先序遍历序列,可知由B和C构成的二叉树,B为根结点,因为在先序遍历序列中,B比C先被访问。再根据中序遍历序列,可知A是B的左孩子,因为B是由B和C构成的二叉树的根结点,C在B前被访问,根据中序遍历的顺序,可知C是B的左孩子。如图4—10所示。考虑A的右子树。根...
计算机二级二叉树前序中序后序
二叉树遍历方式是数据结构的基础知识,作为计算机专业的大学生,我的理解如下:1、 前序遍历 它的遍历顺序是:先访问根结点,再进入这个根结点的左子树;以上述方式遍历完所有左子树后,再进入它的右子树,以同样的方式遍历右子树中的结点,即根结点→左子树→右子树。下图中1为主根结点,245为左子树...
若二叉树的先序遍历序列与中序遍历序列相同且树中结点数大于1,则该...
【答案】:D 本题考查二叉树基本运算。先序遍历二叉树时,先访问根结点,然后先序遍历根的左子树,最后遍历根的右子树。因此,二叉树的先序遍历序列中第一个结点是树根结点。中序遍历二叉树时,首先中序遍历根结点的左子树,然后访问根结点,最后中序遍历根的右子树。因此,若已知二叉树的根结点,则...
关于二叉树的遍历问题,前序abdgcefh,中序dgbaechf,求后序? 2、前序ab...
a b echf dg 3. dg在前序序列中为dg,所以根结点为d,其划分中序序列dg为空和g两个序列,所以d只有右子树 a b echf d g 4. 同样的方式分析出echf,得二叉树如下,所以后序序列为gdbehfca a b c d e f g h 同理前序abdegcfh,中序dbgeachf得到的二叉树为:a...
二叉树中序序列和前序序列有什么不同?
详解为:前序序列的顺序是根、左、右,序列ABCD第一个一定是根结点,A是根节点。中序序列顺序是左、根、右,因为A是根节点,所以DCB位于A左侧,A右侧没有结点,B是DCB三个结点中的根。前序序列是中左右,根结点为A;中序序列是左中右,左子树BCD;遵循遍历序列的规则排列出二叉树,得出后序...
某二叉树前序遍历法顺序是1,2,3,4,5,6,7,8,9 中序遍历法是4,3,5...
简介 前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。若二叉树为空则结束返回,否则:(1)访问根结点。(2)前序遍历左子树。(3)前序遍历右子树 。需要注意的是:遍历左右子树时仍然采用前序遍历方法。如图1所示...
在一棵二叉树先序遍历、中序遍历、后序遍历所产生序列中,所有叶子结 ...
(1)先序遍历(D L R):访问根结点;先序遍历左子树;先序遍历右子树。(2)中序遍历(L D R):中序遍历左子树;访问根结点;中序遍历右子树。(3)后序遍历(L R D):后序遍历左子树;后序遍历右子树;访问根结点。一棵二叉树不论哪种遍历算法,有以下要点:①所有叶子节点先后顺序不...
已知一颗二叉树,求后序遍历。
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是DGEBHFCA。前序遍历的第一个节点为根节点,由前序遍历可知,A为根节点。中序遍历的根节点前面的节点均为左子树的节点,所以左子树上的节点为DBGE。去掉根节点和左子树节点,右子数节点为CHF。前序遍历的第二个...
设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5...
前序:abdgcefh 中序:dgbaecfh 本题问题在于如何根据给定的前序中序结果画出二叉树,从而来确定后序的问题。分析过程如下:(1)前序顺序为根左右,根据前序知道:a为根节点,然后观察a在中序遍历中的结果得到:dgb为a的左子树的中序遍历结果,echf为a的右子数的中序遍历结果。(2)紧接着上面...
求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点...
根据完全二叉树的性质,最后一个结点(编号为n)的双亲结点的编号是en\/2?,这是最后一个分支结点,在它之后是第一个终端(叶子)结点,故序号最小的,叶子结点的下标是en\/2u+1。最坏的情况就是这个二叉树是单支数。 比如有k 层,节点数字也是 k 。需要 2^K - 1 长度dao的数组来存放,而实际...
海雍奥克:1.答案:C分析:根据性质“深度为K的二叉树至多有2k -1个结点(k≥1)”可知,具有结点767是深度为10完全二叉树.前9层的结点有29-1=511个结点,在第10层的结点个数就为767-511=256,那么在第9层中具有两个子结点的结点...
娄底市18086072718: 排序二叉树问题! - ?
海雍奥克: 二叉排序树又叫二叉查找树.它的定义:1、若根结点的左子树非空,则左子树上所有结点的关键字值均小于等于根结点的关键字值. 2、若根结点的右子树非空,则右子树上所有结点的关键字值均大于等于根结点的关键字值. 3、根结点的左、...
娄底市18086072718: 二叉排序树问题,请详细说明下. - ?
海雍奥克: O(n),最坏时二叉排序树退化为单枝树,只能从根开始一层一个查找,实质变为顺序查找
娄底市18086072718: 数据结构二叉排序树问题? - ?
海雍奥克: 最好的情况.每次插完都是一个完全二叉树,因此当插入第i个元素时,此时数中已经有i-1个元素,输的高度为 log(i-1). 因此T >= O(lg(2-1)) + O(lg(3-1)O(lg(i-1)O(l...
娄底市18086072718: 关于二叉排序树查找的问题? 8.在含有27个结点的二叉排序树上,查找关键字为35的结点,则依次比较的关键字有可能是 - ?
海雍奥克:[选项] A. 28,36,18,46,35 B. 18,36,28,46,35 C. 46,28,18,36,35 D. 46,36,18,28,35请哥哥姐姐给说下解析方法,我好笨.
娄底市18086072718: 在构造二叉排序树时,遇到的疑问,求解!急急急!!! - ?
海雍奥克: 一般不允许出现相同元素,因为会对搜索、排序等有影响.如果真的要处理,那就事先约定,这两个元素看做完全等价的,并约定排序比较统一用 ≥ 或者 ≤,然后按照约定来插入
娄底市18086072718: 有关二叉排序树和结点的问题题目是这样的:由4个结点可以构造出多少种不同的二叉排序树?答案是14.我想问这是怎么算出来的,还有有没有通法或者公式... - ?
海雍奥克:[答案] catalan数 可以去查一下 很多组合数学的问题都与此相关 括号匹配 进出栈 多边形划分为三角形等问题
娄底市18086072718: 数据结构 二叉排序树的概念问题判断题:二叉树为二叉排序树的充分必要条件是:其任一结点的值均大于其左孩子的值、小于其右孩子的值.为什么说这是错... - ?
海雍奥克:[答案] 二叉排序树(Binary Sort Tree)又称二叉查找树.它或者是一棵空树;或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; ...
娄底市18086072718: 关于数据结构 二叉排序树的问题 求讲解啊谢谢谢 - ?
海雍奥克: 一、按此序列构建的二叉排序树:二、前序遍历序列:43, 10, 11, 23, 65, 45, 47, 70, 90三、删除65,因为该结点度为2,所以可能两种结果:用中序的前驱或者后继替代1、用中序前驱47替代:2、用中序后继70替代:
娄底市18086072718: 排序二叉树删除节点 - ?
海雍奥克: 假设在二叉排序树上被删结点为*p(指向结点的指针为p),其双亲结点为*f(结点指针为f),且不失一般性,可设*p是*f的左孩子.下面分三种情况进行讨论:(1)若*p结点为叶子结点,即PL和PR均为空树.由于删去叶子结点不破坏整棵树...