算法与数据结构之二叉树的遍历

二叉树的遍历方式

前序遍历(Preorder)

前序遍历就是先访问根节点，再访问左子节点，最后访问右子节点的遍历方式

中序遍历(Inorder)

中序遍历是先访问左子节点，再访问根节点，最后访问右子节点的遍历方式

后序遍历(Postorder)

后序遍历是先访问左子节点，再访问右子节点，最后访问根节点的遍历方式

二叉树的遍历

二叉树的遍历可以通过递归来实现。递归终止的条件是当前节点为空节点，然后返回。前中后序遍历的递归函数不同之处只是输出当前节点的那条语句不同。

题目

假设二叉树有n个节点，编号分别为0至n-1。

输入数据第一行给出节点数，然后接下来的n行按以下个数给出节点信息：

id left right

id为节点编号，left为左子结点编号，right为右子结点编号。当结点不存在时，编号为-1

题目在

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C

样例输入

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

样例输出

Preorder
 0 1 2 3 4 5 6 7 8
Inorder
 2 1 3 0 6 5 7 4 8
Postorder
 2 3 1 6 7 5 8 4 0

代码实现

#include<iostream>
using namespace std;
#define MAX 25
#define NIL -1

struct Node
{
    int parent;
    int left;
    int right;
};

Node T[MAX];
int n,root;


void preorder(int id)
{
    cout<<" "<<id;
    if(T[id].left!=NIL)
    {
        preorder(T[id].left);
    }
    if(T[id].right !=NIL)
    {
        preorder(T[id].right);
    }

}

void inorder(int id)
{

    if(T[id].left!=NIL)
    {

        inorder(T[id].left);
    }
    cout<<" "<<id;
    if(T[id].right !=NIL)
    {
        inorder(T[id].right);
    }

}


void Postorder(int id)
{

    if(T[id].left!=NIL)
    {

        Postorder(T[id].left);

    }

    if(T[id].right !=NIL)
    {

        Postorder(T[id].right);
    }
    cout<<" "<<id;

}




int main()
{
    for(int i=0;i<MAX;i++)
    {
        T[i].parent = NIL;
        T[i].left = NIL;
        T[i].right = NIL;
    }

    cin>>n;
    for(int i=0;i<n;i++)
    {
        int id,left,right;
        cin>>id>>left>>right;
        T[id].left = left;
        T[id].right = right;
        T[left].parent = id;
        T[right].parent = id;

    }
    for(int i=0;i<n;i++)
    {
        if(T[i].parent == NIL)
        {
            root = i;
            break;
        }
    }
    cout<<"Preorder"<<endl;
    preorder(root);
    cout<<endl<<"Inorder"<<endl;
    inorder(root);
    cout<<endl<<"Postorder"<<endl;
    Postorder(root);
    cout<<endl;


}

注意事项

二叉树的遍历会对每一个节点进行访问，因此时间复杂度为O(n)。使用递归实现遍历算法的时候要注意，一旦树的结点数量庞大且分布不均匀，那么就很可能导致递归深度过深，最终堆栈溢出，boom~

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~