树的遍历

这是一篇水文【理直气壮】

废话不多说先上代码

先序遍历

void PreorderTravel(AVLTree T)
{
    if (T != NULL)
    {
        printf("%d\n", T->Element);
        PreorderTravel(T->Left);
        PreorderTravel(T->Right);
    }
}

节点在其儿子的节点前进行处理，这种遍历可以用来利用节点深度来标记每一个节点

中序遍历

void InorderTravel(AVLTree T)
{
    if (T != NULL)
    {
        InorderTravel(T->Left);
        printf("%d\n", T->Element);
        InorderTravel(T->Right);
    }
}

中序遍历的一般策略是首先遍历左子树，然后是当前节点，最后遍历右子树，这个算法有趣的部分除他简单的特性外，还在于总运行时间为O（N）。这是因为在树的每一个节点除进行的工作都是常数时间的，每一个节点访问一次，而在每一个节点进行的工作是检测是否为NULL，建立两个过程调用并执行输出函数，由于每个节点的工作发费时间以及总共有N个节点，因此运行时间为O（N）；

后序遍历

void PostorderTravel(AVLTree T)
{
    if (T != NULL)
    {
        PostorderTravel(T->Left);
        PostorderTravel(T->Right);
        printf("%d\n", T->Element);
    }
}

当有时我们需要处理两个子树然后才能处理当前节点。例如，为了计算一个节点的高度，我们需要知道他两棵子树的高度，由于检查一些特殊情况总是有益的，特别是啊在我们使用递归的情况下。因此我们需要注意这个声明中的树叶的高度，运行时间和上面同出一辙也是O（N）；

新的更新加上了层序遍历

层序遍历和bfs很像，从上到下一层一层的进行遍历

根节点root加入队列
取出队首节点访问它
如果该节点有左孩子，将左孩子入队
如果该节点有右孩子，将右孩子入队
返回第二步，直到队列为空。

void LayerOrder(T root){
    queue<T>q;
    q.push(root);
    while(!q.empty()){
        T now=q.front();
        q.pop();
        cout<<now->data;
        if(now->Left!=nullptr)
        q.push(now->Left);
        if(now->Right!=nullptr)
        q.push(now->Right);
    }
}