上午看到一个题目，给定一个二叉搜索树(BST)的前序遍历(PreOrder)序列，给出算法构建原BST，花了几分钟时间想了个递归解(基本思路是分治，Divide & Conquer)，给出了如下的Pseudo Code，用Java实现了一下，算法正确。
BUILD-BST-FROM-SEQ(s, j, r)
l := r - j + 1
if l < 1 then return NIL
root := MAKE-NODE()
key[root] := s[j]
if l = 1 then return root
i := j + 1
while i < r and s[i] < s[j]
do i := i + 1
left[root] := BUILD-BST-FROM-SEQ(s, j + 1, i - 1)
right[root] := BUILD-BST-FROM-SEQ(s, i, r)
return root
调用BUILD-BST-FROM-SEQ(s, 1, length[s])即可.
初步估计了一下，Best Case时间为O(n)，Worst Case为n^2,平均情况应该是nlog(n).
分享到：
相关推荐
二叉排序树。用二叉链表作存储结构。 要求： (1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T； (2)对二叉排序树T作中序遍历，输出结果； (3)计算二叉排序树T查找成功的平均查找长度,输出结果； (4)...
设二叉排序树的二叉链表存储结构的类型定义如下： typedef struct node{ int data; //用整数表示一个结点的名 struct node *LChild,*RChild; //左右指针域 }BSTNode,*BSTree; 设计算法并编写程序求解以下几个问题...
数据结构作业，平衡二叉排序树
校园导航问题 判别否为二叉排序树 源码我也是在csdn找到的 但是他们都有些问题 要么编译有问题 要么不符合报告要求 稍微和报告要求有关 还有就无关 在我的修改下 还是有些问题 但没大问题 可以作为 报告递交 还有...
分别构建函数，实现二叉排序树的创建，插入数据，删除结点
2. 分别利用线性表和二叉排序树构建单词的存储结构。当识别出一个单词后，若线性表或者二叉排序树中没有该单词，则在适当的位置上添加该单词；若该单词已经被识别，则增加其出现的频率。 3. 统计结束后，删除出现...
撰写一个程序，能够构建字符串型的二叉排序树并在二叉排序树中查找节点。 所谓二叉排序树，简而言之，是一个每个节点可指向 0、1 或 2 个节点的递归的数据结构。最上层的一个节点称为树根。二叉排序树服从凡是比...
typedef struct node{ int data; struct node* lchild,*rchild; }* BTREE; BTREE Sort_tree(int k[],int n); void Insert(BTREE & t,int item); void INORDER(BTREE &t); int main(){ int i=0,numOfInt;...}
二叉排序树的判定，可以判定是否为二叉排序树，这是我在读大学学习的时候写的
构建二叉排序树，对元素进行排序。数据结构算法。
以学号作为主关键字的动态查找表，并用二叉排序树表示和储存它；在自己构建的二叉排序树上实现学生信息查询算法；
本程序实现了二叉排序树的建立，插入和删除结点等操作，经调试无误
排序二叉树的基础代码，包含递归非递归二叉树构建、递归非递归遍历，获取最小最大值。
1、 构建二叉排序树，并进行中根序和后根序遍历 【问题描述】 构建二叉排序树，并进行中根序和后根序遍历。1，结点的权值为int型 【输入形式】 输入n个结点，其为整数 【输出形式】 二叉排序树的中根序和后根序遍历...
第一行输入一个整数t，表示有t组测试数据 第二行起每三行表示一组数据 第1行为输入序列的元素个数：n 第2行为输入的序列：s1 s2 … sn 第3行为输入：sKey iKey dKey 第一行输出中序序列 第二行输出最小值、最大值 ...
一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；...3.通过函数判断是否为一颗二叉排序树
二叉排序树构建 （学生）.c
二叉排序树又称二叉查找树。本文主要对二叉排序树的实现与基本操作进行详细介绍，以下代码实现了：1、二叉树的构建；2、二叉树的中、前、后、层序遍历；3、二叉树中结点的最大距离。下面就跟着小编一起来看下吧
实现CreateTree函数函数原型：btnode *CreateTree (int n)形参说明：n: 节点个数返回值说明：返回树的根节点指针函数功能：构建有n个节点的二叉排序树，第一个节点为根节点，其它节点依次按照二叉排序树的构造过程...