基于中序遍历找到一个结点的后继结点
遍历 一个 基于 找到 结点 中序
2023-09-14 09:07:58 时间
题目:
基于中序遍历找到一个结点的后继结点。
分析:
首先明白中序遍历,顺序为:左--->根----->右
如果当前结点为p。
有两种情况:
1.当p有右子树时,那么其右子树的最左结点即为所求:
2.当p没有右子树时。有以下两种情况:
沿着p向上找,假设p的父结点的左孩子是p。那么该父结点即为所求。否则继续向上找。
代码:
/* 找到中序遍历下一个结点的后继结点 by Rowandjj 2014/8/19 */ #include<iostream> using namespace std; typedef struct _NODE_ { int data; struct _NODE_ *left; struct _NODE_ *right; struct _NODE_ *parent; }Node,*pNode,*pTree; //找到中序遍历时,p的后继结点 pNode after(pNode p) { if(p == NULL) { return NULL; } if(p->right != NULL)//存在右子树 {//找到右子树中的最左结点 pNode pTemp = p->right; while(pTemp->left) { pTemp = pTemp->left; } return pTemp; }else//不存在右子树 {//那么找到该结点的父结点,若当前结点是父结点的左孩子那么父结点即为所求 //否则继续向上寻找 pNode pParent = p->parent; while(pParent && pParent->right == p) { p = pParent; pParent = p->parent; } return pParent; } } //构建 void create(pTree *pRoot,pNode pParent) { int data; cin>>data; if(data == -1) { return; } *pRoot = (pNode)malloc(sizeof(Node)); if(*pRoot == NULL) { exit(-1); } (*pRoot)->data = data; (*pRoot)->left = NULL; (*pRoot)->right = NULL; (*pRoot)->parent = pParent; create(&(*pRoot)->left,*pRoot); create(&(*pRoot)->right,*pRoot); } //中序遍历 void display(pTree pRoot) { if(pRoot == NULL) { return; } if(pRoot->left != NULL) { display(pRoot->left); } cout<<pRoot->data<<" "; if(pRoot->right != NULL) { display(pRoot->right); } } int main() { pTree pTree = NULL; create(&pTree,NULL); // pNode p1 = pTree->left->right; // cout<<p1->data<<endl; // cout<<p1->parent->data<<endl; // cout<<after(pTree)->data; //cout<<after(pTree->left->right)->data<<endl; cout<<after(pTree->left)->data<<endl; display(pTree); return 0; }
相关文章
- 图的遍历及应用
- 遍历ArrayList并移除一个元素[通俗易懂]
- 【说站】java数组如何遍历全部的元素
- 树的先序遍历对应二叉树的_先序遍历输入一个二叉树
- hashmap遍历keyset_怎么遍历一个map
- 编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。
- 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
- 你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。
- Java遍历数组逗号的使用[通俗易懂]
- 在VB中遍历文件并用正则表达式完成复制及vb实现重命名、拷贝文件夹的方法
- 使用MySQL 8的递归CTE遍历树
- 图的遍历(深度优先搜索和广度优先搜索)
- java增强型for循环(三种遍历集合方式)详解编程语言
- Go语言遍历字符串——获取每一个字符串元素
- MySQL中 的遍历查询:一个简洁而又强大的方式(mysql遍历查询结果)
- PHP遍历MySQL:从基本循环到高效操作(php遍历mysql)
- Oracle临时表遍历背后的原理(oracle 临时表原理)
- 一个目录遍历函数
- FSO遍历目录实现全站插马的代码
- php遍历目录viewDir函数
- SQLServer遍历表中记录的2种方法(使用表变量和游标)
- JAVA遍历一个文件夹中的所有文件的小例子
- python两种遍历字典(dict)的方法比较
- jquery进行数组遍历如何跳出当前的each循环