首页 / 算法 / 关于二叉树的问题1-已知前序，中序求后序遍历

关于二叉树的问题1-已知前序，中序求后序遍历

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了关于二叉树的问题1-已知前序，中序求后序遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1405字，纯文字阅读大概需要3分钟。

内容图文

对于一棵二叉树而言，可以由其前序和中序或者中序和后序的遍历序列，确定一棵二叉树。

那么对于已知前序和中序序列，求后序序列也就是先还原二叉树，然后对其进行后序遍历即可。

二叉树结点的结构定义如下:

            struct
             TreeNode
{
    
            char
             value;
    TreeNode *leftChild;
    TreeNode *rightChild;
};

实现代码如下：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

TreeNode* allocateNode()
{

    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->leftChild = nullptr;
    node->rightChild = nullptr;
    return node;
}

char preStr[50], inStr[50];
void postOrder(TreeNode *T)
{
    if (T->leftChild != nullptr)
    {
        postOrder(T->leftChild);
    }
    if (T->rightChild != nullptr)
    {
        postOrder(T->rightChild);
    }
    printf("%c ", T->value);
}

TreeNode* builtTree(int start1, int end1, int start2, int end2)
{
    TreeNode *node = allocateNode();
    node->value = preStr[start1];
    int nodeIndex;
    for (int i = start2; i <= end2; ++i)
    if (preStr[start1] == inStr[i])
    {
        nodeIndex = i;
        break;
    }
    if (nodeIndex != start2)
    {
        node->leftChild = builtTree(start1 + 1, start1 + (nodeIndex - start2), start2, nodeIndex - 1);
    }

    if (nodeIndex != end2)
    {
        node->rightChild = builtTree(start1 + (nodeIndex - start2) + 1, end1, nodeIndex + 1, end2);
    }
    return node;
}

void main(void)
{
    scanf("%s",preStr);
    scanf("%s", inStr);
    int preLen = strlen(preStr);
    int inLen = strlen(inStr);
    TreeNode *root = builtTree(0, preLen - 1, 0, inLen - 1);
    postOrder(root);

}

 

原文：http://www.cnblogs.com/tgycoder/p/4969966.html

内容总结

以上是互联网集市为您收集整理的关于二叉树的问题1-已知前序，中序求后序遍历全部内容，希望文章能够帮你解决关于二叉树的问题1-已知前序，中序求后序遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1045932.html

来源：【匿名】