用二叉链表存储的二叉树进行先序、中序和后序遍历的算法

我会带着你远行 2023-10-17 16:19 0阅读 0赞

> #### 用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作 ####

#include<iostream>  
    #include<cstdio>  
    #include<stdlib.h>  
    using namespace std;  
    typedef int Elemtype;  
    typedef struct BiTnode  
    {  
            Elemtype data;//数据域  
            struct BiTnode* Lchild,*Rchild; //左右子树域；  
    }BiTnode,*BiTree;  
      
    int create(BiTree *T)  
    {  
            Elemtype ch;  
            Elemtype temp;  
            scanf("%d",&ch);  
            temp=getchar();  
            if(ch==-1)  
            {  
                    *T=NULL;  
            }  
            else  
            {  
                    *T=(BiTree)malloc(sizeof(BiTnode) );  
                    if(!(*T))  
                    {  
                        exit(-1);  
                    }  
                    else  
                    {  
                            (*T)->data=ch;  
                            printf("请输入%d的左节点的值",ch);  
                            create(&(*T)->Lchild);  
                            printf("请输入%d的右节点的值",ch);  
                            create(&(*T)->Rchild);  
                    }  
      
            }  
            return 1;  
      
    }  
      
    void Traverse(BiTree T)//前序遍历二叉树  
    {  
            if(NULL==T)  
            {  
                    return;  
            }  
            else  
            {  
                printf("%d ",T->data);  
                Traverse(T->Lchild);  
                Traverse(T->Rchild);  
            }  
      
    }  
      
    //中序遍历二叉树  
    void midTraverse(BiTree T)  
    {  
            if(T==NULL){return;}  
            midTraverse(T->Lchild);  
            printf("%d ",T->data);  
            midTraverse(T->Rchild);  
    }  
      
    //后序遍历二叉树  
    void lasTraverse(BiTree T)  
    {  
            if(T==NULL){return;}  
            lasTraverse(T->Lchild);  
            lasTraverse(T->Rchild);  
            printf("%d ",T->data);  
      
    }  
      
    //求二叉树的深度  
    int TreeDeep(BiTree T)  
    {  
            int deep=0;  
            if(T)  
            {  
                    int leftdeep=TreeDeep(T->Lchild);  
                    int rightdeep=TreeDeep(T->Rchild);  
                    deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1;  
      
            }  
            return deep;  
      
    }  
      
    //求二叉树叶子节点个数  
    int Leafcount(BiTree T,int &num)  
    {  
            if(T)  
            {  
                    if(T->Lchild==NULL&&T->Rchild==NULL)  
                    {  
                            num++;  
                    }  
                    Leafcount(T->Lchild,num);  
                    Leafcount(T->Rchild,num);  
            }  
            return num;  
    }  
      
      
      
    int main()  
    {  
         BiTree T;  
         BiTree *p=(BiTree*)malloc(sizeof(BiTree));  
         int deepth=0,num=0;  
         printf("请输入第一个节点的值，-1代表没有叶节点:\n");  
         create(&T);  
         printf("先序遍历二叉树：\n");  
         Traverse(T);  
         printf("\n");  
         printf("中序遍历二叉树:\n");  
         midTraverse(T);  
         printf("\n");  
         printf("后序遍历二叉树：\n");  
         lasTraverse(T);  
         printf("\n");  
         deepth=TreeDeep(T);  
         printf("树的深度:%d\n",deepth);  
         printf("\n");  
         Leafcount(T,num);  
         printf("二叉树的叶子节点个数为:%d\n",num);  
         printf("\n");  
         return 0;  
    }

![Center][]![Center][]

[Center]: https://img-blog.csdn.net/20171012123724331?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcHJpbnRmODg=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center