C语言--数据结构--实现先序遍历、中序遍历、后序遍历、二叉树的高度、二叉树结点总数；

朱雀 2024-03-30 08:52 57阅读 0赞

掌握二叉树的二叉链表存储结构的表示与实现，掌握和验证在二叉链表存储结构下完成二叉树的遍历及其应用操作的实现方法；

1）结构体

typedef struct Node//二叉树的二叉链表存储表示；
    
    {
    
        char data;//节点数据域；
    
        struct Node*lchild;//左孩子指针；
    
        struct Node*rchild;//右孩子指针；
    
    } Node,*Tree;

2）创建二叉树便于下一步操作

void CreateTree(Tree*T)
    
    //先序创建二叉树；
    
    {
    
        char ch;
    
        scanf("%c",&ch);//输入字符；
    
        if(ch=='#')
    
            (*T)=NULL;//递归结束，为空树；
    
        else
    
        {
    
            *T=(Tree)malloc(sizeof(Node));//创建二叉树空间；
    
            (*T)->data=ch;//根节点数据域置为ch；
    
            CreateTree(&(*T)->lchild);//递归创建左子树；
    
            CreateTree(&(*T)->rchild);//递归创建右子树；
    
    
    
        }
    
    }

三种遍历方法：

1、先序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。（根，左，右）  
2、中序遍历：若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点（左，根，右）  
3、后序遍历：若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。（左，右，根）

void PreOrderTraverse(Tree T)
    
    //先序遍历二叉树；根，左，右；
    
    {
    
        if(T)//如果T非空；
    
        {
    
            printf("%c",T->data);
    
            PreOrderTraverse(T->lchild);//先序遍历左子树；
    
            PreOrderTraverse (T->rchild);//先序遍历右子树；
    
    
    
        }
    
    }
    
    
    
    void InOrderTraverse(Tree T)
    
    //中序遍历二叉树；左，根，右；
    
    {
    
    
    
        if(T)//如果T非空；
    
        {
    
    
    
            PreOrderTraverse(T->lchild);//中序遍历左子树；
    
            printf("%c",T->data);
    
            PreOrderTraverse (T->rchild);//中序遍历右子树；
    
        }
    
    }
    
    
    
    void PostOrderTraverse(Tree T)
    
    //后序遍历二叉树；左，右，根；
    
    {
    
    
    
        if(T)//如果T非空；
    
        {
    
    
    
            PreOrderTraverse(T->lchild);//后序遍历左子树；
    
            PreOrderTraverse (T->rchild);//后序遍历右子树；
    
            printf("%c",T->data);
    
        }
    
    }

计算二叉树的高度

int Depth(Tree T)
    
    //计算二叉树的高度；
    
    {
    
        int m,n;
    
    
    
        if(T==NULL) return 0;//如果是空树，高度为0；
    
        else
    
        {
    
            m=Depth(T->lchild);//递归计算左子树的高度；
    
            n=Depth(T->rchild);//递归计算右子树的高度；
    
            if(m>n)
    
            {
    
                return (m+1);   //二叉树的高度为左右子树较大者+1；
    
            }
    
            else return (n+1);
    
        }
    
    
    
    }

计算二叉树的节点个数

int NodeCount(Tree T)
    
    //统计二叉树的节点个数；
    
    {
    
        if(T==NULL) return 0;//如果是空树，节点个数为0；
    
        else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
    
        //节点个数=左子树节点+右子树节点+根节点；
    
    }

main函数

int main( )
    
    {
    
    
    
        printf("创建一个带节点的二叉树链表： ");
    
        Tree T=NULL;//此时未创建二叉树；
    
        CreateTree(&T);//& 创立一颗二叉树；
    
        printf("先序遍历二叉树为:");
    
        PreOrderTraverse(T);
    
        printf(" ");
    
        printf("中序遍历二叉树为：");
    
        InOrderTraverse(T);
    
        printf(" ");
    
        printf("后序遍历二叉树为：");
    
        PostOrderTraverse(T);
    
        printf(" ");
    
        printf("二叉树的高度为：%d ",Depth(T));
    
        printf("二叉树的节点总数为：%d ",NodeCount(T));
    
    
    
    }

