数据结构-递归遍历二叉树

缺乏、安全感 2022-08-24 11:45 175阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    typedef char TelemType;
     
    typedef struct TNode{
        TelemType data;
        struct TNode *lchild,*rchild;
    } BitNode;
    
    
    //声明
    BitNode* createTree(void);
    void preOrderTraverse(BitNode *);
    void inOrderTraverse(BitNode *);
    void lastOrderTraverse(BitNode *);
     
     
    int main(int agrc,char *argv[]){
        BitNode *root=NULL;
        root=createTree();  
        printf("\n先序遍历二叉树:");
        preOrderTraverse(root);
        printf("\n中序遍历二叉树:");
        inOrderTraverse(root);
        printf("\n后序遍历二叉树:");
        lastOrderTraverse(root);
         
        return 0;
    }
     
    //创建二叉树(先序创建二叉树)
    BitNode* createTree(void){
        BitNode *b;
        TelemType ch;
        scanf("%c",&ch);
        if(ch=='#'){
            b=NULL;
        }else{
            b=(BitNode *)malloc(sizeof(BitNode));
            b->data=ch;
            b->lchild=createTree();
            b->rchild=createTree();
        }
        return b;
    }
     
    //先序遍历
    void preOrderTraverse(BitNode *root){
        if(root){
            printf("%c",root->data);
            preOrderTraverse(root->lchild);      
            preOrderTraverse(root->rchild);      
        }
    }
    
    //中序遍历
    void inOrderTraverse(BitNode *root){
        if(root){
            inOrderTraverse(root->lchild);
            printf("%c",root->data);
            inOrderTraverse(root->rchild);
        }
    }
    
    //后序遍历
    void lastOrderTraverse(BitNode *root){
        if(root){
            lastOrderTraverse(root->lchild);
            lastOrderTraverse(root->rchild);
            printf("%c",root->data);
        }
    }