C语言实现二叉树相关操作

Question

A、编写二叉树的创建函数，可以是排序二叉树的创建思路（见教材），或者以先序遍历为框架；
B、编写中序遍历函数；
C、编写先序遍历函数；
D、编写后序遍历函数；
E、编写排序二叉树的插入操作函数，实现在二叉排序树插入一个新元素；
F、编写函数求二叉树的深度。
编写主函数main，依次完成：创建一颗二叉树 (调用中序遍历函数，输出遍历结果 (调用先序遍历函数，输出遍历结果 (调用后序遍历函数，输出遍历结果 (调用排序二叉树插入函数，插入一个新元素 (再次调用中序遍历函数，输出插入新元素后的遍历结果 (调用求二叉树深度的函数，输出二叉树深度。

Answer 1

#include <stdlib.h>
#include <stdio.h>

typedef struct node
{ //树的结点
    int data;
    struct node *left;
    struct node *right;
} Node;

typedef struct
{ //树根
    Node *root;
} Tree;

void insert(Tree *tree, int value) //创建树
{
    Node *node = (Node *)malloc(sizeof(Node)); //创建一个节点
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    if (tree->root == NULL) //判断树是不是空树
    {
        tree->root = node;
    }
    else
    {                            //不是空树
        Node *temp = tree->root; //从树根开始
        while (temp != NULL)
        {

            if (value < temp->data) //小于就进左儿子
            {
                if (temp->left == NULL)
                {
                    temp->left = node;
                    return;
                }
                else
                { //继续判断
                    temp = temp->left;
                }
            }
            else
            { //否则进右儿子

                if (temp->right == NULL)
                {
                    temp->right = node;
                    return;
                }
                else
                { //继续判断
                    temp = temp->right;
                }
            }
        }
    }
    return;
}

//前序遍历
void preOrederTraverse(Node *node)
{
    if (node != NULL)
    {
        printf("%d ", node->data);
        preOrederTraverse(node->left);
        preOrederTraverse(node->right);
    }
}

void inorder(Node *node) //树的中序遍历
{
    if (node != NULL)
    {
        inorder(node->left);
        printf("%d ", node->data);
        inorder(node->right);
    }
}

//后序遍历
void postOrderTraverse(Node *node)
{
    if (node != NULL)
    {
        postOrderTraverse(node->left);
        postOrderTraverse(node->right);
        printf("%d ", node->data);
    }
}
int getDepth(Node *node)
{
    int deep = 0; //深度计数
    if (node != NULL)
    {                                                                //如果当前结点不为空
        int leftdeep = getDepth(node->left);                         //则先判断其左子树的深度
        int rightdeep = getDepth(node->right);                       //然后判断右子树的深度
        deep = leftdeep >= rightdeep ? leftdeep + 1 : rightdeep + 1; //二叉树的深度对应左右子树中最大的一个 再加上当前的深度1
    }
    return deep; //将深度值返回
}

int main()
{
    Tree tree;
    tree.root = NULL; //创建一个空树
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) //输入n个数并创建这个树
    {
        int temp;
        scanf("%d", &temp);
        insert(&tree, temp);
    }
    inorder(tree.root); //中序遍历
    printf("\n");
    preOrederTraverse(tree.root); //前序遍历
    printf("\n");
    postOrderTraverse(tree.root); //后序遍历
    printf("\n");
    insert(&tree, 10);
    inorder(tree.root); //中序遍历
    printf("\n");
    preOrederTraverse(tree.root); //前序遍历
    printf("\n");
    postOrderTraverse(tree.root); //后序遍历
    printf("\n");
    printf("%d", getDepth(tree.root));
    getchar();
    getchar();
    return 0;
}