7-1 根据后序和中序遍历输出先序遍历 (25分)（c++）

爱被打了一巴掌 2022-12-12 15:05 132阅读 0赞

//思路：一个树，知道了后序遍历数组，中序遍历数组，又知道了树的元素个数  
// 后序遍历数组的\[n-1\]即为元素的根，可以在中序遍历数组中找到根的位置  
// 可以求出左子树元素个数，右子树元素个数  
// 那么左边就是这个树的左子树，右边就是右子树  
// 因此，可以知道左子树的中序遍历的起始位置就是当前中序遍历数组的起始位置  
// 也可以知道左子树后序遍历数组的起始位置，就是原后序遍历数组的起始位置  
// 同理，可以得到建立起右子树，  
// 根据返回值，可以建立起这个二叉树  
//n表示当前数的元素个数

const int maxn = 1e3 + 5;
    typedef int ElemType;
    typedef struct BiTNode
    {
        
        ElemType data;
        struct BiTNode *lTree, *rTree;
    }BitNode, *BiTree;
    
    BiTree createTree(int *InorderTree, int *PostOrderTree, int n)
    {
        
        if (n <= 0) return NULL;
        else
        {
        
            BiTree temp_tree = (BitNode*)malloc(sizeof(BitNode));
            temp_tree->data = PostOrderTree[n-1];
            int i;
            for (i = 0; i < n; i++)
            {
        
                if (InorderTree[i] == PostOrderTree[n-1])
                    break;
            }
            temp_tree->lTree = createTree(InorderTree, PostOrderTree, i);
            temp_tree->rTree = createTree(InorderTree + i + 1, PostOrderTree + i, n - i - 1);
            return temp_tree;
        }
    }
    
    void print_preorderTree(BiTree T)
    {
        
        if (!T) return ;
        else
        {
        
            cout << " " << T->data;
            print_preorderTree(T->lTree);
            print_preorderTree(T->rTree);
        }
    }