《编程之美》读书笔记19: 3.9 重建二叉树
对根节点a以及先序遍历次序P和中序遍历次序I,查找a在I中的位置,将I分为两部分,左边部分的元素都在a的左子树上,右边的元素都在a的右子树上,因而可以确定a的左子树节点数和a的右子树节点数,再结合P,可以确定a的左孩子和右孩子,以及各个孩子的先序和中序遍历次序。
由于已经知道节点数,可以事先分配好内存,可以按先序遍历次序连续存放节点。
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
rebuild_tree_1
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Node
{
Node* left;
Node* right;
char data;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void rebuild(char preorder[], char inorder[], Node result[], size_t size)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
result->data = *preorder;
result->left=NULL;
result->right=NULL;
char *p = inorder;
size_t left_size=0;
while (left_size<size && *p++!=*preorder) ++left_size;
assert (left_size<size);
size_t right_size = size-1-left_size;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (left_size)
{
result->left=result+1;
rebuild(preorder+1, inorder, result+1, left_size);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (right_size)
{
result->right=result+left_size+1;
rebuild(preorder+left_size+1, inorder+left_size+1,
result+left_size+1, right_size);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
上面的代码,栈深度是O(n),有可能出现栈溢出,可以修改代码,减少一次递归调用,实现栈深度为O(lg n)。
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
rebuild_tree_2
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void rebuild2(char preorder[], char inorder[], Node result[], size_t size)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (1)
{
result->data = *preorder;
result->left=NULL;
result->right=NULL;
char *p = inorder;
size_t left_size=0;
while (left_size<size && *p++!=*preorder) ++left_size;
assert (left_size<size);
size_t right_size = size-1-left_size;
if (left_size==0 && right_size==0) break;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (left_size<right_size)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (left_size)
{
result->left=result+1;
rebuild2(preorder+1, inorder, result+1, left_size);
}
result->right=result+left_size+1;
preorder += left_size+1;
inorder += left_size+1;
result += left_size+1;
size = right_size;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
} else
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (right_size)
{
result->right=result+left_size+1;
rebuild2(preorder+left_size+1, inorder+left_size+1,
result+left_size+1, right_size);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (left_size)
{
result->left=result+1;
++preorder;
++result;
size = left_size;
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
书上的代码(P246):
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
NODE* pTemp = new NODE;
pTemp -> chValue = *pPreOrder;
pTemp -> pLeft = NULL;
pTemp -> pRight = NULL;
// 如果节点为空,把当前节点复制到根节点
if(*pRoot == NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
*pRoot = pTemp;
}
可能引起内存泄漏(当*pRoot!=NULL,新申请的内存没释放),注释也不对(不是复制节点,而是更改指针指向新建的节点)。另外,频繁的new,极有可能会产生内存碎片。当节点很小时,内存浪费很严重(每new一次都要额外分配空间储存相关信息)。