精华内容
下载资源
问答
  • C++ 二叉树 前序遍历 中序遍历 后序遍历 通过递归代码推出非递归实现 通过遍历规则推出非递归实现
    10
    6
    4
    8
    14
    12
    16

    一般二叉树有3中遍历方式

    1. 前序遍历:先访问根节点,再访问左子节点,最后访问右子节点。对于上图二叉树的前序遍历顺序是:10、6、4、8、14、12、16
    2. 中序遍历:先访问左子节点,再访问根节点,最后访问右子节点。对于上图二叉树的中序遍历顺序是:4、6、8、10、12、14、16
    3. 后序遍历:先访问左子节点,再访问右子节点,最后访问根节点。对于上图二叉树的后序遍历顺序是:4、8、6、12、16、14、10

    定义与辅助代码

    struct BinaryTreeNode{
        int value;
        BinaryTreeNode *pLeft;
        BinaryTreeNode *pRight;
    };
    
    namespace SON_NODE{
        typedef int dir_type;
        constexpr dir_type LEFT = 1;
        constexpr dir_type RIGHT = 2;
    }
    
    BinaryTreeNode* AddNode(BinaryTreeNode *rootNode, int value, SON_NODE::dir_type dir){
        if (rootNode == nullptr){
            return nullptr;
        }
        BinaryTreeNode *pNew = new BinaryTreeNode();
        pNew->value = value;
        pNew->pLeft = nullptr;
        pNew->pRight = nullptr;
        if (dir == SON_NODE::LEFT){
            rootNode->pLeft = pNew;
        }
        else{
            rootNode->pRight = pNew;
        }
        return pNew;
    }
    // 生成上图中的树结构
    BinaryTreeNode *GetBinaryTree(){
        BinaryTreeNode *rootNode = new BinaryTreeNode();
        rootNode->value = 10;
        rootNode->pLeft = nullptr;
        rootNode->pRight = nullptr;
    
        BinaryTreeNode *pNew = AddNode(rootNode, 6, SON_NODE::LEFT);
        AddNode(pNew, 4, SON_NODE::LEFT);
        AddNode(pNew, 8, SON_NODE::RIGHT);
    
        pNew = AddNode(rootNode, 14, SON_NODE::RIGHT);
        AddNode(pNew, 12, SON_NODE::LEFT);
        AddNode(pNew, 16, SON_NODE::RIGHT);
        return rootNode;
    }
    BinaryTreeNode *GetBinaryTree1(){
        return nullptr;
    }
    BinaryTreeNode *GetBinaryTree2(){
        BinaryTreeNode *rootNode = new BinaryTreeNode();
        rootNode->value = 10;
        rootNode->pLeft = nullptr;
        rootNode->pRight = nullptr;
    
        BinaryTreeNode *pNew = AddNode(rootNode, 6, SON_NODE::LEFT);
        AddNode(pNew, 8, SON_NODE::RIGHT);
    
        return rootNode;
    }
    BinaryTreeNode *GetBinaryTree3(){
        BinaryTreeNode *rootNode = new BinaryTreeNode();
        rootNode->value = 10;
        rootNode->pLeft = nullptr;
        rootNode->pRight = nullptr;
    
        BinaryTreeNode *pNew = AddNode(rootNode, 14, SON_NODE::RIGHT);
        AddNode(pNew, 12, SON_NODE::RIGHT);
    
        return rootNode;
    }
    

    前序遍历

    // 前序遍历-递归
    void PreOrderByRecursive(BinaryTreeNode *rootNode){
        if (rootNode == nullptr){
            return;
        }
        cout << rootNode->value << " ";
        PreOrderByRecursive(rootNode->pLeft);
        PreOrderByRecursive(rootNode->pRight);
    }
    

    前序遍历的递归代码非常简洁,不必多说
    但我们可以用递归的实现来推导非递归的实现

    10
    6
    4
    8
    14
    12
    16

    以上图为例,递归的思想既是先访问根节点10,然后将10的左子节点当作根节点递归调用
    那么编译器具体是如何实现这种功能的呢?答案是函数栈,我们可以模拟一下大概的过程
    当第一次调用函数时,便会开辟一个栈内存,这个栈中只有3个步骤
    (方括号表示一个栈内存,删除线表示已经执行)

    (栈顶)
    A [访问node、左子节点递归调用、右子节点递归调用]

    当函数执行到左子节点递归调用时,会有一个问题,递归调用的话肯定要执行一个新的函数,但是我(A)执行我自己(A’),我(A)却还没有执行完,如何才能保证执行完我自己(A’)之后,我(A)再继续执行呢?答案是利用函数栈
    在递归调用时,函数栈会开辟一个新的栈内存

    (栈顶)
    A’ [访问node、左子节点递归调用、右子节点递归调用]
    A [访问node、左子节点递归调用、右子节点递归调用]

    假如这时候(A’)又要递归,那么

    (栈顶)
    A’’ [访问node、左子节点递归调用、右子节点递归调用]
    A’ [访问node、左子节点递归调用、右子节点递归调用]
    A [访问node、左子节点递归调用、右子节点递归调用]

    而当(A’’)执行完后,又到了(A’)的右子节点递归调用,那么

    (栈顶)
    A’’ [访问node、左子节点递归调用、右子节点递归调用]
    A’ [访问node、左子节点递归调用、右子节点递归调用]
    A [访问node、左子节点递归调用、右子节点递归调用]

    之后,直到(A’’)执行完,才发现(A’)也执行完,之后才会轮到(A)的右子节点递归调用
    假如我们模拟所有的操作都在一个栈中执行过程,那么最开始的时候是

    (栈顶)
    A [访问node]
    A [左子节点递归调用]
    A [右子节点递归调用]

    当执行完访问node之后,该node就会出栈

    (栈顶)
    A [左子节点递归调用]
    A [右子节点递归调用]

    接下来执行左子节点递归调用

    (栈顶)
    A’ [访问node]
    A’ [左子节点递归调用]
    A’ [右子节点递归调用]
    A [右子节点递归调用]

    从上面的过程中,我们可以发现一个事情,对于每一个节点,都可以用3个栈内存来进行前序遍历,那就是右子节点在栈底,左子节点在上一层栈,本节点在栈顶,接着取出栈顶元素(访问本节点),然后继续取出栈顶(左子节点)构建3个栈…如此循环直到栈为空表示所有节点都访问过

    // 前序遍历-循环
    /* 思想:
    先将根节点放进栈
    1. 取出栈顶节点node
    2. 若node有右子节点,放进栈
    3. 若node有左子节点,放进栈
    重复1~3直到栈为空
    */
    void PreOrderByLoop(BinaryTreeNode *rootNode){
        if (rootNode == nullptr){
            return;
        }
        vector<BinaryTreeNode *> treeNodeVec{rootNode};
        while (!treeNodeVec.empty()){
            auto pNode = treeNodeVec.back();
            treeNodeVec.pop_back();
            cout << pNode->value << " ";
            // 必须右子节点先进栈
            if (pNode->pRight != nullptr){
                treeNodeVec.push_back(pNode->pRight);
            }
            if (pNode->pLeft != nullptr){
                treeNodeVec.push_back(pNode->pLeft);
            }
        }
        cout << endl;
    }
    
    void TestPreOrder(){
        PreOrderByLoop(GetBinaryTree());
        PreOrderByLoop(GetBinaryTree1());
        PreOrderByLoop(GetBinaryTree2());
        PreOrderByLoop(GetBinaryTree3());
    }
    

    中序遍历

    // 中序遍历-递归
    void InOrderByRecursive(BinaryTreeNode *rootNode){
        if (rootNode == nullptr){
            return;
        }
        InOrderByRecursive(rootNode->pLeft);
        cout << rootNode->value << " ";
        InOrderByRecursive(rootNode->pRight);
    }
    

    根据递归代码推非递归实现,递归过程可以发现,对于每一个节点,右子节点会在栈底,该节点在中间,左子节点在栈顶构建3个栈空间,难点在于,对于栈顶节点,如何确保其左子节点已经被访问了,可以使用可访问标记来解决

    /* 中序遍历-循环1
    思想:
    使用pair让每个节点都自带标记
    1. 将根节点进栈
    2. 取出栈顶元素
        a. 若左子节点没有被访问过,则依次将右子节点,本节点,左子节点入栈,并标记左子节点已访问
        b. 若左子节点已经被访问,输出本节点
    3. 重复2至栈空
     */
    void InOrderByLoop(BinaryTreeNode *rootNode){
        if (rootNode == nullptr){
            return;
        }
        vector< pair<BinaryTreeNode*, bool> > treeNodeVec;
        treeNodeVec.emplace_back(make_pair(rootNode, false));
        while (!treeNodeVec.empty()){
            auto pNode = treeNodeVec.back().first;
            auto &visited = treeNodeVec.back().second;
            treeNodeVec.pop_back();
    
            if (visited){
                cout << pNode->value << " ";
                treeNodeVec.pop_back();
                continue;
            }
            if (pNode->pRight != nullptr){
                treeNodeVec.emplace_back(make_pair(pNode->pRight, false));
            }
            treeNodeVec.emplace_back(make_pair(pNode, true));
            if (pNode->pLeft != nullptr){
                treeNodeVec.emplace_back(make_pair(pNode->pLeft, false));
            }
        }
        cout << endl;
    }
    
    void TestInOrder(){
        InOrderByLoop(GetBinaryTree());
        InOrderByLoop(GetBinaryTree1());
        InOrderByLoop(GetBinaryTree2());
        InOrderByLoop(GetBinaryTree3());
    }
    

    若不根据递归而根据中序遍历的规则(即先处理左子节点,只有左子节点输出后才处理右子节点)来实现非递归

    10
    6
    4
    8
    14
    12
    16

    我们根据上图来模拟一下后序遍历
    首先从10开始遍历,根据规则,一定最先找到最左下角的叶子节点4,之后访问6,再到8,以此类推,访问结果为 4、6、8、10、12、14、16
    遍历到一个节点时,先不输出,而是先将往左子节点遍历,待输出左子节点后,才输出本节点,这种先进后出的现象可以使用栈来解决
    而对于一个栈顶节点,首先会将所有左子节点入栈(先访问左子节点),那么此时栈顶节点有3种情况

    1. 没有左子节点
    2. 左子节点已经访问
    3. 左子节点没有访问

    对第3中情况,继续入栈…
    而前两种情况,直接出栈输出,输出该节点之后有2种情况

    1. 有右子节点
    2. 没有右子节点

    第1种情况,显而易见需要处理右子节点(入栈),然后继续处理栈顶节点
    第2种情况,继续处理栈顶节点…

    我们用上图来模拟一下,首先从根节点开始往左子节点遍历依次入栈,直到停止时栈情况为

    (栈顶)
    [4]
    [6]
    [10]

    此时由于节点4没有左子节点,直接输出,然后也没有右子节点,所以栈变成

    (栈顶)
    [6]
    [10]

    请注意,这个时候我们并不用判断节点6的左子节点是否已经处理,因为一开始我们就把6的左子节点放到了栈的更上层。也就是说,当我们一开始便把所有左子节点依次入栈之后,对于所有栈顶元素,其要么没有左子节点要么左子节点已经被访问,此时我们只需要判断有没有右子节点并访问即可…
    至此,我们便可以开始写代码

    // 中序遍历-循环2
    /* 思想:
    1. 将指针指向根节点
    2. 先遍历所有左子节点并入栈
    3. 当指针没有左子节点时,出栈这个节点(相当于访问该节点)
    4. 接着讲指针指向该节点的右子节点
    5. 重复2~4操作直至栈空
    */
    void InOrderByLoop1(BinaryTreeNode *rootNode){
        if (rootNode == nullptr){
            return;
        }
        vector<BinaryTreeNode *> treeNodeVec;
        auto *pNode = rootNode;
        while (!treeNodeVec.empty() || pNode != nullptr){
            while (pNode != nullptr){
                treeNodeVec.push_back(pNode);
                pNode = pNode->pLeft;
            }
            pNode = treeNodeVec.back();
            treeNodeVec.pop_back();
            cout << pNode->value << " ";
            pNode = pNode->pRight;
        }
        cout << endl;
    }
    // 不同实现
    void InOrderByLoop2(BinaryTreeNode *rootNode){
        if (rootNode == nullptr){
            return;
        }
        vector<BinaryTreeNode *> treeNodeVec({rootNode});
        bool isNewNode = true;
        while (!treeNodeVec.empty()){
            auto pNode = treeNodeVec.back();
            // isNewNode表示当前栈顶是否是新加入的节点
            while (isNewNode && pNode->pLeft != nullptr){
                treeNodeVec.push_back(pNode->pLeft);
                pNode = pNode->pLeft;
            }
            treeNodeVec.pop_back();
            cout << pNode->value << " ";
            isNewNode = false;
            if (pNode->pRight != nullptr){
                treeNodeVec.push_back(pNode->pRight);
                isNewNode = true;
            }
        }
        cout << endl;
    }
    

    后序遍历

    // 后序遍历-递归
    void PostOrderByRecursive(BinaryTreeNode *rootNode){
        if (rootNode == nullptr){
            return;
        }
        PostOrderByRecursive(rootNode->pLeft);
        PostOrderByRecursive(rootNode->pRight);
        cout << rootNode->value << " ";
    }
    

    后序遍历的非递归方法中,难点在于,对于每一个节点,在访问前,如何确保这个节点的左右子节点都被访问过
    通过递归调用栈可以得知,对于每一个节点,先将自己入栈,再将右子节点入栈,最后是左子节点入栈。那么只要本节点的左右节点入过栈,下一次本节点在栈顶时,就表示左右子节点已经访问过,此时就可访问本节点了
    我们可以使用几种方式来标记本节点的左右节点入过栈

    // 后序遍历-循环1
    /* 思想:
    在本节点入栈后,记录一个可访问标记,再将左右子节点入栈
    这样每次发现栈顶的可访问标记为true时,就表示空标记下面的节点
    的左右节点已经访问过,此时直接访问本节点
    */
    void PostOrderByLoop(BinaryTreeNode *rootNode){
        if (rootNode == nullptr){
            return;
        }
        vector<BinaryTreeNode *> treeNodeVec({rootNode});
        while (!treeNodeVec.empty()){
            auto pNode = treeNodeVec.back();
            if (pNode == nullptr){
                treeNodeVec.pop_back();
                cout << treeNodeVec.back()->value << " ";
                treeNodeVec.pop_back();
                continue;
            }
            // 添加可访问标记
            treeNodeVec.push_back(nullptr);
            if (pNode->pRight != nullptr){
                treeNodeVec.push_back(pNode->pRight);
            }
            if (pNode->pLeft != nullptr){
                treeNodeVec.push_back(pNode->pLeft);
            }
        }
        cout << endl;
    }
    // 与上述思想一致
    void PostOrderByLoop1(BinaryTreeNode *rootNode){
        if (rootNode == nullptr){
            return;
        }
        vector< pair<BinaryTreeNode*, bool> > treeNodeVec;
        treeNodeVec.emplace_back(make_pair(rootNode, false));
        while (!treeNodeVec.empty()){
            auto pNode = treeNodeVec.back().first;
            auto &visited = treeNodeVec.back().second;
    
            if (visited){
                cout << pNode->value << " ";
                treeNodeVec.pop_back();
                continue;
            }
            visited = true;
            if (pNode->pRight != nullptr){
                treeNodeVec.emplace_back(make_pair(pNode->pRight, false));
            }
            if (pNode->pLeft != nullptr){
                treeNodeVec.emplace_back(make_pair(pNode->pLeft, false));
            }
        }
        cout << endl;
    }
    
    void TestOrder(){
        PostOrderByLoop(GetBinaryTree());
        PostOrderByLoop(GetBinaryTree1());
        PostOrderByLoop(GetBinaryTree2());
        PostOrderByLoop(GetBinaryTree3());
    }
    

    代码中对于每一个节点,我们都额外创建了一个bool或者空指针来判断该节点是否左右子节点已访问,那么有没有不用为每个节点都创建标记的办法呢?
    上述实现都是基于递归函数调用栈的想法来改进的,接下来我们直接通过后序遍历的规则(先处理左子节点,左子节点输出后,再处理右子节点)来实现一下

    10
    6
    4
    8
    14
    12
    16

    我们根据上图来模拟一下后序遍历
    首先从10开始遍历,根据规则,一定最先找到最左下角的叶子节点4,之后回到6,发现6还有右子节点,那么会找到8,这时候6的左右子节点都被访问了,那么访问6,以此类推,访问结果为 4、8、6、12、16、14、10…
    让我们找一下其中的规律,首先访问4之前,实际上已经经过6了,而输出4之后还要回到6再去访问8,接着才能访问6,对于这种先经过却后访问的方式,可以很容易联想到用栈来解决
    我们首先创建一个栈,对于一个节点,我们先将所有左子节点依次入栈(先访问左子节点)。这时候我们可以确立一种规则,对于栈顶元素,我们可以保证该节点没有左子节点or左子节点已经被访问。接下来我们只需要判断该节点的右子节点是否被访问就能确定该节点能否访问了
    此时栈顶的节点有3种情况:

    1. 没有右子节点
    2. 右子节点已经访问
    3. 右子节点还没访问

    我们用上图来模拟一下,假设已经访问4(节点4已经出栈),栈顶就是节点6,这时候我们要怎么确保节点8已经被访问过了呢?细心的同学一定会发现,假如节点6可以被访问,那么上一个出栈的一定是节点8(这不是废话嘛),将这个顺序转换成二叉树的结构来说就是,一个节点可以被访问,那么上一个被访问的一定是该节点的右子节点!!!
    至此,我们便可以开始写代码

    /* 后序遍历-循环2
    思想:
    1. 根节点入栈
    2. 循环将栈顶元素的左子节点入栈
    3. 取栈顶元素node
        a. 若node没有右子节点,则输出node,出栈,重新进入步骤3
        b. 若node有右子节点,但右子节点为上一个输出的节点,则输出node,出栈,重新进入步骤3
        c. 若node有右子节点,且不是上一个输出的节点,右子节点进栈,返回步骤2
    4. 循环2~4至栈空
     */
    void PostOrderByLoop2(BinaryTreeNode *rootNode){
        if (rootNode == nullptr){
            return;
        }
        vector<BinaryTreeNode *> treeNodeVec({rootNode});
        BinaryTreeNode *lastOutputNode = nullptr;
        BinaryTreeNode *pNode = nullptr;
        while (!treeNodeVec.empty()){
            pNode = treeNodeVec.back();
            while (pNode->pLeft != nullptr){
                treeNodeVec.emplace_back(pNode->pLeft);
                pNode = pNode->pLeft;
            }
            // 所有节点已经入过栈了,此时只需要输出所有节点即可
            while (!treeNodeVec.empty()){
                pNode = treeNodeVec.back();
                if (pNode->pRight == lastOutputNode || pNode->pRight == nullptr){
                    cout << pNode->value << " ";
                    treeNodeVec.pop_back();
                    lastOutputNode = pNode;
                }
                else{
                    treeNodeVec.emplace_back(pNode->pRight);
                    break;
                }
            }
        }
        cout << endl;
    }
    

    至此,豁然开朗
    而后在网上搜了一下,貌似对于三种非递归用统一方式实现很受欢迎,就贴一下代码吧

    void OrderByLoop(BinaryTreeNode *rootNode){
        if (rootNode == nullptr){
            return;
        }
        vector<pair<BinaryTreeNode*, bool>> treeNodeVec;
        treeNodeVec.emplace_back(make_pair(rootNode, false));
        while (!treeNodeVec.empty()){
            auto pNode = treeNodeVec.back().first;
            auto &visited = treeNodeVec.back().second;
            treeNodeVec.pop_back();
    
            if (visited){
                cout << pNode->value << " ";
                treeNodeVec.pop_back();
                continue;
            }
            // 对于不同遍历方式,只需要改变一下三种进栈顺序即可,需要先访问的后进栈
            // 右子节点
            if (pNode->pRight != nullptr){
                treeNodeVec.emplace_back(make_pair(pNode->pRight, false));
            }
            // 本节点
            treeNodeVec.emplace_back(make_pair(pNode, true));
            // 左子节点
            if (pNode->pLeft != nullptr){
                treeNodeVec.emplace_back(make_pair(pNode->pLeft, false));
            }
        }
        cout << endl;
    }
    

    参考文献:
    [1] 李春葆.数据结构教程(第4版)[M].172-181.
    [2] 何海涛.剑指Offer(第2版)[M].60-61.
    [3] https://blog.csdn.net/czy47/article/details/81254984

    展开全文
  • 题目1078:二叉树遍历题目描述:二叉树的前序、中序、后序遍历的定义:前序...给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。输入:两个字符串,其长度...

    题目1078:二叉树遍历

    题目描述:

    二叉树的前序、中序、后序遍历的定义:

    前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树;

    中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树;

    后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。

    给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。

    输入:

    两个字符串,其长度n均小于等于26。

    第一行为前序遍历,第二行为中序遍历。

    二叉树中的结点名称以大写字母表示:A,B,C....最多26个结点。

    输出:

    输入样例可能有多组,对于每组测试样例,

    输出一行,为后序遍历的字符串。

    样例

    输入:

    ABC

    BAC

    FDXEAG

    XDEFAG

    样例输出:

    BCA

    XEDGAF

    来源:

    2006年清华大学计算机研究生机试真题

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

    解析

    由前序遍历和中序遍历求后序遍历,这要求考生对三种遍历方式都有掌握。这里要用到前序遍历的根结点第一个被取出,而中序遍历的左子树在根结点之前取出、右子树在根结点之后取出,这两个性质。

    C++实现如下

    #include

    #include

    //1078:二叉树遍历

    using namespace std;

    //结点类

    struct Node

    {

    Node * lchild;

    Node * rchild;

    char c;

    };

    //重建后续排序二叉树

    Node * rebuild(string s1, string s2)

    {

    //建立根结点

    Node * t=NULL;//一定要初始化为NULL,不然报错

    if(s1.size()>0){

    t=new Node;

    t->c=s1[0];

    t->lchild=NULL;

    t->rchild=NULL;

    }

    if(s1.size()>1){

    //寻找根结点在中序遍历中的位置

    int root;

    for(int i=0; i

    if(s2[i]==t->c){

    root=i;

    break;

    }

    }

    //左子树重建

    string qianxu_left=s1.substr(1, root); //注意substr的用法,第二个参数是子字符串长度

    string zhongxu_left=s2.substr(0, root);

    t->lchild=rebuild(qianxu_left, zhongxu_left);

    //右子树重建

    string qianxu_right=s1.substr(root+1, s1.size()-root-1);

    string zhongxu_right=s2.substr(root+1, s2.size()-root-1);

    t->rchild=rebuild(qianxu_right, zhongxu_right);

    }

    return t;

    }

    //后序遍历:左右根

    void houxu(Node * t)

    {

    //左子树非空,遍历左子树

    if(t->lchild!=NULL)

    houxu(t->lchild);

    //右子树非空,遍历右子树

    if(t->rchild!=NULL)

    houxu(t->rchild);

    //取出该结点的值

    cout<c;

    }

    int main()

    {

    string s1, s2;

    while(cin>>s1>>s2){

    Node * t=rebuild(s1, s2);

    houxu(t);

    cout<

    }

    return 0;

    }运行结果

    Accepted 内存:1520KB  代码长度:1465B  耗时:10MS

    展开全文
  • 可以跟之前这篇形成对比http://blog.csdn.net/hhooong/article/details/43195395代码如下:#include#includeusing namespace std ;struct BinTreeNode {char data ;BinTreeNode *left ;BinTreeNode *right ;...

    可以跟之前这篇形成对比

    http://blog.csdn.net/hhooong/article/details/43195395

    代码如下:

    #include

    #include

    using namespace std ;

    struct BinTreeNode {

    char data ;

    BinTreeNode *left ;

    BinTreeNode *right ;

    };

    void BinTreeSuccess(char* post,char* in ,int length){

    if(length == 0){

    return ;

    }

    char value_node = post[length-1] ;

    int rootNum = 0 ;

    for(;rootNum

    if(in[rootNum] == value_node)

    break ;

    }

    cout <

    //cout <

    BinTreeSuccess(post,in,rootNum);//left_tree;

    BinTreeSuccess(post+rootNum,in+rootNum+1,length-rootNum-1);//right_tree;

    }

    int main (){

    char* post = "DGEBHIFCA";

    char* in ="DBGEACHFI";

    int length = 9;

    BinTreeSuccess(post,in,length);

    return 0;

    }贴个执行截图:看最下面的a.exe后输出的字符串

    0818b9ca8b590ca3270a3433284dd417.png

    展开全文
  • 根据一棵树的中序遍历后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 用例描述: 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树: 3 / 9 20 / 15 7 ...

    题目描述

    根据一棵树的中序遍历与后序遍历构造二叉树。
    注意:
    你可以假设树中没有重复的元素。

    用例描述:

    中序遍历 inorder = [9,3,15,20,7]
    后序遍历 postorder = [9,15,7,20,3]
    返回如下的二叉树:
    3
    /
    9 20
    /
    15 7

    思路

    1. 题目将中序遍历和后序遍历的结果以数组形式给出,不便于操作,因此可以用集合类来辅助完成二叉树的构建,这里我选用的是常用的list
    2. 如果中序遍历的list长度为0,说明是空树直接返回nul
    3. 如果中序遍历的list长度为1,说明当前节点是叶子节点,直接返回
    4. 根据后序遍历的list,取到最后一个元素就是根节点
    5. 根据中序遍历取到的第一个元素就是左子树位置记作leftsize
    6. 根据中序遍历结果,可将其分为:
      leftIn [0,leftSize) ; rightIn [ leftSize+1,inOrderList.size() )
    7. 根据后序遍历结果,可将其分为:
      leftPost [0,leftSize) ; rightPost [ leftSize,postOrderList.size()-1);

    代码如下:

    import java.util.ArrayList;
    import java.util.List;
    
    class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode(int val) {
            this.val = val;
        }
    }
    class Solution {
        private List<Integer> arrayToList(int[] arr){
            List<Integer> list = new ArrayList<>();
            for (int x : arr){
                list.add(x);
            }
            return list;
        }
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            //1.将数组转化为list
            List<Integer> inOrderList = arrayToList(inorder);
            List<Integer> postOrderList = arrayToList(postorder);
            //2.构建辅助方法
            return buildHelper(inOrderList,postOrderList);
        }
    
        private TreeNode buildHelper(List<Integer> inOrderList, List<Integer> postOrderList) {
            //如果inOrderList.size() == 0,说明为空树,直接返回null
            if (inOrderList.size() == 0){
                return null;
            }
            //如果inOrderList.size() == 1,说明当前树只有一个节点,直接返回该节点即可
            if (inOrderList.size() == 1){
                return new TreeNode(inOrderList.get(0));
            }
            //postOrderLise.get(postOrderList.size()-1)表示根节点的值
            int rootVal = postOrderList.get(postOrderList.size()-1);
            TreeNode root = new TreeNode(rootVal);
            //根据rootVal在中序遍历中确定左子树的位置
            int leftSize = inOrderList.indexOf(rootVal);
            List<Integer> leftIn = inOrderList.subList(0,leftSize);
            List<Integer> rightIn = inOrderList.subList(leftSize+1,inOrderList.size());
            List<Integer> leftPost = postOrderList.subList(0,leftSize);
            List<Integer> rightPost = postOrderList.subList(leftSize,postOrderList.size()-1);
            //递归创建左子树
            root.left = buildHelper(leftIn,leftPost);
            //递归创建右子树
            root.right = buildHelper(rightIn,rightPost);
            return root;
        }
    }
    
    展开全文
  • 二叉树的概念 1、每个节点最多只有两个子节点的树称为二叉树 2、二叉树的子节点分为左节点和右节点 3、如果二叉树的所有节点都在最后一层,并且节点总数为2^n-1,n为...后序遍历:先遍历左子树,再遍历右子树,最后输出
  • 二叉树的先序,中序,后序如何遍历,不在此多说了。...例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并输出它的后序遍历序列。输入:输入可能包含多个测试样例,对于每个...
  • 二叉树按照从左到右的规则,把六种遍历简化到只研究三种遍历:前序遍历(DLR),中序遍历(LDR),后序遍历(LRD)。 二叉树遍历的实质是递归。 目录 二叉树的遍历 前序遍历 中序遍历 后序遍历 练习写出下列...
  • 那么对下图而言,前序遍历为UNI,中序遍历为NUI,后序遍历为NIU,观察这三种情况,可以发现前中后实际上指的是根的遍历顺序。 实例 假设给定如下所示一颗二叉搜索树,那么我们如何对其进行前序遍历、中序遍历以及...
  • 实验目的编写一个程序,实现二叉树的先序遍历,中序遍历后序遍历。实验内容编程序并上机调试运行。编写一个程序,实现二叉树的先序遍历,中序遍历后序遍历。编写程序/***********二叉树的遍历**************/#...
  • void pre_order(TreeNode * Node)//前序遍历递归算法 { if(Node == NULL) return; printf("%d “, Node->data);//显示节点数据,可以更改为其他操作。在前面 pre_order(Node->left); pre_orde
  • 一、二叉树的遍历概念 二叉树的遍历是指从根结点触发,按照某种次序依次访问二叉树中所有结点,...中序遍历:若二叉树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然
  • 绝对要收藏【数据结构之树】一、基础概念二、前序遍历2.1 递归参考代码2.2 非递归参考代码 一、基础概念 树 :由n个有限节点组成的一个具有层次关系的集合; 根节点 :没有父节点的节点; 二、前序遍历 遍历顺序...
  • 链式存储结构存储的递归思想遍历二叉树之前讲过,树是由根结点和子树部分...遍历左子树,之后访问根结点,然后遍历右子树,称为“中序遍历”;遍历完左右子树,再访问根结点,称为“后序遍历”。三种方式唯一的不同...
  • 刚刚又 复习 预习了一下树的遍历,也刚好再看看每两种遍历方法组合后建立树的...1、已知前序遍历、中序遍历后序遍历 解题思想: 前序遍历中,根节点一定是会出现在最前面,我们就可以通过这个点来得到每个子树的根
  • /*分别使用递归思想与迭代思想实现二叉树的前序遍历、中序遍历后序遍历*/ //递归思想实现前序遍历、中序遍历后序遍历 //1、递归思想实现前序遍历 void PreOrderTraverse(BitTree T) { if (T == NULL) return; ...
  • 填空题:已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为_____________。  答案:DGEBHFCA。  解题过程:  一、基本概念扫盲:对一棵二叉树进行遍历,我们可以采取3中顺序...
  • 图6.1.13应输出的后序遍历序列为ACBMXZPD注意:你的程序应能鉴别任何的错误输入。题解1鉴别错误输入设predstr—前序串;s1—前序串的字符集;midstr—中序串;s2—中序串的字符集;predstr串与midstr串必须同时满足...
  • 用递归方法实现二叉树的中序遍历后序遍历算法 //用递归方法实现二叉树的中序遍历后序遍历算法; #include "stdio.h" #include "stdlib.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef char ...
  • /*** 给出先序遍历和中序遍历序列求出二叉树的后续遍历序列* @author wxisme**/public class ToReverse {public static void main(String[] args) {Scanner scan = new Scanner(System.in);Stri...
  • 本文主要讲解如何根据二叉树的中序遍历后序遍历,构建树。 在写PTA的钻石争霸赛时,在写最后一道题时,刚开始需要根据二叉树的中序遍历后序遍历,构建二叉树,然后才能继续写题。经过当时向学长学习之后,也完成...
  • // 再后序遍历右子树 Visit(T->data); // 最后访问根结点 } } void main() { BiTree T; InitBiTree(T); // 初始化二叉树T printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\n")...
  • 对二叉树的前中后序递归以及非递归算法以及层序遍历思想做了整合 因为某些书籍上对这类算法,写的非常笼统,所以,这里将从树的链式存储开始,结合整个 链表、栈、队列等结构来完成对树的学习,当然,这里也将会完美...
  • void dfs(int t) { //实际上就是按中序遍历的顺序访问 if(t > n) return ; dfs(t << 1); ans[t] = zx[++ idx]; dfs(t << 1 | 1); } dfs(1); 后序转层序: int idx = 0; void dfs(int t) { //...
  • 递归时,如果不先print,则是递归调用到最底层之后再print,所以这里我们看到的中序遍历以及后序遍历都是从最底部向上输出的。
  • 给树的后序和中序遍历,求先序遍历 假设有一棵树长这样 很容易写出他的后序遍历DBAGFEC 也很容易写出他中序遍历DABCGEF 1.后序遍历是前后根,根节点永远是最后一个,因此我们可以找到根节点c 2.要我们输出前序遍历...
  • 节点→左孩子→右孩子 preorder中序遍历。左孩子→节点→右孩子 inorder后序遍历。左孩子→右孩子→节点 postorder2、宽度优先搜索(BFS)就是从上到下,从左到右一层一层一个一个的访问上图from leetcode这样记忆就会...
  • 两种特殊的二叉树 完全二叉树: 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个...先序遍历 :先遍历根节点,再遍历左节点,最后遍历右节点
  • public class 算法训练根据前中序遍历后序遍历 { static StringBuffer str=new StringBuffer(); public static void main(String[] args) { Scanner sc=new Scanner(System.in); String q=sc.next(); String z...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 79,151
精华内容 31,660
关键字:

中序遍历转后序遍历