排序二叉树构建二叉排序树,依次输入56,78,34,45,85,45,36,91,84,78,两个45和78
排序二叉树 时间:2021-09-12 阅读:(
)
构造一个二叉排序树
看了百度知道之前有人回答 “二叉排序树的插入 如果遇到 相同的节点 怎么办”,你也可以看一下该问题的答案,个人觉得挺有道理的。
根据这个结论,该二叉树这样排
12
/
5 17
/ /
3 5 14 20
9 15
/
8 10
或者
12
/
5 17
/ /
3 9 14 20
/
5 8 10 15
都可以,看你的要求,只要中序遍历是递增即可。
上述两个中序遍历都是
3 5 5 8 9 10 12 14 15 17 20最佳排序二叉树在结构上的特点是什么
展开全部
堆排序就是相当于一个排序二叉树,只是它是根节点的优先级别大于任何儿子的优先级别,这样可以每次删除根节点,然后调整整个堆。
program heap;
var a:array[1..10000] of integer;
n,i:integer;
procedure down(i:integer);
var x,j:integer;
begin
x:=a[i];
j:=i*2;
while j<=n do
begin
if a[j]>a[j+1] then j:=j+1;
if a[j]begin
a[i]:=a[j];
i:=j;
j:=i*2;
end else break;
end;
a[i]:=x;
end;
procedure delete(i);
begin
n:=n-1;
if (n=0)or(i=n+1) then exit
else
begin
a[i]:=a[n+1];
down(i);
end;
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=n div 2 downto 1 do down(i);
for i:=1 to n do
begin
write(a[1]);
delete(1);
end;
end.
如果对您有帮助,请记得采纳为满意答案,谢谢!祝您生活愉快!
vaela用C语言实现二叉排序树
#include<stdlib.h> #include<stdio.h> int counter; /*计数器*/ struct tree /*声明书的结构*/ {struct tree *left; int data; struct tree *right; }; typedef struct tree treenode; /*声明新类型树的结构*/ typedef treenode *b_tree; /*声明二叉树的链表*/ b_tree insert_node(b_tree root,int node) /*插入二叉树的结点*/ {b_tree newnode; b_tree currentnode; b_tree parentnode; newnode=(b_tree)malloc(sizeof(treenode)); /*分配新结点空间*/ newnode->data=node; newnode->right=NULL; newnode->left=NULL; if(root==NULL)return newnode; else{currentnode=root; while(currentnode!=NULL) {parentnode=currentnode; if(currentnode->data>node) currentnode=currentnode->left; else currentnode=currentnode->right; } if(parentnode->data>node) parentnode->left=newnode; else parentnode->right=newnode; } return root; /*返回根结点的指针*/ } b_tree create_btree(int *data, int len) /*建立二叉树*/ { b_tree root=NULL; int i; for(i=0;i<len;i++) root=insert_node(root,data[i]); return root; } void inorder(b_tree point) { /*中序遍历二叉树*/ if(point!=NULL) {inorder(point->left); printf("
%d
",point->data); /*处理结点内容*/ inorder(point->right); } } int tree_search(b_tree root,int key) /*查找二叉树*/ { b_tree pointer; pointer=root; counter=0; while(pointer!=NULL) { counter++; if(pointer->data<key) pointer=pointer->right; else if(pointer->data>key) pointer=pointer->left; else if(pointer->data==key) return 1; } return 0; } void main() { b_tree root=NULL; int m,i,index; /*读入输入值所用的暂存变量*/ float max=0; int nodelist[20]; /*声明存储输入数据之数组*/ int value; printf("
Please input the elements of binary tree(exit for 0):
"); index=0; scanf("%d",&value); /*读取输入值放到变量value*/ while(value!=0) {nodelist[index]=value; index=index+1; scanf("%d",&value); } printf("%d",index); root=create_btree(nodelist,index); printf("
the inorder traversal result is :"); inorder(root); printf("
"); for(m=0;m<index;m++) { tree_search(root,nodelist[m]); max+=counter; /*计算查找长度*/ } printf("the average long is: %.2f
",max/index); /*输出average查找长度*/ getch(); }利用二叉排序树对顺序表进行排序 (1)生成一个顺序表L;(2)对所生成的顺序表L构造二叉排序树(3)利用栈结构
用C或C++语言实现的功能:
(1)生成一个顺序表L;
(2)对所生成的顺序表L构造二叉排序树
(3)利用栈结构实现中序遍历二叉排序树;
(4)中序遍历所构造的二叉排序树将记录由小到大输出。
急!急!求二叉排序树程序
#include <iostream.h>
//二叉排序树类的前视定义
template<class Type> class BSTree;
//二叉排序树结点类的定义
template<class Type>
class BSTreeNode
{friend class BSTree <Type>;
private:
Type data; //数据域(在此为关键字)
BSTreeNode <Type> *leftChild, *rightChild;
public:
BSTreeNode():leftChild(NULL),rightChild (NULL){};//构造函数
BSTreeNode(const Type &d) : data (d), leftChild (NULL),rightChild (NULL) {} ; //构造函数
~BSTreeNode(){}; //析构函数
};
//二叉排序树的类定义
template <class Type>
class BSTree
{
private:
BSTreeNode<Type> * root; //二叉排序树的根指针
void Insert ( const Type & x, BSTreeNode<Type> *&p );
//在p为根的二叉排序树上插入数据元素x
void Delete ( const Type & k, BSTreeNode<Type> *&p );
//在p为根的二叉排序树上删除关键字为k的结点
BSTreeNode<Type> * Min(BSTreeNode<Type> *p);
BSTreeNode<Type> * Find(const Type &k, BSTreeNode<Type> *p );
//在p为根的二叉排序树上查找关键字为k的结点
void InOrder(BSTreeNode<Type> *r);
public:
BSTree() : root (NULL) {}//构造函数
Type Find ( const Type &k ) {//查找
BSTreeNode<Type>* p=Find ( k, root );
if(p==NULL){
cout<<"There is not a node that equals "<<k<<endl;
return NULL;
}
return p->data;
}
void Insert(const Type &x) { Insert ( x, root ); } //插入
void Delete(const Type &k) { Delete ( k, root ); } //删除
void SortDisplay(){InOrder(root);cout<<endl;}
};
template <class Type>
void BSTree<Type>::
Insert(const Type &x, BSTreeNode<Type> * &p) {
//在p为根的二叉排序树插入结点的递归算法
if ( p == NULL ) //空二叉树
p = new BSTreeNode<Type>(x); //创建数据元素x的结点
else if (x<p->data )
//在左子树插入
Insert ( x, p->leftChild );
else if ( x > p->data )
//在右子树插入
Insert ( x, p->rightChild );
else //结点x已存在
{
cout << "There has node x" << endl;
}
}
template <class Type>
BSTreeNode<Type> * BSTree<Type> ::
Find (const Type &k, BSTreeNode<Type> *p) {
//在p为根的二叉排序树上进行查找的递归算法
if ( p == NULL ) return NULL; //查找失败
else if ( k<p->data )
//在左子树上递归查找
return Find (k,p->leftChild );
else if (k>p->data )
//在右子树上递归查找
return Find ( k, p->rightChild );
else return p; //相等,查找成功
}
template <class Type>
void BSTree<Type> ::
Delete(const Type &k, BSTreeNode<Type> * &p){
//在p为根的二叉排序树上删除关键字为k的结点
if ( p != NULL ){
BSTreeNode<Type> * temp;
if ( k < p->data )
Delete ( k, p->leftChild );
else if ( k > p->data )
Delete ( k, p->rightChild );
else if ( p->leftChild != NULL && p->rightChild != NULL ){
BSTreeNode<Type> * tparent=p;
temp=p->rightChild;
while(temp->leftChild!=NULL){
tparent=temp;
temp=temp->leftChild;
}
p->data = temp->data;
if(tparent==p)
Delete ( p->data,tparent->rightChild );
else Delete ( p->data,tparent->leftChild );
}
else {
temp = p;
if ( p->leftChild == NULL )
p = p->rightChild;
else if ( p->rightChild == NULL )
p = p->leftChild;
delete temp;
}
}
}
template <class Type>
void BSTree<Type>::InOrder(BSTreeNode<Type>* r){
if(r!=NULL){
InOrder(r->leftChild);
cout<<r->data<<" ";
InOrder(r->rightChild);
}
}
void main (){
BSTree<int> a;
int x;
cout<<"输入序列:"<<" ";
for(int i=0;;i++){
cin>>x;
if(x==-1)break;
a.Insert(x);
}
cout<<endl;
cout<<"输出中序遍历序列应为:";
a.SortDisplay();
cout<<endl;
cout<<"输入需要删除的整数:"<<" ";
int y;
cin>>y;
cout<<endl;
cout<<"查找结果是:"<<a.Find(y)<<endl;
cout<<endl;
a.Delete(y);
cout<<"输出删除后的中序遍历序列应为:"<<" ";
a.SortDisplay();
}构建二叉排序树,依次输入56,78,34,45,85,45,36,91,84,78,两个45和78
题目中应该几乎没有这种情况吧,像这一题,可以先试着把后一个45插到原45的左子树下(其实右子树下也是一样的)然后按照平衡二叉树的规则去做变换,而结果的78由于本题里前一个78的右子树上已经有了节点了,也只能插在做子树上面。
ps:以上都是个人见解,因为实际中并未见过此例~
第一、香港服务器机房这里我们可以看到有提供四个大带宽方案,是全向带宽和国际带宽,前者适合除了中国大陆地区的全网地区用户可以用,后者国际带宽适合欧美地区业务。如果我们是需要大陆地区速度CN2优化的,那就需要选择常规的优化带宽方案,参考这里。CPU内存硬盘带宽流量价格选择E3-12308GB240GB SSD50M全向带宽不限999元/月方案选择E3-12308GB240GB SSD100M国际带宽不...
香港云服务器最便宜价格是多少钱一个月/一年?无论香港云服务器推出什么类型的配置和活动,价格都会一直吸引我们,那么就来说说香港最便宜的云服务器类型和香港最低的云服务器价格吧。香港云服务器最便宜最低价的价格是多少?香港云服务器只是服务器中最受欢迎的产品。香港云服务器有多种配置类型,如1核1G、2核2G、2核4G、8到16核32G等。这些配置可以满足大多数用户的需求,无论是电商站、视频还是游戏、小说等。...
SugarHosts 糖果主机商也算是比较老牌的主机商,从2009年开始推出虚拟主机以来,目前当然还是以虚拟主机为主,也有新增云服务器和独立服务器。早年很多网友也比较争议他们家是不是国人商家,其实这些不是特别重要,我们很多国人商家或者国外商家主要还是看重的是品质和服务。一晃十二年过去,有看到SugarHosts糖果主机商12周年的促销活动。如果我们有需要香港、美国、德国虚拟主机的可以选择,他们家的...
排序二叉树为你推荐
linux命令Linux 命令php文件php 格式文件 怎么打开?急!!!互动电视怎么用互动电视上网科学计算器说明书科学计算机具体怎么用?约束是什么意思爱不约束是什么意思申请信箱怎么样申请一个免费的信箱3g模块如何启用3G功能及初始化3G模块?监控软件安装监控系统安装教程安全证安全员证是不是全国通用的?安全证安全管理资格证和安全员证,之间的联系及区别是什么?需要满足什么条件才能考取这两个证呢?谢谢大家!
老域名失效请用户记下 政务和公益机构域名注册管理中心 vps安全设置 美国独立服务器 国外永久服务器 香港vps99idc 韩国加速器 免费ftp空间 双11抢红包攻略 最好看的qq空间 100m免费空间 刀片服务器是什么 赞助 免费网页申请 新世界服务器 网购分享 免费asp空间申请 免费主页空间 xshell5注册码 香港博客 更多