第4章第1节练习题1 二叉树的基本操作(递归实现)

时间:2023-02-23 23:35:56

二叉树的递归遍历

所谓二叉树的遍历,本质上就是沿某条搜索路径访问树中的每个结点,使得每个节点均被访问一次,而且仅被访问一次。

由二叉树的基本定义可以知道,遍历一颗二叉树首先必须决定对根结点(N),左子树(L),右子树(R)的访问顺序,按照先遍历左孩子再遍历右孩子的原则,常见的遍历次序有先序遍历(NLR)中序遍历(LNR)后序遍历(LRN)三种遍历算法。

在这里使用做个简单的例子来说明下。
第4章第1节练习题1 二叉树的基本操作(递归实现)

一.先序遍历

先序遍历的操作过程为:

Created with Raphaël 2.1.0 开始 二叉树是否为空? 结束 访问根结点 先序遍历左子树 先序遍历右子树 yes no

那么先序遍历的结果应该为
A->B->D->F->C->E

这样根据定义便可以写出相应的算法描述

void PreOrder(BiTNode* T){
    if(T==NULL){
        return;
    }else{
        printf("%c",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

二.中序遍历

中序遍历的过程为:

Created with Raphaël 2.1.0 开始 二叉树是否为空? 结束 先序遍历左子树 访问根结点 先序遍历右子树 yes no

那么中序遍历的结果应该为
B->F->D->A->C->E

这样根据定义便可以写出相应的算法描述

void InOrder(BiTNode* T){
    if(T==NULL){
        return;
    }else{
        InOrder(T->lchild);
        printf("%c",T->data);
        InOrder(T->rchild);
    }
}

三.后序遍历

后序遍历的过程为:

Created with Raphaël 2.1.0 开始 二叉树是否为空? 结束 先序遍历左子树 先序遍历右子树 访问根结点 yes no

那么后序序遍历的结果应该为
F->D->B->E->C->A

这样根据定义便可以写出相应的算法描述

void PostOrder(BiTNode* T){
    if(T==NULL){
        return;
    }else{
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%c",T->data);
    }
}

上述算法中,递归遍历左、右子树的顺序都是固定的,只是访问根结点的顺序不同。不管采用哪种遍历算法,每个节点都访问一次且仅访问一次,故时间复杂度都是 O(n) 。在递归遍历中,递归工作栈的栈深度恰好为树的深度,所以在最坏的情况下,二叉树有n个结点且深度为n的单支树,遍历算法的空间复杂度为 O(n)

完整代码见附件


附件

//AB#DF###C#E##
#include<stdio.h>
#include<stdlib.h>

#define MaxSize 100
typedef char ElemType;
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

BiTree CreateBiTree(BiTNode*);
void PreOrder(BiTNode*);
void InOrder(BiTNode*);
void PostOrder(BiTNode*);

int main(int argc, char* argv[]){
    BiTNode *T;
    T=(BiTNode*)malloc(sizeof(BiTNode));
    T=CreateBiTree(T);
    PreOrder(T);
    printf("\n");
    InOrder(T);
    printf("\n");
    PostOrder(T);
    printf("\n");
    return 0;
}

BiTree CreateBiTree(BiTNode* T){
    ElemType x;
    scanf("%c",&x);
    if(x=='#'){
        return T;
    }
    T=(BiTNode*)malloc(sizeof(BiTNode));
    T->data=x;
    T->lchild=CreateBiTree(T->lchild);
    T->rchild=CreateBiTree(T->rchild);
    return T;
}

void PreOrder(BiTNode* T){
    if(T==NULL){
        return;
    }else{
        printf("%c",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void InOrder(BiTNode* T){
    if(T==NULL){
        return;
    }else{
        InOrder(T->lchild);
        printf("%c",T->data);
        InOrder(T->rchild);
    }
}

void PostOrder(BiTNode* T){
    if(T==NULL){
        return;
    }else{
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%c",T->data);
    }
}