已知一颗二叉树的中序遍历和后序遍历构建二叉树

￡神魔★判官ぃ 2022-12-16 09:25 150阅读 0赞

### 文章目录 ###

*  一、算法思路
 *  二、函数实现（c语言）
 *   *  1.树节点定义
     *  2.函数声明
     *  3.函数实现

--------------------

# 一、算法思路 #

前提条件：所构建二叉树中的每一项均不相等，给出所有节点的个数

1、后序遍历中的最后一项为当前子树的根节点

2、通过后序遍历得到根节点的值后找到根节点的值在中序遍历中的位置，根节点的两边分别对应其左子树和右子树的中序遍历

3、通过中序遍历确立当前根节点左右子树的个数，即可在后序遍历数组中分出左右子树的后序遍历（因为后序遍历顺序为左子树->右子树->根节点）

4、递归构建二叉树：  
（1）若传入的遍历数组为空（size == 0），返回null  
（2）根据当前这棵（子）树建立当前根节点，并分出左子树与右子树的中序、后序遍历  
（3）当前根节点的左子树与右子树通过获得的左右子树的中序、后序遍历递归构建

# 二、函数实现（c语言） #

## 1.树节点定义 ##

typedef struct TreeNode *Tree;
    struct TreeNode {
        
        int Element;
        Tree  Left;
        Tree  Right;
    };

## 2.函数声明 ##

Tree NewNode(void);
    //创建一个节点
    
    Tree Construct(int *post, int *in, int size);
    //构建二叉树，post和in分别为后序遍历和中序遍历数组
    //size为数组元素即二叉树所有节点总个数

## 3.函数实现 ##

Tree NewNode(void){
        
        Tree node;
        node = (Tree)malloc(sizeof(struct TreeNode));
        node->Left = node->Right =NULL;
        return node;
    }

Tree Construct(int *post, int *in, int size){
        
        if(size == 0) return NULL;
        int root_post = size-1;//后序遍历中当前子树根节点位置
        int root_in = 0;//中序遍历中当前子树根节点位置
        
        for(int i = 0;i < size;i++){
        
            if(in[i] == post[root_post]){
        
                root_in = i;
                break;
            }
        }//两种遍历方式种根节点位置均已确认
        
        Tree node;
        node = NewNode();
        node->Element = post[root_post];
        //构建当前子树根节点
        
        int size_left = root_in ;
        int size_right = size - root_in - 1;
        node->Left = Construct(post, in, size_left)
        ;//递归构建当前根节点的左子树
        node->Right = Construct(post+size_left, in+size_left+1, size_right);
        //递归构建当前根节点的右子树
        return node;
        //将当前已构建好的子树返回
    }