首页 > 代码库 > 【编程之美】3.9重建二叉树
【编程之美】3.9重建二叉树
题目：
给定一棵二叉树，假定每个节点都用唯一的字符表示，具体结构如下：
struct NODE {
NODE* pLeft;
NODE* pRight;
char chValue;
};
NODE* pLeft;
NODE* pRight;
char chValue;
};
假设已经有了前序遍历和中序遍历结果，希望通过一个算法重建这棵树。
给定函数的定义如下：
void Rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot);
参数
pPreOrder:前序遍历结果的字符串数组。
pInOrder: 中序遍历结果的字符串数组。
nTreeLen: 树的长度。
pRoot: 根据前序和中序遍历结果重新构建树的根节点。
例如
前序遍历结果：a b d c e f
中序遍历结果：d b a e c f
思路：不难，根据前序遍历结果找跟，根据中序遍历结果划分左右子树，递归求解。
/*start time = 15:55end time = 16:23*/#include<iostream>using namespace std;typedef struct NODE{ NODE *pLeft, *pRight; char chValue;}NODE;void Rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot){ if(pPreOrder == NULL || pInOrder == NULL) //边界条件不要忘了 这是看答案后补上的 { return; } if(nTreeLen <= 0) { return; } //重建根节点 一定是先序遍历的第一个值 *pRoot = new NODE; (*pRoot)->chValue = http://www.mamicode.com/pPreOrder[0]; (*pRoot)->pLeft = NULL; (*pRoot)->pRight = NULL; //查找根在中序遍历中的位置，把中序遍历表转化为左子树和右子树两个部分 int iLocateRoot; for(iLocateRoot = 0; iLocateRoot < nTreeLen; iLocateRoot++) { if(pInOrder[iLocateRoot] == pPreOrder[0]) { break; } } //重建左子树 Rebuild(pPreOrder+1, pInOrder, iLocateRoot, &((*pRoot)->pLeft)); //重建右子树 Rebuild(pPreOrder+iLocateRoot+1, pInOrder + iLocateRoot + 1, nTreeLen - iLocateRoot - 1, &((*pRoot)->pRight));}int main(){ char pre[7] = {‘a‘,‘b‘,‘d‘,‘c‘,‘e‘,‘f‘,‘\0‘}; char in[7] = {‘d‘,‘b‘,‘a‘,‘e‘,‘c‘,‘f‘,‘\0‘}; NODE * T = NULL; Rebuild(pre, in, 7, &T); return 0;}
【编程之美】3.9重建二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。