l3 通过前序遍历和中序遍历重构二叉树

关键点就是每个根结点的左子树和右子树都连在一块,所以只要找到根结点就能切割

#include <iostream>
#include <stdexcept>
#include <queue>
struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
};

BinaryTreeNode * constructorCore (int * startPreorder, int * endPreorder, int * startInorder, int * endInorder);

BinaryTreeNode * constructor (int * preorder, int * inorder, int length) {
    if (preorder == NULL || inorder == NULL || length <= 0) {
        return NULL;
    }
    return constructorCore(preorder, preorder + length - 1, inorder, inorder + length - 1);
}

BinaryTreeNode * constructorCore (int * startPreorder, int * endPreorder, int * startInorder, int * endInorder) {
    
    int rootValue = startPreorder[0];
    
    BinaryTreeNode * rootNode = new BinaryTreeNode();
    rootNode->m_nValue = rootValue;
    rootNode->leftChild = NULL;
    rootNode->rightChild = NULL;
    
    if (startPreorder == endPreorder) {
        if (startInorder == endInorder && *startInorder == *startPreorder) {
            return rootNode;
        } else {
            throw std::invalid_argument("invalid input");
        }
    }
    
    int *rootInorder = startInorder;
    while (rootInorder < endInorder && *rootInorder != rootValue ) {
        rootInorder++;
    }
    
    if (rootInorder == endInorder && *rootInorder != rootValue) {
        throw std::invalid_argument("invalid input");
    }
    
    long leftLength = rootInorder - startInorder;
    int * leftPreOrderEnd = startPreorder + leftLength;
    
    if (leftLength > 0) {
        rootNode->leftChild = constructorCore(startPreorder + 1, leftPreOrderEnd, startInorder, rootInorder - 1);
    }
    
    if (endInorder - startInorder > leftLength ) {
        rootNode->rightChild = constructorCore( leftPreOrderEnd + 1, endPreorder, rootInorder + 1, endInorder);
    }
    
    return rootNode;
}

//只是测试用例,用来输出重建后的结果
struct TestNode {
    int leafHeight;
    BinaryTreeNode * node;
};

//测试用例可以不看
void traverse (BinaryTreeNode * list) {
    if (list == NULL) {
        return;
    }
    
    TestNode * rootNode = new TestNode();
    rootNode->leafHeight = 0;
    rootNode->node = list;
    
    int currentLeafHeight = 0;
    std::queue<TestNode *> nodeQueue ;
    
    nodeQueue.push(rootNode);
    
    while (!nodeQueue.empty()) {
        if (nodeQueue.front()->leafHeight > currentLeafHeight) {
            printf("\n");
            currentLeafHeight = nodeQueue.front()->leafHeight;
        }
        printf("%d      ",nodeQueue.front()->node->m_nValue);
        if (nodeQueue.front()->node->leftChild != NULL) {
            TestNode * tNode = new TestNode();
            tNode->leafHeight = nodeQueue.front()->leafHeight + 1;
            tNode->node = nodeQueue.front()->node->leftChild;
            nodeQueue.push(tNode);
        }
        if (nodeQueue.front()->node->rightChild != NULL) {
            TestNode * tNode = new TestNode();
            tNode->leafHeight = nodeQueue.front()->leafHeight + 1;
            tNode->node = nodeQueue.front()->node->rightChild;
            nodeQueue.push(tNode);
        }
        
        TestNode * needDelete = nodeQueue.front();
        nodeQueue.pop();
        delete needDelete->node;
        delete needDelete;
    }
}

int main() {
    int  preorder[] = {1,2,4,7,3,5,6,8};
    int  inOrder[] = {4,7,2,1,5,3,8,6};
    
    BinaryTreeNode * list = constructor(preorder, inOrder, 8);
    traverse(list);
    
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 数据结构和算法--二叉树的实现 几种二叉树 1、二叉树 和普通的树相比,二叉树有如下特点: 每个结点最多只有两棵子...
    sunhaiyu阅读 6,511评论 0 14
  • 数据结构与算法--从平衡二叉树(AVL)到红黑树 上节学习了二叉查找树。算法的性能取决于树的形状,而树的形状取决于...
    sunhaiyu阅读 7,676评论 4 32
  • 树和二叉树 1、树的定义 树(Tree)是由一个 或 多个结点 组成的有限集合T,且满足: ①有且仅有一个称为根的...
    利伊奥克儿阅读 1,394评论 0 1
  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,290评论 0 25
  • 1、其实政策或许是有帮助的,只不过一定要考量周全和清楚 2、如果现在不思索经济,老是想着经济有问题,那么将来一定也...
    智囊团阅读 137评论 0 0