二叉树

二叉树是一种递归形式的双链表，二叉树的实现主要是利用双重递归的调用来创建左子树和右子树的。二叉树的遍历分为三种方式：一种是先序遍历，即根左右。另一种是中序遍历，即左根右。最后一种是后序遍历，即左右根。本文是以先序的方式创建的二叉树。二叉树的递归形式代码如下：

#include <iostream>#include <stdio.h>#include <stdlib.h>/* run this program using the console pauser or add your own getch, system("pause") or input loop *///定义树的结构typedef struct BiTNode{    char data;//数据域     struct BiTNode *lchild,*rchild;//左结点和右节点 }BiTNode,*BiTree;//创建二叉树,利用先序递归的方式(根左右) BiTree CreateBiTree(BiTree &T){    char x;    scanf("%c",&x);    if(x=='#'){        return T=NULL;    }else{        T = (BiTNode*)malloc(sizeof(BiTNode));//创建结点        T->data = x;        T->lchild = CreateBiTree(T->lchild);//创建左子树        T->rchild = CreateBiTree(T->rchild);//创建右子树         return T;       }}//遍历二叉树(先序遍历)void  preTree(BiTree T){//T始终指向的是根结点,然后通过根结点依次链接     if(T!=NULL){        printf("%c\t",T->data);        preTree(T->lchild);        preTree(T->rchild);    }}//遍历二叉树(中序遍历)void  inTree(BiTree T){//T始终指向的是根结点,然后通过根结点依次链接     if(T!=NULL){        inTree(T->lchild);        printf("%c\t",T->data);        inTree(T->rchild);    }}//遍历二叉树(后序遍历)void  finishTree(BiTree T){//T始终指向的是根结点,然后通过根结点依次链接     if(T!=NULL){        finishTree(T->lchild);        finishTree(T->rchild);        printf("%c\t",T->data);    }}//二叉树结点总数int Count(BiTree T){    if(T==NULL){//空二叉树结点数为0        return 0;    }else{//左右子树结点总数加1        return Count(T->lchild)+Count(T->rchild)+1;    }}//叶子数 int LeafCount(BiTree T){    if(T == NULL){        return 0;    }else if((T->lchild==NULL) && (T->rchild==NULL)){        return 1;    }else{        return LeafCount(T->lchild)+LeafCount(T->rchild);    }}//统计叶子结点 int Leaf(BiTree T){    int LeafCount = 0;    if(T!=NULL)    {        Leaf(T->lchild);        Leaf(T->rchild);        if(T->lchild==NULL && T->rchild==NULL)        {            LeafCount++;   //统计叶子结点数目        }    }    return LeafCount;} int main(int argc, char** argv) {    BiTree T;    printf("请输入创建结点的观察值:\n");    CreateBiTree(T);    printf("创建成功!\n");    printf("先序遍历:\n");    preTree(T);    printf("\n中序遍历:\n");    inTree(T);    printf("\n后序遍历:\n");    finishTree(T);    printf("\n二叉树结点总数:\n");    Count(T);    printf("二叉树叶子结点总数:\n");    LeafCount(T);    Leaf(T);    return 0;}

更多相关文章

随机推荐