热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

2018.5.23(二叉树中序遍历中查找某一结点的后继结点)

#include#include#includeusingnamespacestd;structTree{intdata;Tr

#include
#include
#include
using namespace std;
struct Tree
{
int data;
Tree *parent;//存储某一结点的父结点
Tree *left,*right;
};
Tree *Insert(Tree *root,const int node)//插入元素,使其符合二叉树的结构
{
Tree *parent_point,*current_point;
Tree *new_point;
new_point=(Tree*)malloc(sizeof(Tree));//新开辟一块new_point的空间,使其left,right,parent都指向NULL
new_point->data=node;
new_point->parent=NULL;
new_point->left=NULL;
new_point->right=NULL;
if(root==NULL)
return new_point;
current_point=root;
while(current_point!=NULL)
{
parent_point=current_point;
current_point=(node>current_point->data)?current_point->right:current_point->left;//判断某一数值该放到当前结点的左子树上还是该结点的右子树上
}
if(node>parent_point->data)
{
parent_point->right=new_point;
new_point->parent=parent_point;
}
else
{
parent_point->left=new_point;
new_point->parent=parent_point;
}
return root;
}
Tree *Create(const int *node,const int len)
{
Tree *root=NULL;
for(int i=1;i<=len;i++)
root=Insert(root,node[i]);
return root;
}
Tree *Find(Tree *node,int num)//查找结点位置
{
while(node!=NULL&&node->data!=num)//node!=NULL一定要在node->data!=num前,如果在其后,当node==NULL时,node->data就是非法调用,会出错
node=(num>node->data)?node->right:node->left;//有二叉树的结构可知,左子树的值都小于其父结点,右子树的值都大于其父结点,故只需判断num与node->data的相对大小,如果num大,则node向其右子树方向去,反之,向其左子树方向去
return node;
}
void Solve(Tree *node)//查找后继元素
{
printf("%d->",node->data);
if(node->right!=NULL)//如果需查找的结点存在右子树
{
node=node->right;
while(node!=NULL&&node->left!=NULL)//查找当前节点右子树最左端的结点
node=node->left;
if(node!=NULL)
printf("%d\n",node->data);
else
printf("NULL\n");
return ;
}
if(node->right==NULL)//如果需查找的结点不存在右子树
{
while(node->parent->left!=node)//判断当前结点的父节点的左子树是否等于当前结点;
{
node=node->parent;//如果没找到满足条件的结点,当前结点指向其父节点
if(node->parent==NULL)//如果便利到根节点也没有找到其后继结点,说明其需查找的结点不存在后继结点,返回NULL;
{
printf("NULL\n");
return ;
}
}
printf("%d\n",node->parent->data);//如果while()中未执行printf("NULL\n");语句,说明其存在后继结点,打印出找到结点的父节点
return ;
}
}
void print(Tree *root)
{
if(root!=NULL)
{
print(root->left);
printf("%d ",root->data);
print(root->right);
}
}
int main()
{
Tree *root;
int n;
printf("Input n:\n");
while(cin>>n)
{
if(n==0)
break;
int node[n+1];
printf("\nInput %d numbers\n",n);
for(int i=1;i<=n;i++)
scanf("%d",&node[i]);
root=Create(node,n);
printf("***中序遍历***\n");
print(root);
printf("\n");
int num;
printf("\nInput some numbers:\n");
while(cin>>num)
{
if(num==0)
break;
Tree *find_num=Find(root,num);
if(find_num==0)
printf("No Find!\n");
else
Solve(find_num);
}
printf("\nInput n:\n");
}
return 0;
}

查找后继元素解析:
当n=9时
9个数分别为6,3,8,5,2,9,4,7,10;
其树形结构为:

《2018.5.23(二叉树-中序遍历中查找某一结点的后继结点)》
中序遍历结果为:2,3,4,5,6,7,8,9,10
如何查找某一节点的后继元素?
思路:
当某一结点存在右子树时,其后继结点为其右子树上最左的结点,例如元素3的后继节点为其右子树(元素5)最左的结点(元素4),故3的后继结点为4;
当某一结点不存在右子树时,其后继结点为第一个当前结点的父结点的左子树与当前结点相等的结点的父结点,例如,若查找元素5的后继结点,先判断其是否存在右子树,结果为不存在,去找此结点的父结点,为元素3,判断当前结点(元素5)的父节点的左子树元素2)是否与当前结点(元素5)相同,,继续向上找,当前结点来到元素5的父节点元素3位置,判断当前结点(元素3)的父节点的左子树元素3)是否为当前结点(元素3)的结点,,故第一个满足条件的结点为元素3,其父节点为元素6,故元素5的后继结点为元素6;


推荐阅读
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
  • Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意:给你一个的表格,你 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 本题涉及一棵由N个节点组成的树(共有N-1条边),初始时所有节点均为白色。题目要求处理两种操作:一是改变某个节点的颜色(从白变黑或从黑变白);二是查询从根节点到指定节点路径上的第一个黑色节点,若无则输出-1。 ... [详细]
  • 本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率,使用经典的EK(Edmonds-Karp)和Dinic算法进行求解。 ... [详细]
  • 在多线程编程环境中,线程之间共享全局变量可能导致数据竞争和不一致性。为了解决这一问题,Linux提供了线程局部存储(TLS),使每个线程可以拥有独立的变量副本,确保线程间的数据隔离与安全。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 本文探讨了如何在模运算下高效计算组合数C(n, m),并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元,从而实现除法取余的计算。 ... [详细]
  • 本题通过将每个矩形视为一个节点,根据其相对位置构建拓扑图,并利用深度优先搜索(DFS)或状态压缩动态规划(DP)求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]
author-avatar
手机用户2602913291
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有