数据结构严薇敏——简单二叉树的建立、先序、中序、后序递归遍历及求叶子结点数

心已赠人 2022-05-18 07:39 53阅读 0赞

**采用二叉树的二叉链表存储表示**

**它的存储结构为：**

typedef char ElemType;
    
    typedef struct BiTNode
    {
        ElemType data;
        struct BiTNode *lchild,*rchild;
    }BiTNode;

**使用递归来实现下图中二叉树的建立、遍历、求叶子节点。**

![70][]

## **实现代码：** ##

#include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElemType;
    
    typedef struct BiTNode
    {
        ElemType data;
        struct BiTNode *lchild,*rchild;
    }BiTNode;
    
    void PreTraverse(BiTNode *root)      //先序
    {
        if(root == NULL)
            return;
    
        printf("%c",root->data);
        PreTraverse(root->lchild);
        PreTraverse(root->rchild);
    }
    void InTraverse(BiTNode *root)       //中序
    {
        if(root == NULL)
            return;
    
    
        InTraverse(root->lchild);
        printf("%c",root->data);
        InTraverse(root->rchild);
    }
    void PostTraverse(BiTNode *root)     //后序
    {
        if(root == NULL)
            return;
    
        PostTraverse(root->lchild);
        PostTraverse(root->rchild);
        printf("%c",root->data);
    }
    
    void CountLeafNUm(BiTNode *root,int *leafnum)           //计算叶子节点
    {
        if(root == NULL)
            return;
        if(root->lchild == NULL && root->rchild == NULL)
            (*leafnum)++;
        CountLeafNUm(root->lchild, leafnum);
        CountLeafNUm(root->rchild, leafnum);
    }
    void CreateTree()
    {
        BiTNode node1 = {'A',NULL,NULL};
        BiTNode node2 = {'B',NULL,NULL};
        BiTNode node3 = {'C',NULL,NULL};
        BiTNode node4 = {'D',NULL,NULL};
        BiTNode node5 = {'E',NULL,NULL};
        BiTNode node6 = {'F',NULL,NULL};
        BiTNode node7 = {'G',NULL,NULL};
    
        node1.lchild = &node2;
        node1.rchild = &node3;
        node2.rchild = &node4;
        node4.lchild = &node7;
        node3.lchild = &node5;
        node3.rchild = &node6;
    
        printf("\n先序遍历为：");
        PreTraverse(&node1);
        printf("\n中序遍历为：");
        InTraverse(&node1);
        printf("\n后序遍历为：");
        PostTraverse(&node1);
    
        int leafnum = 0;
        CountLeafNUm(&node1,&leafnum);
        printf("\n叶子节点的数目为：%d",leafnum);
        printf("\n");
    }
    int main()
    {
        CreateTree();
        return 0;
    }

[70]: /images/20220518/d2a474ef3f91412caeb21e2741756781.png