二叉树的中序遍历

以你之姓@ 2021-09-29 14:22 333阅读 0赞

### 题目描述 ###

在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。如下图，每个节点有一个编号。树的访问方式叫做中序遍历，方法为：首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树。如下图，中序遍历为：4、3、7、1、6、2、5、8。现在输入一棵二叉树（根的编号一定是1），请你输出二叉树的中序遍历。

![Failed to load picture][]

### 输入输出格式 ###

#### 输入格式： ####

第一行，一个整数n，代表二叉树节点个数，它的范围在\[1...10000\]；

第2-n+1行，每行三个整数，第一个整数代表第i个节点的编号，第二个整数左儿子的编号，第三个整数为右儿子的编号，如果没有左或者右儿子则为0。

#### 输出格式： ####

依次输出二叉树中序遍历节点。

### 输入输出样例 ###

**输入样例：**

8 
    1 3 5 
    2 0 0 
    3 4 7 
    4 0 0 
    5 6 8 
    6 0 2 
    7 0 0 
    8 0 0

**输出样例：**

4 3 7 1 6 2 5 8
    
    思路：搜左，出根，搜右。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//程序名:新的C++程序
    //作者: 
    
    #include<iostream>
    #include<fstream>
    #include<algorithm>
    
    using namespace std;
    int f;
    struct tree
    {
        int root;
        int ls,rs,no;
    }a[10001];
    void mid(int i)
    {
        if(a[i].ls)mid(a[i].ls);
        if(!f)cout<<i,f++;
        else cout<<" "<<i;
        if(a[i].rs)mid(a[i].rs);
    }
    int m;
    int main()
    {
        cin>>m;
        for(int i=1;i<=m;i++)cin>>a[i].no>>a[i].ls>>a[i].rs;
        mid(1);
        return 0;
    }

转载于:https://www.cnblogs.com/2006hanziwei/p/10744052.html

[Failed to load picture]: /images/20210725/26922696ea1046ca9f4d71f8646d17a1.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/d4c538826b054373b6499627199c5e90.png