先序创建二叉树及三种遍历

77 阅读 0 评论 51 点赞

我是靠谱客的博主震动流沙，最近开发中收集的这篇文章主要介绍先序创建二叉树及三种遍历，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include<stdio.h>
#include<stdlib.h>
int max = 0;
struct node{
    int data;
    struct node *left;
    struct node *right;
};

struct node *create(struct node *newNode){//先序创建二叉树 
    char data;
    scanf("%c",&data);
    if(data == '#'){
        newNode = NULL;
    }else{
        newNode = (struct node *)malloc(sizeof(struct node));
        newNode->data = data;
        newNode->left = create(newNode->left);
        newNode->right = create(newNode->right);
    }
    return newNode;
} 

void PreOrderTraversal(struct node *tree){//先序遍历 
    if(tree){
        printf("%c",tree->data);
        PreOrderTraversal(tree->left);
        PreOrderTraversal(tree->right); 
    }
}

void InOrderTraversal(struct node *tree){//中序遍历 
    if(tree){
        InOrderTraversal(tree->left);
        printf("%c",tree->data);
        InOrderTraversal(tree->right); 
    }
}

void PostOrderTraversal(struct node *tree){//后序遍历 
    if(tree){
        PostOrderTraversal(tree->left);
        PostOrderTraversal(tree->right);
        printf("%c",tree->data); 
    }
}

void leaf(struct node *tree){//从左到右输出叶子结点 
    if(tree){
        if(tree->left==NULL && tree->right==NULL){
            printf("%c",tree->data); 
        } 
        leaf(tree->left);
        leaf(tree->right);  
    }
}

void deep(struct node *tree,int step){//树的深度 
    if(tree){
        if(step > max){
            max = step;
        }
        deep(tree->left,step+1);
        deep(tree->right,step+1);
    }
} 

int main(){
    struct node *tree = NULL;
    tree = create(tree);
    if(tree){
        PreOrderTraversal(tree);printf("n");
        InOrderTraversal(tree);printf("n");
        PostOrderTraversal(tree); printf("n");
        leaf(tree); printf("n");
        deep(tree,1);
        printf("%d",max);
    }else{
        printf("NULL"); 
    }
    return 0;
}