【数据结构与算法】二叉树遍历

二叉树的遍历

因为使用二叉树最多是 链式存储结构，所遍历的方式也是按照链式结构来的。

遍历的宗旨

在遍历是按照某种次序依次访问二叉树的所有节点，并且每个节点仅仅 被访问一次。

前序遍历（根左右）

遍历顺序 ABDHIEJCFKG

中序遍历（左根右）

遍历顺序 HDIBEJAFKCG

后序遍历（左右根）

遍历顺序 HIDJEBKFGC

层序遍历

遍历顺序 ABCDEFGHIJK

二叉树代码实现

前序遍历（根左右）

二叉树的遍历方式，在创建二叉树时就确定好了

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

// 二叉树结构
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
} BiTNode, *BiTree;

// 创建二叉树 按照用户遵循的 前序遍历的（根左右） 方式输入数据
void createBiTree(BiTree *T){
    char c;
    printf("输入元素：");
    scanf("%c",&c);
    getchar();
    if (c == '#'){
        *T = NULL;
    } else{
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = c;
        createBiTree(&(*T)->lchild); // 先创建左子节点
        createBiTree(&(*T)->rchild); // 再创建右子节点
    }
}

// 遍历二叉树
void preOrderTraverse(BiTree T,int level){
    if(T!=NULL){
        printf("数据 %c 在第 %d 层\n", T->data, level);
        preOrderTraverse(T->lchild,level+1);
        preOrderTraverse(T->rchild,level+1);
    }
}

int main(){
    int level = 1;
    BiTNode *T;

    createBiTree(&T);
    preOrderTraverse(T,level);

    return 0;
}

输入顺序

中序遍历（左根右）

输入方式还是前序的输入方式，只是遍历的打印位置修改了一下

// 中序遍历二叉树
void preOrderTraverse(BiTree T,int level){
    if(T!=NULL){
        preOrderTraverse(T->lchild,level+1);
        printf("数据 %c 在第 %d 层\n", T->data, level);
        preOrderTraverse(T->rchild,level+1);
    }
}

后序遍历（左右后）

输入方式还是前序的输入方式，只是遍历的打印位置修改了一下

// 后序遍历二叉树
void preOrderTraverse(BiTree T,int level){
    if(T!=NULL){
        preOrderTraverse(T->lchild,level+1);
        preOrderTraverse(T->rchild,level+1);
        printf("数据 %c 在第 %d 层\n", T->data, level);
    }
}