二叉树的三种遍历常用于恢复:先序,中序,后序。对于先+中,后+中这两种组合,对任意二叉树的恢复都有唯一解,但对先+后的情况则不是,这种情况下要满足要求:对所有非叶节点,其两个子节点都存在,也即,一个节点要么是叶节点,要么有两个节点。
典型的恢复方法是递归建构节点的左,右子树。一个一个看:
假设二叉树原型如下,为了方便,节点的值刚好等于层次遍历索引
先序:
1,2,4,5,10,11,3,6,7,
中序:
4,2,10,5,11,1,6,3,7,
后序:
4,10,11,5,2,6,7,3,1,
先+中恢复:
对先序,注意第一个节点是根节点,其遍历顺序是中左右,因此,若把第一个节点作为基准,则其左右子树连续存储在该节点之后,不过,目前我们还不知道到底左右子树的分界点在哪,因此需要结合中序来确定其分界点。先序的第一个节点在中序的第5个位置(从0开始算),而我们知道中序的存储顺序是:先中后,因此,对中序列,该节点的左边是其左子树,右边是右子树。因此,根据节点在中序中的位置可以确定其左子树的元素个数,对应到先序即可得到该节点的左,右子树分别在先,中序的位置。根据上述信息就可递归的恢复根节点的左,右子树,进而得到整个树。
后+中:
与上述类似,只不对后序,根节点在末尾,其它的可依此类推。
先+后:
这种情况下恢复的二叉树不一定有唯一解,考虑如下的树:
1
/
2
先序:1,2
后序:2,1
与
1
\
2
先序: 1,2
后序:2,1
可看到不同的树,先,后序遍历是一样的。
其唯一解的条件文章开头已经说过了。不过没有经过严格考究!
这里只针对有唯一解的情况做讨论,还考虑上图的例子,结合实例描述如下:
先序:
1,2,4,5,10,11,3,6,7,
后序:
4,10,11,5,2,6,7,3,1,
对先序,第一个节点与后序最后节点对应,然后再看先序的第二个节点(值为2),我们知道,如果先序存在子树,则必同时存在左右子树,因此可断定,第二个节点正是根节点的左子树节点,可先恢复成:
1
/
2
而它又把后序分成两个部分,一左一右(右边不包括最末的根节点):左(4,10,11,5,2),右(6,7,3),说到这里,再结合上图,一切都明白了:“左”正是根的左子树,“右”正是根的右子树。于是,我们又得到了根节点的左右子树,递归,搞定。
上代码:
-
typedef struct tagTREE
-
{
-
int val;
-
tagTREE* left;
-
tagTREE* right;
-
tagTREE* parent;
-
bool isVisited;
-
}TREE;
-
template<class T>
-
void show(T* vec,int N)
-
{
-
for (int i=0;i<N;++i)
-
{
-
cout<<vec[i]<<",";
-
}
-
cout<<endl;
-
}
-
-
void CreateTree(TREE** node, int a[], int N )
-
{
-
-
cout<<endl;
-
int* arr = new int[a[N-1]];
-
for (int i=0;i<a[N-1];++i)
-
{
-
arr[ i ] = 0;
-
}
-
int k=0;
-
for (int i=0;i<N;++i)
-
{
-
arr[ a[i]-1 ] = i;
-
}
-
-
TREE* arrTree = new TREE[N];
-
-
-
arrTree[0].parent = NULL;
-
-
for (int i=1;i<=N;++i)
-
{
-
arrTree[i-1].val = a[i-1];
-
arrTree[i-1].isVisited = false;
-
int parentIdx = int(a[i-1] / 2);
-
-
if( parentIdx == 0 )
-
arrTree[i-1].parent = NULL;
-
else
-
arrTree[i-1].parent = &arrTree[ arr[ parentIdx-1 ] ];
-
-
int leftIdx = int(a[i-1] * 2 );
-
int rightIdx = leftIdx + 1;
-
-
if ( leftIdx > a[N-1] || arr[leftIdx-1] == 0 )
-
{
-
arrTree[i-1].left = NULL;
-
}
-
else
-
{
-
arrTree[i-1].left = &arrTree[ arr[ leftIdx-1 ] ];
-
}
-
-
if ( rightIdx > a[N-1] || arr[rightIdx-1] == 0 )
-
{
-
arrTree[i-1].right = NULL;
-
}
-
else
-
{
-
arrTree[i-1].right = &arrTree[ arr[ rightIdx-1 ] ];
-
}
-
-
}
-
*node = arrTree;
-
-
-
for (int i=1;i<=N;++i)
-
{
-
cout<<"val="<<arrTree[i-1].val;
-
cout<<" left=";
-
if (arrTree[i-1].left)
-
{
-
cout<<arrTree[i-1].left->val;
-
}
-
cout<<" right=";
-
if (arrTree[i-1].right)
-
{
-
cout<<arrTree[i-1].right->val;
-
}
-
cout<<" parent=";
-
if (arrTree[i-1].parent)
-
{
-
cout<<arrTree[i-1].parent->val;
-
}
-
cout<<endl;
-
}
-
}
-
-
void PreOrder(TREE* pTree,int** out)
-
{
-
if( !pTree )
-
return;
-
*(*out)++ = pTree->val;
-
-
if ( pTree->left )
-
PreOrder(pTree->left,out);
-
if ( pTree->right )
-
PreOrder(pTree->right,out);
-
}
-
void InOrder(TREE* pTree,int** out)
-
{
-
if( !pTree )
-
return;
-
if ( pTree->left )
-
InOrder(pTree->left,out);
-
*(*out)++ = pTree->val;
-
if ( pTree->right )
-
InOrder(pTree->right,out);
-
}
-
void PostOrder(TREE* pTree,int** out)
-
{
-
if( !pTree )
-
return;
-
if ( pTree->left )
-
PostOrder(pTree->left,out);
-
if ( pTree->right )
-
PostOrder(pTree->right,out);
-
*(*out)++ = pTree->val;
-
}
-
-
-
TREE* pre_in(const int* pre,const int* in, int n)
-
{
-
if( n == 0 )
-
return NULL;
-
-
TREE* head = new TREE();
-
-
head->val = pre[0];
-
head->parent = NULL;
-
-
int i=0;
-
for (;i<n;++i)
-
{
-
if( pre[0] == in[i] )
-
break;
-
}
-
-
TREE* left = pre_in( pre+1,in,i );
-
TREE* right = pre_in( pre+i+1,in+i+1,n-i-1 );
-
-
head->left = left;
-
head->right = right;
-
-
return head;
-
}
-
-
TREE* post_in(const int* post,const int* in, int n)
-
{
-
if (n==0)
-
return NULL;
-
-
TREE* head = new TREE();
-
-
head->val = post[n-1];
-
head->parent = NULL;
-
-
int i=0;
-
for (;i<n;++i)
-
{
-
if( post[n-1] == in[i] )
-
break;
-
}
-
-
TREE* left = post_in(post,in,i);
-
TREE* right = post_in(post+i,in+i+1,n-i-1);
-
-
head->left = left;
-
head->right = right;
-
-
return head;
-
}
-
-
-
TREE* pre_post(const int* pre,const int* post, int n)
-
{
-
if (n==0)
-
return NULL;
-
-
TREE* head = new TREE();
-
-
head->val = pre[0];
-
head->parent = NULL;
-
-
-
-
if( n < 2 )
-
return head;
-
-
int i = 0;
-
for (;i<n-1;++i)
-
{
-
if( pre[1] == post[i] )
-
break;
-
}
-
-
TREE* left = pre_post(pre+1,post,i+1);
-
TREE* right = pre_post(pre+i+2,post+i+1,n-i-2);
-
-
head->left = left;
-
head->right = right;
-
-
return head;
-
}
-
-
int _tmain(int argc,char* argv[])
-
{
-
TREE* pTree = new TREE();
-
-
-
-
-
-
-
const int N = 9;
-
int a[N] = {1,2,3,4,5,6,7,10,11};
-
-
CreateTree(&pTree,a,N);
-
-
-
int pre[N];
-
int in[N];
-
int post[N];
-
-
int* pre_ptr = (int*)pre;
-
int* in_ptr = (int*)in;
-
int* post_ptr = (int*)post;
-
-
PreOrder(pTree,&pre_ptr);
-
InOrder(pTree,&in_ptr);
-
PostOrder(pTree,&post_ptr);
-
-
cout<<"pre="<<endl;
-
show(pre,N);
-
cout<<"in="<<endl;
-
show(in,N);
-
cout<<"post="<<endl;
-
show(post,N);
-
-
-
TREE* head = pre_in(pre,in,N);
-
int pre_in_post[N];
-
int* pre_in_post_ptr = (int*)pre_in_post;
-
PostOrder(head,&pre_in_post_ptr);
-
cout<<endl<<"pre_in_post:"<<endl;
-
show(pre_in_post,N);
-
-
-
head = post_in(post,in,N);
-
int post_in_pre[N];
-
int* post_in_pre_ptr = (int*)post_in_pre;
-
PreOrder(head,&post_in_pre_ptr);
-
cout<<endl<<"post_in_pre:"<<endl;
-
show(post_in_pre,N);
-
-
-
-
head = pre_post(pre,post,N);
-
int pre_post_in[N];
-
int* pre_post_in_ptr = (int*)pre_post_in;
-
InOrder(head,&pre_post_in_ptr);
-
cout<<endl<<"pre_post_in:"<<endl;
-
show(pre_post_in,N);
-
return 0;
-
}
阅读(505) | 评论(0) | 转发(0) |