数据结构——已知先序中序求后序，已知中序后序求先序-白红宇

数据结构——已知先序中序求后序，已知中序后序求先序

阅读量：4963 次

发布时间：2019-06-12

本文共 2086 字，大约阅读时间需要 6 分钟。

　　总结下二叉树的已知两种遍历方式求第三种遍历顺序的方法，已知先序和中序遍历或者后序与中序遍历后二叉树是唯一确定的，下面介绍怎么求出第三种遍历顺序。

　　先序遍历顺序为：根结点——左子结点——右子结点，中序遍历为：左子结点——根结点——右子结点，我们注意到，先序遍历的第一个元素就是二叉树根结点，我们在中序遍历中以该元素分为左右两部分，则左边为左子树，右边为右子树，递归即可还原二叉树，这个过程中可直接输出后序遍历的顺序。同理，可以用后序与中序还原出先序遍历的顺序。

代码及测试数据如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               12 13 #define FRER() freopen("in.txt", "r", stdin);14 15 using namespace std;16 17 //函数状态码定义18 #define TRUE 119 #define FALSE 020 #define OK 121 #define ERROR 022 #define INFEASIBLE -123 #define OVERFLOW -224 25 typedef char TElemType;26 typedef int Status;27 28 typedef struct BiNode {29 TElemType data;30 struct BiNode *lchild, *rchild;31 }BiNode, *BiTree;32 33 BiTree BinaryTreeFormorderings(char *, char *, int);34 BiTree BinaryTreePostorderings(char *, char *, int);35 36 /*37 ABDECFG38 DBEAFCG39 DEBFGCA40 */41 42 int main()43 {44 FRER()45 int n;46 char str[100], ptr[100];47 cin >> n >> str >> ptr;48 BinaryTreePostorderings(str, ptr, n);49 return 0;50 }51 52 BiTree BinaryTreeFormorderings(char *pre, char *in, int len) {53 if(len <= 0)54 return NULL;55 BiNode *node = new BiNode;56 node->data = *pre;57 int idx = 0;58 while(idx < len) {59 if(*(in + idx) == *pre)60 break;61 ++idx;62 }63 node->lchild = BinaryTreeFormorderings(pre + 1, in, idx);64 node->rchild = BinaryTreeFormorderings(pre + idx + 1, in + idx + 1, len - (idx + 1));65 cout << node->data << ' ';66 return node;67 }68 69 BiTree BinaryTreePostorderings(char *in, char *post, int len) {70 if(len == 0)71 return NULL;72 BiNode *node = new BiNode;73 node->data = *(post + len - 1);74 cout << node->data << ' ';75 int idx = 0;76 while(idx < len) {77 if(*(in + idx) == *(post + len - 1))78 break;79 ++idx;80 }81 node->lchild = BinaryTreePostorderings(in, post, idx);82 node->rchild = BinaryTreePostorderings(in + idx + 1, post + idx, len - (idx + 1));83 return node;84 }

转载于:https://www.cnblogs.com/fan-jiaming/p/9822765.html

你可能感兴趣的文章