全部代码的实现：

#include<stdio.h>
    
    #include<stdlib.h>
    
    
    
    typedef struct Node//二叉树的二叉链表存储表示；
    
    {
    
        char data;//节点数据域；
    
        struct Node*lchild;//左孩子指针；
    
        struct Node*rchild;//右孩子指针；
    
    } Node,*Tree;
    
    
    
    void CreateTree(Tree*T)
    
    //先序创建二叉树；
    
    {
    
        char ch;
    
        scanf("%c",&ch);//输入字符；
    
        if(ch=='#')
    
            (*T)=NULL;//递归结束，为空树；
    
        else
    
        {
    
            *T=(Tree)malloc(sizeof(Node));//创建二叉树空间；
    
            (*T)->data=ch;//根节点数据域置为ch；
    
            CreateTree(&(*T)->lchild);//递归创建左子树；
    
            CreateTree(&(*T)->rchild);//递归创建右子树；
    
    
    
        }
    
    }
    
    
    
    void PreOrderTraverse(Tree T)
    
    //先序遍历二叉树；根，左，右；
    
    {
    
        if(T)//如果T非空；
    
        {
    
            printf("%c",T->data);
    
            PreOrderTraverse(T->lchild);//先序遍历左子树；
    
            PreOrderTraverse (T->rchild);//先序遍历右子树；
    
    
    
        }
    
    }
    
    
    
    void InOrderTraverse(Tree T)
    
    //中序遍历二叉树；左，根，右；
    
    {
    
    
    
        if(T)//如果T非空；
    
        {
    
    
    
            PreOrderTraverse(T->lchild);//中序遍历左子树；
    
            printf("%c",T->data);
    
            PreOrderTraverse (T->rchild);//中序遍历右子树；
    
        }
    
    }
    
    
    
    void PostOrderTraverse(Tree T)
    
    //后序遍历二叉树；左，右，根；
    
    {
    
    
    
        if(T)//如果T非空；
    
        {
    
    
    
            PreOrderTraverse(T->lchild);//后序遍历左子树；
    
            PreOrderTraverse (T->rchild);//后序遍历右子树；
    
            printf("%c",T->data);
    
        }
    
    }
    
    
    
    int Depth(Tree T)
    
    //计算二叉树的高度；
    
    {
    
        int m,n;
    
    
    
        if(T==NULL) return 0;//如果是空树，高度为0；
    
        else
    
        {
    
            m=Depth(T->lchild);//递归计算左子树的高度；
    
            n=Depth(T->rchild);//递归计算右子树的高度；
    
            if(m>n)
    
            {
    
                return (m+1);   //二叉树的高度为左右子树较大者+1；
    
            }
    
            else return (n+1);
    
        }
    
    
    
    }
    
    
    
    int NodeCount(Tree T)
    
    //统计二叉树的节点个数；
    
    {
    
        if(T==NULL) return 0;//如果是空树，节点个数为0；
    
        else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
    
        //节点个数=左子树节点+右子树节点+根节点；
    
    }
    
    int main( )
    
    {
    
    
    
        printf("创建一个带节点的二叉树链表： ");
    
        Tree T=NULL;//此时未创建二叉树；
    
        CreateTree(&T);//& 创立一颗二叉树；
    
        printf("先序遍历二叉树为:");
    
        PreOrderTraverse(T);
    
        printf(" ");
    
        printf("中序遍历二叉树为：");
    
        InOrderTraverse(T);
    
        printf(" ");
    
        printf("后序遍历二叉树为：");
    
        PostOrderTraverse(T);
    
        printf(" ");
    
        printf("二叉树的高度为：%d ",Depth(T));
    
        printf("二叉树的节点总数为：%d ",NodeCount(T));
    
    
    
    }