二叉树前序中序,后序中序,公共最近祖先的实现
注释中详细介绍了算法,故不再赘述。
无论是前序还是后序,一个节点的左子树和右子树都是可以看做是分开的,有一定规律可循,故可用递归进行实现。
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int len = 12;
char pre[len] = "ABDEHCFIJGK";
char mid[len] = "DBHEAIFJCKG";
typedef struct _Node{
char data;
struct _Node *left;
struct _Node *right;
}TreeNode, *Tree;
// 确定c在中序序列mid中的下标,假设树的各个节点的值各不相同
int position(char c) {
return strchr(mid, c) - mid;
}
/* 利用前序中序序列创建树
* i: 子树的前序序列字符串的首字符在pre[]中的下标
* j: 子树的中序序列字符串的首字符在mid[]中的下标
* len: 子树的字符串序列的长度
*/
void premidCreateTree(Tree &node, int i, int j, int len) {
if(len <= 0) {
node = NULL;
return;
}
node = new TreeNode;
node->data = pre[i];
int m = position(pre[i]);
// i+1 :该node节点的左子树前序序列字符串的首字符在pre[]中的下标
// j :该node节点的左子树中序序列字符串的首字符在mid[]中的下标
// m-j :该node节点的左子树字符串序列的长度
premidCreateTree(node->left, i+1, j, m-j);
// i+(m-j)+1 :该node节点的右子树前序序列字符串的首字符在pre[]中的下标
// m+1 :该node节点的右子树中序序列字符串的首字符在mid[]中的下标
// len-1-(m-j):该node节点的右子树字符串序列的长度
premidCreateTree(node->right, i+(m-j)+1, m+1, len-1-(m-j));
}
// 前序遍历树
void PreTravelTree(Tree &node) {
if(node) {
cout << node->data;
PreTravelTree(node->left);
PreTravelTree(node->right);
}
}
/* 利用后序中序序列创建树
* i: 子树的后序序列字符串的尾字符在post[]中的下标
* j: 子树的中序序列字符串的首字符在mid[]中的下标
* len: 子树的字符串序列的长度
*/
void PostMidCreateTree(PNode &pn, int i, int j, int len) {
if(len <= 0) {
node = NULL;
return;
}
pn = new Node;
pn->v = post[i];
int m = Position(post[i]);
PostMidCreateTree(pn->left, i-1-(len-1-(m-j)), j, m-j);//注意参数:m-j左子树的长度,len-1-(m-j)右子树的长度
PostMidCreateTree(pn->right, i-1, m+1, len-1-(m-j));
}
// 寻找两个节点的最近公共祖先,但是遇到下面这种情况时,会有bug
// A 寻找B,C的公共祖先,不能用此算法
// / \
// B D
// /
// C
int findPNode(Tree root, char a, char b, TreeNode** PNode){
if(root == NULL) return 0;
if(root->data == a || root->data == b) {
return 1;
}
int left = findPNode(root->left, a, b, PNode);
if(left == 2) return 2;
int right = findPNode(root->right, a, b, PNode);
if(right == 2) return 2;
if(left + right == 2) *PNode = root;
return left + right;
}
// 二叉树是普通的二叉树,节点只有left/right,没有parent指针。
//
// 10
// / \
// 6 14
// / \ / \
// 4 8 12 18
// / \
// 3 5
//
// 基本思想:记录从根找到node1和node2的路径,然后再把它们的路径用类似的情况一来做分析,比如还是node1=3,node2=8这个case.
// 我们肯定可以从根节点开始找到3这个节点,同时记录下路径3,4,6,10,类似的我们也可以找到8,6,10。
// 我们把这样的信息存储到两个vector里面,把长的vector开始的多余节点3扔掉,从相同剩余长度开始比较,4!=8, 6==6,我们找到了我们的答案。
bool findParentByVector(TreeNode* root, char NData, vector<TreeNode*>& path) {
if(root == NULL) return false;
if(root->data != NData) {
if(findParentByVector(root->left, NData, path)) {
path.push_back(root);
return true;
} else {
if(findParentByVector(root->right, NData, path)) {
path.push_back(root);
return true;
} else {
return false;
}
}
} else {
path.push_back(root);
return true;
}
}
TreeNode* findBstNode(TreeNode* root, char a, char b) {
vector<TreeNode*> path1;
vector<TreeNode*> path2;
bool find = false;
find |= findParentByVector(root, a, path1);
find &= findParentByVector(root, b, path2);
if(find) {
int minSize = path1.size() > path2.size() ? path2.size() : path1.size();
int th1 = path1.size() - minSize;
int th2 = path2.size() - minSize;
for(; th1 < (int)path1.size() && th2 < (int)path2.size(); th1++, th2++) {
if(path1[th1] == path2[th2]) {
return path1[th1];
}
}
}
return NULL;
}
int main() {
Tree root = NULL;
premidCreateTree(root, 0, 0, strlen(mid));
PreTravelTree(root);
TreeNode *PNode = NULL;
/*findPNode(root, 'D', 'B', &PNode);
cout << endl << PNode->data << endl;*/
PNode = findBstNode(root, 'I', 'G');
cout << endl << PNode->data << endl;
getchar();
return 0;
}
相关推荐
如果给出了遍历二叉树的前序序列和中序序列,则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。 [基本要求] 已知一棵二叉树的前序和中序序列,试设计完成下列任务的一个算法: (1)构造一棵二叉树...
实现了二叉树的前序递归创建,非递归层次创建,非递归前序加中序创建;前序、中序、后序的递归遍历以及前、中、后、层次的非递归遍历;操作方面,使用后序递归遍历实现了size()和height()方法;除此,还有find...
1、任意输入前序 + 中序序列或者中序 + 后序序列,生成二叉树 3、利用打印二叉树功能显示二叉树的逐步构造过程,使用自上而下的二叉树显示 4、使用EGE(xege.org) / SFML...
移除链表元素,反转链表,删除排序链表中的重复元素,有效的括号,用栈实现队列,二叉树的前序遍历,二叉树的中序遍历,二叉树的后序遍历,二叉树的层序遍历,二叉树的最大深度,对称二叉树,翻转二叉树,路径总和,二叉搜索树中...
二叉树的最近公共祖先 (medium) 二叉树的层序遍历 (medium) 验证二叉搜索树 (medium) 从前序与中序遍历序列构造二叉树 (medium) Array 在排序数组中查找元素的第一个和最后一个位置 (Easy) 搜索二维矩阵 (Easy) 螺旋...
(前序、中序、后序递归遍历)(实现其一) (3)把二叉树的叶子结点按从左到右的顺序连成一个单链表,表头指针为head。 二叉树按二叉链表方式存储,链接时用叶子结点的右指针域来存放单链表指针。遍历该链表输出...
一、实验目的: 1、掌握二叉树的结构特征,以及各种存储结构的特点及使用范围。 2、掌握用指针类型描述、访问和处理...3. 设顺序存储的二叉树中有编号为i和j的两个结点,请设计算法求出它们最近的公共祖先结点的编号。
1.2 对于二叉树T的两个结点n1和n2,我们应该选择二叉树T结点的前序、中序和后序中哪两个序列来判断结点n1必定是结点n2的祖先 1.4 已知一棵度为k的树中
5.4 二叉树存储结构及实现 5.4.1 顺序存储结构 具体步骤: (1)将二叉树按完全二叉树编号。 (2)将二叉树中的结点一编号顺序存储到一维数组中。 5.4.2 二叉链表 基本思想: 令二叉树的每个结点对应一个链表结点,...
gas station leetcode algorithm 记录一下学习算法的一些代码。 冗余连接 II 全排列 II 左叶子之和 ...把二叉搜索树转换为累加树 ...二叉树的最近公共祖先 岛屿的周长 单词拆分 单词拆分 II 有效的山脉数组 插入区间
二叉树的最近公共祖先.py 对称二叉树.py 二叉树的层次遍历.py 二叉树中最大路径和.py 二叉树的直径.py 把二叉搜索树转换为累加树.py 二叉树的所有路径.py 完全二叉树的节点个数.py 二叉树的锯齿形层次遍历.py 最大...
编写一个程序,确定二叉树的特征。如:每个节点的层次,从根到该节点的枝长(路径长度),子孙的个数及祖先的个数。每个节点在前序、中序、后序中的访问的序号。
236.二叉树的最近公共祖先.js 算法 algorithm 排序 搜索 回溯 递归 贪心 动态规划dp 二分法 leftpad 50.pow-x-n.js 69.x-的平方根.js 278.第一个错误的版本.js 374.猜数字大小.py 递归 recursion +
java lru leetcode 力码 不。 问题 解决方案 30 连接所有单词的子串 ...二叉树的最大深度 ...从前序和中序遍历构造二叉树 ...从中序和后序遍历构造...二叉树的最低公共祖先 , 255 在二叉搜索树中验证前序序列 270 最近二叉搜
* 基于链表节点实现二叉树节点 */ package dsa; public class BinTreeNode implements BinTreePosition { protected Object element;//该节点中存放的对象 protected BinTreePosition parent;//父亲 ...
6. 由前序和中序遍历重建二叉树 7. 用两个栈实现队列 8. 求旋转数组的最小数字 9. 斐波那契数列的第n项(青蛙跳台阶) 10. 二进制中1的个数 11. 数值的整数次方 12. 打印1到最大的n位数 13. O(1)时间删除链表...
的最低共同祖先-二叉树的最低公共祖先-二叉树最大路径和-消除游戏 深度优先搜索 -路径总和-路径总和 II -路径总和 III - 验证二叉搜索树-二叉树预序遍历-二叉树中序遍历-二叉树后序遍历-二叉搜索树中的中序后继- ...
* 二叉树节点ADT接口 */ package dsa; public interface BinTreePosition extends Position { //判断是否有父亲(为使代码描述简洁) public boolean hasParent(); //返回当前节点的父节点 public ...
二叉树两结点的最近共同祖先结点(leetcode 236) 排列组合算法 Tutorial Books Visual Code CS Interview : Code of 《剑指Offer:名企面试官精讲典型编程题(纪念版)》 : 2019年秋招计算机类面经 : Leetcode 题解 ...
2、实现1所要求的代码后,运行设计好的代码,将以下的几组整数序列建成搜索二叉树,并记录下它们的前序遍历序列和后序遍历序列: a. 1、3、5、7、9; b. 1、13、35、13、27; c. 50、25、78、13、44、...