当前位置:首页 > 芯闻号 > 充电吧
[导读]1、二叉树排序--1)一个无序整数数组--2)创建二叉树,数组第一个元素为根结点,数组中下一个元素小于根的值放左边,大于的放右边。--3)中序遍历,结果即为数组从小到大的排序。当n较大时,用快速排序、

1、二叉树排序

--1)一个无序整数数组

--2)创建二叉树,数组第一个元素为根结点,数组中下一个元素小于根的值放左边,大于的放右边。

--3)中序遍历,结果即为数组从小到大的排序。

当n较大时,用快速排序、堆排序或归并排序。

当待排序的关键字是随机分布时,快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。

堆排序和快速排序都是不稳定的。

若要求排序稳定,可选用归并排序。但从单个记录起进行两两归并的排序算法并不值得提倡。通常可以将它和直接插入排序结合在一起使用。

稳定排序:直接插入排序、冒泡排序、归并排序

不稳定:堆排序、快速排序、希尔排序、选择排序

2、代码实现

#includeusing namespace std;
#define dim(x) (sizeof(x)/sizeof(x[0]))

void swap(int *x,int *y)
{
	int t = *x;
	*x = *y;
	*y = t;
}
//定义二叉树结构体
struct NODE
{
	int iData;
	NODE *pLChild;
	NODE *pRChild;
};
//中序遍历
void InOrder(NODE *node)
{
	if(node == NULL) return;
	InOrder(node->pLChild);
	printf("%d ",node->iData);
	InOrder(node->pRChild);
}
//创建二叉树
NODE * TreeSort(const int sz[],const int nLen)
{
	//先创建好所有结点
	NODE *tree = new NODE[nLen];
	for(int i=0;i<nLen;i++)
	{
		tree[i].iData = sz[i];
		tree[i].pLChild = NULL;
		tree[i].pRChild = NULL;
	}
	//根据规则,建立结点间的关系
	NODE *pRoot = &tree[0]; //根结点选择数组第一个元素
	for(int i=1;i<nLen;i++)
	{
		NODE *pCur = pRoot;
		bool bGo = true; //控制跳出循环的
		while(bGo)
		{
			//判断新加入的结点是不是比当前节点小
			while(tree[i].iData iData)
			{
				if(pCur->pLChild == NULL)
				{
					pCur->pLChild = &tree[i];
					bGo = false;
					break;
				}
				pCur = pCur->pLChild;
			}
			//判断新加入的结点是不是比当前节点大
			while(tree[i].iData > pCur->iData)
			{
				if(pCur->pRChild == NULL)
				{
					pCur->pRChild = &tree[i];
					bGo = false;
					break;
				}
				pCur = pCur->pRChild;
			}
		}
	}
	return pRoot;
}

void main()
{
	int a[] = {49,38,65,97,76,13,27};
	NODE *pRoot = TreeSort(a,dim(a));
	InOrder(pRoot);
	printf("n");
	delete pRoot;
	system("pause");
}

输出:

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

草木曼发,春山可望。3月28日以“凝聚·同行”为主题的2024鲸鸿动能开发者精英会首站在昆明启动。大会深度聚焦阅读、短剧等行业应用,吸引了40多位杰出开发者参与,共同探讨流量商业化新路径,挖掘鸿蒙生态下新的增长机遇。

关键字: 元服务 HarmonyOS 鲸鸿动能

作为年轻人群高度聚集的视频社区,哔哩哔哩在汇聚海量年轻用户、构建优质内容生态的同时,也在不断加大新技术的投入,为用户打造更智能、更安全、更流畅的使用体验。近日,哔哩哔哩宣布完成鸿蒙原生应用Beta版本开发,该版本已具备完...

关键字: 哔哩哔哩 鸿蒙

阔别六年,行业年度盛事 - “CHINAPLAS国际橡塑展”将重磅回归上海,于2024年4月23 - 26日在上海国家会展中心(虹桥)盛装绽放。开幕在即,“国际橡塑展回归上海启航盛典”3月28日在上海举办,线下160多位...

关键字: 智能制造 橡塑科技 新能源汽车

在3月26-29日举行的博鳌亚洲论坛上,三星的绿色发展和科技创新等实践,成为了与会者关注的焦点。

关键字: 三星电子

近日有网友在职场内容社区发布消息称,据相关员工内部消息,某大厂开始裁员,裁员比例10%到30%。该消息中点名的PCG、CSIG事业群,均为腾讯公司下属事业群。从腾讯多位知情人士了解到,该消息为假消息。

关键字: 腾讯 裁员

业内消息,近日杭州市规划部门称位于浙江的“蚂蚁之江总部”已退地。值得一提的是,蚂蚁二期地块早已退地,如今一期的退地也得到了官方回复。

关键字: 蚂蚁集团 阿里巴巴

近日从国家知识产权局官网获悉,华为技术有限公司公布了一项名为“一种光模块、光通信设备及光通信系统“的专利,公开号CN117767976A。专利摘要显示,本申请涉及光通信技术领域,尤其涉及一种光模块、光通信设备及光通信系统...

关键字: 华为 光通信 专利

业内消息,近日外媒报道国内游戏巨头腾讯内部正在发生一场巨变,一款可爱角色克服障碍的简单易玩游戏已经被放在了优先开发位置,而以往备受青睐的一款高成本、复杂的外国IP手游则被冷落。

关键字: 腾讯 游戏

市场分析机构 Canalys 发布的最新数据显示,2023 年中国大陆 PC 市场(不含平板)出货量前五的厂商中,除华为实现增长(11%)外其余均下跌,其中戴尔的出货量仅剩 314.8 万台,环比下滑 44%,近乎腰斩。

关键字: 裁员 芯片 戴尔

最近AI圈突然流行起开源概念。Meta承诺将会打造开源AI,马斯克起诉OpenAI,说它缺少开源模型。与此同时,一批科技领袖和科技企业纷纷为开源概念呐喊。不过科技界碰到一个难以解决的根本问题:它们对“开源AI”的概念无法...

关键字: 开源AI 开源软件 Meta OpenAI
关闭
关闭