当前位置:   article > 正文

二叉树的还原恢复_二叉树有重复节点怎么还原

二叉树有重复节点怎么还原

二叉树的三种遍历常用于恢复:先序,中序,后序。


1.对于先+中,后+中这两种组合,对任意二叉树的恢复都有唯一解


2.但对先+后的情况则不是,这种情况下要满足要求:对所有非叶节点,其两个子节点都存在,也即,一个节点要么是叶节点,要么有两个节点。


典型的恢复方法是递归建构节点的左,右子树。


一个一个看:

假设二叉树原型如下,为了方便,节点的值刚好等于层次遍历索引


先序: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. /**利用vector引用的方式,可以避免每次复制导致空间利用过大,利用引用直接在原始空间内进行操作。</span>
  2. * Definition for binary tree
  3. * struct TreeNode {
  4. * int val;
  5. * TreeNode *left;
  6. * TreeNode *right;
  7. * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8. * };
  9. */
  10. class Solution {
  11. public:
  12. TreeNode* getTree(vector<int> &preorder, vector<int> &inorder, int prebeg, int preend, int inbeg, int inend)
  13. {
  14. if(prebeg < preend && inbeg < inend)
  15. {
  16. TreeNode *rev = new TreeNode(preorder[prebeg]);
  17. vector<int>::iterator mid = find(inorder.begin()+inbeg, inorder.begin()+inend, preorder[prebeg]);
  18. int span = mid - (inorder.begin() + inbeg);
  19. rev->left = getTree(preorder, inorder, prebeg+1, prebeg+1+span, inbeg, inbeg+span);
  20. rev->right = getTree(preorder, inorder, prebeg+1+span, preend, inbeg+span+1, inend);
  21. return rev;
  22. }
  23. return NULL;
  24. }
  25. TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
  26. return getTree(preorder, inorder, 0, preorder.size(), 0, inorder.size());
  27. }
  28. };





后+中:

与上述类似,只不对后序,根节点在末尾,其它的可依此类推。

  1. /**利用vector引用的方式,可以避免每次复制导致空间利用过大,利用引用直接在原始空间内进行操作。</span>
  2. * Definition for binary tree
  3. * struct TreeNode {
  4. * int val;
  5. * TreeNode *left;
  6. * TreeNode *right;
  7. * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8. * };
  9. */
  10. class Solution {
  11. public:
  12. TreeNode *getTree(vector<int> &inorder, vector<int> &postorder, int inbeg, int inend, int postbeg, int postend)
  13. {
  14. if (inbeg < inend && postbeg < postend)
  15. {
  16. TreeNode *rev =new TreeNode(postorder[postend-1]);
  17. vector<int>::iterator mid = find(inorder.begin()+inbeg, inorder.begin()+inend, postorder[postend-1]);
  18. int span = mid - (inorder.begin() + inbeg);
  19. rev->left = getTree(inorder, postorder, inbeg, inbeg+span, postbeg, postbeg+span);
  20. rev->right = getTree(inorder, postorder, inbeg+span+1, inend, postbeg+span, postend-1);
  21. return rev;
  22. }
  23. return NULL;
  24. }
  25. TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
  26. return getTree(inorder, postorder, 0, inorder.size(), 0, postorder.size());
  27. }
  28. };


先+后:

这种情况下恢复的二叉树不一定有唯一解,考虑如下的树:

         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),说到这里,再结合上图,一切都明白了:“左”正是根的左子树,“右”正是根的右子树。于是,我们又得到了根节点的左右子树,递归,搞定。


上代码:

[cpp]  view plain  copy
  1. typedef struct tagTREE  
  2. {  
  3.     int val;        //值  
  4.     tagTREE* left;  //左节点  
  5.     tagTREE* right; //右节点  
  6.     tagTREE* parent;//父节点(有时候为了方便,不一定都定义它)  
  7.     bool isVisited; //标记该结点是否已访问,给某些特殊操作准备  
  8. }TREE;  
  9. template<class T>  
  10. void show(T* vec,int N)  
  11. {  
  12.     for (int i=0;i<N;++i)  
  13.     {  
  14.         cout<<vec[i]<<",";  
  15.     }  
  16.     cout<<endl;  
  17. }  
  18. //按数组里指定的层次数值,生成任意二叉树结构,数组里缺失的数值表示对应该层次的该节点没有  
  19. void CreateTree(TREE** node, int a[], int N )  
  20. {  
  21.     //预处理,记录节点在全部节点中的索引,而不是其真正位置号  
  22.     cout<<endl;  
  23.     int* arr = new int[a[N-1]];  
  24.     for (int i=0;i<a[N-1];++i)  
  25.     {  
  26.         arr[ i ] = 0;  
  27.     }  
  28.     int k=0;  
  29.     for (int i=0;i<N;++i)  
  30.     {  
  31.         arr[ a[i]-1 ] = i;  
  32.     }  
  33.   
  34.     TREE* arrTree = new TREE[N];  
  35.   
  36.     //root  
  37.     arrTree[0].parent = NULL;  
  38.   
  39.     for (int i=1;i<=N;++i)  
  40.     {  
  41.         arrTree[i-1].val = a[i-1];    
  42.         arrTree[i-1].isVisited = false;  
  43.         int parentIdx = int(a[i-1] / 2);  
  44.   
  45.         if( parentIdx == 0 )  
  46.             arrTree[i-1].parent = NULL;  
  47.         else  
  48.             arrTree[i-1].parent = &arrTree[ arr[ parentIdx-1 ] ];  
  49.   
  50.         int leftIdx = int(a[i-1] * 2 );  
  51.         int rightIdx = leftIdx + 1;  
  52.   
  53.         if (  leftIdx > a[N-1] || arr[leftIdx-1] == 0 )  
  54.         {  
  55.             arrTree[i-1].left = NULL;  
  56.         }  
  57.         else  
  58.         {  
  59.             arrTree[i-1].left = &arrTree[ arr[ leftIdx-1 ] ];  
  60.         }  
  61.   
  62.         if ( rightIdx > a[N-1] || arr[rightIdx-1] == 0 )  
  63.         {  
  64.             arrTree[i-1].right = NULL;  
  65.         }  
  66.         else  
  67.         {  
  68.             arrTree[i-1].right = &arrTree[ arr[ rightIdx-1 ] ];  
  69.         }  
  70.   
  71.     }  
  72.     *node = arrTree;  
  73.   
  74.     //test  
  75.     for (int i=1;i<=N;++i)  
  76.     {  
  77.         cout<<"val="<<arrTree[i-1].val;  
  78.         cout<<" left=";  
  79.         if (arrTree[i-1].left)  
  80.         {  
  81.             cout<<arrTree[i-1].left->val;  
  82.         }  
  83.         cout<<" right=";  
  84.         if (arrTree[i-1].right)  
  85.         {  
  86.             cout<<arrTree[i-1].right->val;  
  87.         }  
  88.         cout<<" parent=";  
  89.         if (arrTree[i-1].parent)  
  90.         {  
  91.             cout<<arrTree[i-1].parent->val;  
  92.         }  
  93.         cout<<endl;  
  94.     }  
  95. }  
  96. //先序遍历,第一个参数是二叉树的头结点,第二个参数是用于记录遍历序列的数组,下同  
  97. void PreOrder(TREE* pTree,int** out)  
  98. {  
  99.     if( !pTree )  
  100.         return;  
  101.     *(*out)++ = pTree->val;  
  102.   
  103.     if ( pTree->left )  
  104.         PreOrder(pTree->left,out);  
  105.     if ( pTree->right )  
  106.         PreOrder(pTree->right,out);  
  107. }  
  108. void InOrder(TREE* pTree,int** out)  
  109. {  
  110.     if( !pTree )  
  111.         return;  
  112.     if ( pTree->left )  
  113.         InOrder(pTree->left,out);  
  114.     *(*out)++ = pTree->val;  
  115.     if ( pTree->right )  
  116.         InOrder(pTree->right,out);  
  117. }  
  118. void PostOrder(TREE* pTree,int** out)  
  119. {  
  120.     if( !pTree )  
  121.         return;  
  122.     if ( pTree->left )  
  123.         PostOrder(pTree->left,out);  
  124.     if ( pTree->right )  
  125.         PostOrder(pTree->right,out);  
  126.     *(*out)++ = pTree->val;  
  127. }  
  128.   
  129. //先+中恢复二叉树  
  130. TREE* pre_in(const int* pre,const int* in, int n)  
  131. {  
  132.     if( n == 0 )  
  133.         return NULL;  
  134.   
  135.     TREE* head = new TREE();      
  136.     //先序的第一个节点是根节点  
  137.     head->val = pre[0];  
  138.     head->parent = NULL;  
  139.     //由根节点在中序的位置,基左边是根的左子树,右边是右子树  
  140.     int i=0;  
  141.     for (;i<n;++i)  
  142.     {  
  143.         if( pre[0] == in[i] )  
  144.             break;  
  145.     }  
  146.     //递归的构建节点的左右子树,这里需要确定左/右子树对应的先序/中序段  
  147.     TREE* left  = pre_in( pre+1,in,i );  
  148.     TREE* right = pre_in( pre+i+1,in+i+1,n-i-1 );  
  149.   
  150.     head->left = left;  
  151.     head->right = right;  
  152.     //返回头节点  
  153.     return head;  
  154. }  
  155. //后+中恢复二叉树  
  156. TREE* post_in(const int* post,const int* in, int n)  
  157. {  
  158.     if (n==0)  
  159.         return NULL;  
  160.   
  161.     TREE* head = new TREE();  
  162.     //后序与先序类似,最后一节点是根节点  
  163.     head->val = post[n-1];  
  164.     head->parent = NULL;  
  165.     //确定根在中序中的位置  
  166.     int i=0;  
  167.     for (;i<n;++i)  
  168.     {  
  169.         if( post[n-1] == in[i] )  
  170.             break;  
  171.     }  
  172.     //递归的构建左右子树,这里需要确定左/右子树对应的后序/中序段  
  173.     TREE* left  = post_in(post,in,i);  
  174.     TREE* right = post_in(post+i,in+i+1,n-i-1);  
  175.   
  176.     head->left = left;  
  177.     head->right = right;  
  178.   
  179.     return head;  
  180. }  
  181.   
  182. //先+后恢复二叉树  
  183. TREE* pre_post(const int* pre,const int* post, int n)  
  184. {  
  185.     if (n==0)  
  186.         return NULL;  
  187.   
  188.     TREE* head = new TREE();  
  189.   
  190.     head->val = pre[0];  
  191.     head->parent = NULL;  
  192.       
  193.     //对有唯一解的二叉树,若将先序的第一个节点当做父节点,则第二个节点pre[1]必是左子树节点  
  194.     //pre[1]在后序中的位置确定了pre[0](post[n-1])的左右子树范围  
  195.     if( n < 2 )  
  196.         return head;  
  197.   
  198.     int i = 0;    
  199.     for (;i<n-1;++i)  
  200.     {  
  201.         if( pre[1] == post[i] )  
  202.             break;  
  203.     }  
  204.   
  205.     TREE* left  = pre_post(pre+1,post,i+1);  
  206.     TREE* right = pre_post(pre+i+2,post+i+1,n-i-2);  
  207.   
  208.     head->left = left;  
  209.     head->right = right;  
  210.   
  211.     return head;  
  212. }  
  213.   
  214. int _tmain(int argc,char* argv[])  
  215. {  
  216.     TREE* pTree = new TREE();  
  217.   
  218.     //任意二叉树,不能用于测试pre_post函数  
  219.     //const int N = 7;  
  220.     //int a[N] = {1,2,3,4,5,6,11};  
  221.       
  222.     //先+后有唯一解的二叉树,用于测试pre_post函数  
  223.     const int N = 9;  
  224.     int a[N] = {1,2,3,4,5,6,7,10,11};  
  225.   
  226.     CreateTree(&pTree,a,N);  
  227.   
  228.   
  229.     int pre[N];  
  230.     int in[N];  
  231.     int post[N];  
  232.       
  233.     int* pre_ptr  = (int*)pre;  
  234.     int* in_ptr   = (int*)in;  
  235.     int* post_ptr = (int*)post;  
  236.   
  237.     PreOrder(pTree,&pre_ptr);  
  238.     InOrder(pTree,&in_ptr);  
  239.     PostOrder(pTree,&post_ptr);  
  240.   
  241.     cout<<"pre="<<endl;  
  242.     show(pre,N);  
  243.     cout<<"in="<<endl;  
  244.     show(in,N);  
  245.     cout<<"post="<<endl;  
  246.     show(post,N);  
  247.   
  248.     //------------- pre_in_post  
  249.     TREE* head = pre_in(pre,in,N);  
  250.     int pre_in_post[N];  
  251.     int* pre_in_post_ptr = (int*)pre_in_post;  
  252.     PostOrder(head,&pre_in_post_ptr);  
  253.     cout<<endl<<"pre_in_post:"<<endl;  
  254.     show(pre_in_post,N);  
  255.       
  256.     //------------- post_in_pre  
  257.     head = post_in(post,in,N);  
  258.     int post_in_pre[N];  
  259.     int* post_in_pre_ptr = (int*)post_in_pre;  
  260.     PreOrder(head,&post_in_pre_ptr);  
  261.     cout<<endl<<"post_in_pre:"<<endl;  
  262.     show(post_in_pre,N);  
  263.   
  264.     //------------- pre_post_in  
  265.     //注意:这种情况况不是任意二叉树都有唯一解,只对这种二叉树才有唯一解:每个非叶节点都有个孩子  
  266.     head = pre_post(pre,post,N);  
  267.     int pre_post_in[N];  
  268.     int* pre_post_in_ptr = (int*)pre_post_in;  
  269.     InOrder(head,&pre_post_in_ptr);  
  270.     cout<<endl<<"pre_post_in:"<<endl;  
  271.     show(pre_post_in,N);  
  272.     return 0;  
  273. }  
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/663498
推荐阅读
相关标签
  

闽ICP备14008679号