当前位置：首页 > article >正文

10 先序遍历创建二叉树

article 2024/11/17 15:49:57

这个代码是使用手动输入的方式创建二叉树比较直观

#include "stdio.h"
#include "stdlib.h"

typedef int ElemType;
typedef struct node {
    ElemType data;
    struct node *lchild;
    struct node *rchild;
} Node;

Node *create_node(int value) {
    Node *node = (Node *) malloc(sizeof(Node));
    if (node == NULL) {
        exit(-1);
    }

    node->data = value;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

Node *create_tree() {
    int val = 0;
    printf("请输入创建树的数据 0为NULL");
    scanf("%d", &val);
    if (val == 0) {
        return NULL;
    }

    Node *node = create_node(val);
    printf("请输入%d的左子节点:", val);
    node->lchild = create_tree();
    printf("请输入%d的右子节点:", val);
    node->rchild = create_tree();
    return node;
}

// 先序遍历 根左右
void preOrder(Node *node) {
    if (node == NULL) {
        return;
    }
    printf("%d ", node->data);
    preOrder(node->lchild);
    preOrder(node->rchild);
}

void inOrder(Node *node) {
    if (node == NULL) {
        return;
    }

    inOrder(node->lchild);
    printf("%d ", node->data);
    inOrder(node->rchild);
}

void postOrder(Node *node) {
    if (node == NULL) {
        return;
    }

    postOrder(node->lchild);
    postOrder(node->rchild);
    printf("%d ", node->data);
}

//计算高度
int getHeight(Node *node) {
    if (node == NULL) {
        return 0;
    }

    int leftHeight = getHeight(node->lchild);
    int rightHeight = getHeight(node->rchild);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

int main() {
    Node *root = create_tree();
    preOrder(root);
    printf("\n");
    inOrder(root);
    printf("\n");
    postOrder(root);
    printf("\n");
    printf("高度为%d", getHeight(root));
    return 0;
}

运行效果