1.二叉树三种周游(traversal)方式:
3.如何判断一棵二叉树是否是平衡二叉树
4.设计一个算法,找出二叉树上任意两个节点的最近共同父结点,复杂度如果是O(n2)则不得分。
5.如何不用递归实现二叉树的前序/后序/中序遍历?
6.在二叉树中找出和为某一值的所有路径(注意是到叶子节点)
7.怎样编写一个程序,把一个有序整数数组放到二叉树中?
8.判断整数序列是不是二叉搜索树的后序遍历结果
9.求二叉树的镜像
10.一棵排序二叉树(即二叉搜索树BST),令 f=(最大值+最小值)/2,设计一个算法,找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
11.把二叉搜索树转变成排序的双向链表
12.打印二叉树中的所有路径(与题目6很相似)
解决思路:
1.二叉树三种周游(traversal)方式:任何一本数据结构的书都有描述,略过;
2.怎样从顶部开始逐层打印二叉树结点数据?
设置一个队列,然后只要队列不为空,将对首元素的左右孩子加入队列(如果左右孩子不为空),然后将队列的首元素出对即可,如下图所示:
二叉树如下图所示:
那么,整个过程如下:
自然,就输出了a,b,c,d,e,f
3.如何判断一个二叉树是否是平衡的?
太简单了,利用递归就可以了:判断根节点的左右子树深度之差是否小于等于1(这里需要用到求深度的方法),如果是,根节点就是平衡的;然后,在判断根节点的左孩子和右孩子是否是平衡的。如此继续下去,直到遇见叶子节点。一旦不是,立刻返回false;
计一个算法,找出二叉树上任意两个节点的最近共同父结点,复杂度如果是O(n2)则不得分
首先找到这两个点key1和key2,并且记录下找到这两个点的路径Path1和Path2。然后,找到第一个点k满足,key1<k<key2就可以了。
如图:
假设key1 = 5,key2 = 7,那么显然,Path1{8,6,5}, Path2{8,6,7}。满足第一个key1<k<key2的k为6。故k = 6。
至于怎么求出Path1和Path2,可以看问题12。
5.如何不用递归实现二叉树的前序/后序/中序遍历?(网易面试就问到了,悲剧了,当时一下子卡住了)
看看书,基本任何一本数据结构的书都有,主要利用栈。
6.在二叉树中找出和为某一值的所有路径?
还是先解决12题目,访问二叉树到叶子节点的任意路径。这个问题解决了,自然求和看是否满足条件就可以了。
7.怎样编写一个程序,把一个有序整数数组放到二叉树中?
递归,还是利用递归:
设有int array[begin,end],首先将array[(begin + end)/2]加入二叉树,然后递归去做array[begin,(begin + end)/2 - 1]和array[(begin + end)/2 + 1, end]。注意写好函数的形式就可以了。一切都很自然。
8.判断整数序列是不是二叉搜索树的后序遍历结果?
看看吧,后续遍历是这样做的:左右根,所以访问的最有一个节点实际上就是整棵二叉树的根节点root:然后,找到第一个大于该节点值的根节点b,b就是root右子树最左边的节点(大于根节点的最小节点)。那么b前面的就是root的左子树。既然是二叉搜索树的遍历结果,那么在b和root之间的遍历结果,都应该大于b。去拿这个作为判断的条件。
9.求二叉树的镜像?
还是利用递归:只要节点不为空,交换左右子树的指针,然后在分别求左子树的镜像,再求右子树的镜像,直到节点为NULL。
10.一棵排序二叉树(即二叉搜索树BST),令 f=(最大值+最小值)/2,设计一个算法,找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
首先,在BST中,最小值就是最左边的节点,最大值就是最右边的节点。
在分别求出min和max后,求出f。然后利用查找,找出一个大于f的节点就可以了。
复杂度为logN。
11.把二叉搜索树转变成排序的双向链表
12..打印二叉树中的所有路径
路径的定义就是从根节点到叶子节点的点的集合。
还是利用递归:用一个list来保存经过的节点,如果已经是叶子节点了,那么打印list的所有内容;如果不是,那么将节点加入list,然后继续递归调用该函数,只不过,入口的参数变成了该节点的左子树和右子树。
程序如下:
- 解答1:自己看书了
- 解答2:
-
-
voidPrintAtLevel(BiTNode*root){
- vector<BiTNode*>vector;
- vector.push_back(root);
-
while(!vector.empty()){
- BiTNode*tmp=vector.front();
-
if(tmp->lchild!=NULL)
- vector.push_back(tmp->lchild);
-
if(tmp->rchild!=NULL)
- vector.push_back(tmp->rchild);
- cout<<tmp->data<<endl;
- vector.pop_back();
- }
- }
-
-
intisBalencedTree(treeNode*root){
-
if(root==NULL)
-
return0;
-
intdepth1=getDepth(root->lchild);
-
intdepth2=getDepth(root->rchild);
-
if(depth1==depth2||depth1==depth2+1||depth1==depth2-1)
-
return1;
-
else
-
return0;
-
intflag1=isBalencedTree(root->lchild);
-
intflag2=isBalencedTree(root->rchild);
-
if(flag1&&flag2)
-
return1;
-
else
-
return0;
- }
-
- 则不得分。
-
intgetPublicAncestors(treeNode*root,intkey1,intkey2){
- treeNode*ptr=root;
-
intpath1[1000];
-
intpathLen1=0;
-
while(ptr!=NULL){
-
if(key1==ptr->data){
- path1[pathLen1]=ptr->data;
- pathLen1++;
- printArray(path1,pathLen1);
-
break;
- }
-
else
-
if(ptr->data>key1){
- path1[pathLen1]=ptr->data;
- pathLen1++;
- ptr=ptr->lchild;
- }
-
else
-
if(ptr->data<key1){
- path1[pathLen1]=ptr->data;
- pathLen1++;
- ptr=ptr->rchild;
- }
- }
- ptr=root;
-
intpath2[1000];
-
intpathLen2=0;
-
while(ptr!=NULL){
-
if(key2==ptr->data){
- path2[pathLen2]=ptr->data;
- pathLen2++;
- printArray(path2,pathLen2);
-
break;
- }
-
else
-
if(ptr->data>key2){
- path2[pathLen2]=ptr->data;
- pathLen2++;
- ptr=ptr->lchild;
- }
-
else
-
if(ptr->data<key2){
- path2[pathLen2]=ptr->data;
- pathLen2++;
- ptr=ptr->rchild;
- }
- }
-
inti=pathLen1-1;
-
-
if(key2<key1){
- key2=key2^key1;
- key1=key2^key1;
- key2=key2^key1;
- }
-
for(;i>0;i--){
-
if(key1<path1[i]&&path1[i]<key2){
-
intresult=path1[i];
-
returnresult;
- }
- }
- }
-
-
voidFindPath(treeNode*root,intpath[],intpathLen,intexpectedSum,int
- currentSum){
-
if(root==NULL)
-
return;
- currentSum+=root->data;
- path[pathLen]=root->data;
- pathLen++;
-
if(currentSum==expectedSum&&root->lchild==NULL&&root->rchild==
- NULL){
- printArray(path,pathLen);
- }
-
if(root->lchild!=NULL){
- FindPath(root->lchild,path,pathLen,expectedSum,currentSum);
- }
-
if(root->rchild!=NULL){
- FindPath(root-
- >rchild,path,pathLen,expectedSum,currentSum);
- }
- currentSum-=root->data;
- }
-
-
voidcreateTreeFromArray(inta[],intbegin,intend,treeNode**root){
-
if(begin>end)
-
return;
-
else{
-
*root=(treeNode*)malloc(sizeof(treeNode));
-
intmid=(begin+end)/2;
- (*root)->data=a[mid];
- (*root)->rchild=NULL;
- (*root)->lchild=NULL;
- createTreeFromArray(a,begin,mid-1,&(*root)->lchild);
- createTreeFromArray(a,mid+1,end,&(*root)->rchild);
- }
- }
-
-
intisPostTraverse(inta[],intbegin,intend){
-
if(begin>=end)
-
return1;
-
else{
-
introot=a[end];
-
intlroot;
-
inti;
-
intlocation=begin;
-
for(i=begin;i<end;i++){
-
if(a[i]>root){
- location=i;
- lroot=a[i];
-
break;
- }
- }
-
for(i=location+1;i<end;i++){
-
if(a[i]<lroot){
-
return0;
- }
- }
-
intflag1=isPostTraverse(a,begin,location-1);
-
intflag2=isPostTraverse(a,location,end-1);
-
if(flag1&&flag2)
-
return1;
-
else
-
return0;
- }
- }
-
-
voidchangeMirror(treeNode**root){
-
if(*root==NULL)
-
return;
-
else{
- treeNode*temp=(*root)->lchild;
- (*root)->lchild=(*root)->rchild;
- (*root)->rchild=temp;
- changeMirror(&(*root)->lchild);
- changeMirror(&(*root)->rchild);
- }
- }
-
-
-
intfindNearMid(treeNode**root){
- treeNode*ptr=*root;
-
intmin,max;
-
while(ptr!=NULL){
- min=ptr->data;
- ptr=ptr->lchild;
- }
-
printf("theminis%d\n",min);
- ptr=*root;
-
while(ptr!=NULL){
- max=ptr->data;
- ptr=ptr->rchild;
- }
-
printf("themaxis%d\n",max);
-
inthalf=(min+max)>>1;
-
printf("halfis%d\n",half);
- ptr=*root;
-
while(1){
-
if(ptr->data<half){
- ptr=ptr->rchild;
- }
-
else
-
if(ptr->data>half){
-
intresult=ptr->data;
-
returnresult;
- }
-
else
- {
-
return(ptr->rchild)->data;
- }
- }
- }
-
-
voidprintPathsRecur(treeNode*node,intpath[],intpathLen){
-
if(node==NULL)
-
return;
-
- path[pathLen]=node->data;
- pathLen++;
-
-
if(node->lchild==NULL&&node->rchild==NULL){
- printArray(path,pathLen);
-
}else{
-
- printPathsRecur(node->lchild,path,pathLen);
- printPathsRecur(node->rchild,path,pathLen);
- }
- }
-
voidprintPaths(treeNode*node){
-
intpath[1000];
- printPathsRecur(node,path,0);
- }
-
-
-
intgetDepth(tNoderoot){
-
if(root==NULL)
-
return0;
-
else
-
returngetDepth(root->lchild)>getLeaf(root->rchild)?1+
- getDepth(
- root->lchild):1+getDepth(root->rchild);
-
-
-
-
- depthRchild;
-
- }
-
-
voidprintArray(intints[],intlen){
-
inti;
-
for(i=0;i<len;i++){
-
printf("%d",ints[i]);
- }
-
printf("\n");
- }
分享到:
相关推荐
比如上图正常的一个满节点,A:根节点、B:左节点、C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右);中序顺序是BAC(先左后根最后右);后序顺序是BCA(先左后右最后根)。 比如上图二叉树遍历结果 ...
1本程序在vc++6.0编译通过并能正常运行。 2主界面 程序已经尽量做到操作简便了,用户只需要根据提示一步步进行操作就行了。 六思考和总结: 这个课程设计的各个基本操作大部分都在我的综合性实验中实现了,所以做...
第1部分介绍多核编程的基础知识,包括多核编程常见问题、锁竞争、加速比、负载均衡等基本概念,多线程退出算法、读写锁、旋转锁、原子操作等多线程编程基础知识,基于OpenMP标准的并行程序设计基础等; 第2部分介绍...
1. 对一个算法的评价,不包括如下( )方面的内容。 A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度 2. 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行( )。 A. p->next=HL->next; ...
产生霍夫曼编码需要对原始数据扫描两遍,第一遍扫描要精确地统计出原始数据中的每个值出现的频率,第二遍是建立霍夫曼树并进行编码,由于需要建立二叉树并遍历二叉树生成编码,因此数据压缩和还原速度都较慢,但简单...
printf("2,由遍历序列恢复二叉树算法。\n"); printf("3,Dijkstra算法。\n"); printf("4,希尔排序算法。\n"); printf("5,Kruskal算法。\n"); printf("6,基数排序算法。\n"); printf("7,关键路径算法。\n"); ...
本书的目标是使你在C语言程序设计方面由一位初学者成为一位称职的程序员。 内容简介 本书是编程语言先驱者Ivor Horton的经典之作,是C语言方面最畅销的图书品种之一。本书集综合性、实用性为一体,是学习C语言...
讲解数据结构的常见算法及其代码,以及整个程序原代码,适合广大初级以及入门朋友学习 参考!数据结构与算法基本程序目录 一、 线性表及其操作 1、 尾插法建立一个单链表,并按顺序输出 2、 单链表的元素查找,按...
◆ 说明了类和ADT在问题解决过程中的作用 ◆ 诠释了ADT的主要应用,如查找航班图、事件驱动的模拟和八皇后问题 ◆ 大部分章节中的例子都使用了标准模板库(STL) ◆ 介绍了递归 ◆ 附录中提供了基本的C++语法,以...
算法设计:研究如何将解决问题的步骤形式化为一系列指令,使得计算机可以执行以求解问题。 算法特性:包括输入、输出、有穷性、确定性和可行性。即一个有效的算法必须能在有限步骤内结束,并且对于给定的输入产生...
150个编程题问答从二叉树到二分查找,该部分涵盖了关于数据结构和算法的最常见、最有用的面试题以及最为精巧的解决方案。应对棘手算法题的5种行之有效的方法通过这5种方法,你可以学会如何处理并攻克算法难题,包括...
算法设计:研究如何将解决问题的步骤形式化为一系列指令,使得计算机可以执行以求解问题。 算法特性:包括输入、输出、有穷性、确定性和可行性。即一个有效的算法必须能在有限步骤内结束,并且对于给定的输入产生...
《数据结构》(C语言版) 算法源码及运行演示系统使用说明 一、启动演示系统 双击演示系统应用程序文件“DS_VC_ALGO.EXE”启动演示系统,出现图1所示界面。 <br> <br> <br> <br> <br> ...
《数据结构》(C语言版) 算法源码及运行演示系统使用说明 一、启动演示系统 双击演示系统应用程序文件“DS_VC_ALGO.EXE”启动演示系统,出现图1所示界面。 <br> <br> <br> <br> <br> ...
150个编程题问答从二叉树到二分查找,该部分涵盖了关于数据结构和算法的最常见、最有用的面试题以及最为精巧的解决方案。应对棘手算法题的5种行之有效的方法通过这5种方法,你可以学会如何处理并攻克算法难题,包括...
满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。 完全...
能熟练使用各种数据结构解决各种问题,设计良好的数据结构。 4. 能理解数据结构在程序设计中的重要性。 5. 熟练掌握插入排序、Shell排序、堆排序、快速排序、基数排序等常用的各种排序算法及其时间和空间开销。...
《妙趣横生的算法(C语言实现)》可作为算法入门人员的教程,也可以作为学习过C语言程序设计的人士继续深造的理想读物,也可作为具有一定经验的程序设计人员巩固和提高编程水平,查阅相关算法实现和数据结构知识的参考...
算法6.5是中序遍历线索二叉树的非递归算法,要对其源码进行测试,可首先调用算法6.6及6.7建立中序线索二叉树。以下是测试程序的源码,相关类型和辅助函数定义在文件include06.h和include06.cpp中,此略。 // test...
2、掌握栈、队列的常见算法的程序实现。 四、实验内容: 1、用顺序存储定义栈结构。写出这种存储方式下的算法实现,包括:初始化栈、判栈为空、出栈、入栈、求栈顶元素等运算,自己填写主函数。 2、利用顺序栈的基本...