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

二叉树的遍历

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

遍历的宗旨

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

前序遍历(根左右)

遍历顺序 ABDHIEJCFKG

mark

中序遍历(左根右)

遍历顺序 HDIBEJAFKCG

mark

后序遍历(左右根)

遍历顺序 HIDJEBKFGC

mark

层序遍历

遍历顺序 ABCDEFGHIJK

mark

二叉树代码实现

前序遍历(根左右)

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

#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;
}

输入顺序

mark

中序遍历(左根右)

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

// 中序遍历二叉树
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);
    }
}

mark

后序遍历(左右后)

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

// 后序遍历二叉树
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);
    }
}

mark

发表评论 / Comment

用心评论~