编程与算法

二叉树的实现以及先中后序遍历

好久没有记录自己的数据结构的学习进度了,现在来写一下最近的二叉树的创建和先中后序遍历

首先来说一下二叉树的创建,二叉树的创建实际上很简单,原理是使用递归调用,递归调用的一个好处就是不用自己设计Stack,使用的系统的Stack,这样就省去了一些麻烦

这里就不解释递归的工作原理了,直接上代码

BiTree createBtree(BiTree *root){
    char temp;
    scanf("%c",&temp);
    if(temp == '$')
        return NULL;
    if(!(*root)){
        *root = (BiTree)calloc(1,sizeof(struct BTNode));
    }
    (*root)->data = temp;
    createBtree(&((*root)->lchild));
    createBtree(&((*root)->rchild));
}

这个递归里BiTree的定义如下

typedef struct BTNode{     
    char data ;             
    struct BTNode *lchild;
    struct BTNode *rchild ;  
}*BiTree;

这里的BiTree本来就是一个指针,函数的形参里使用的是指向指针的指针,为什么使用指向指针,是因为如果仅仅使用指针,则会导致只修改了局部的指针变量而没有修改总体的指针变量,因此为了保证整体的指针能整体被改动,所以要用指向指针的指针,这里可能就会因为只使用一个指针导致将内存地址带回

这里容易分不清局部变量和指针的内容,使用C++的引用就不会出现这种情况

剩下的先中后序便利就十分简单了,就不再赘述

void DLR(BiTree root){
    if(!root)
        return ;
    else{
        printf("%c",root->data);
        DLR(root->lchild);
        DLR(root->rchild);
    }
}
void LDR(BiTree root){
    if(!root)
        return ;
    else{
        LDR(root->lchild);
        printf("%c",root->data);
        LDR(root->rchild);
    }
}
void LRD(BiTree root){
    if(!root)
        return ;
    else{
        LRD(root->lchild);
        LRD(root->rchild);
        printf("%c",root->data);
    }
}

发表评论

您的电子邮箱地址不会被公开。