编辑代码

#include <stdio.h>
#include <malloc.h>

typedef struct TreeNode *BinTree;
struct TreeNode{
    int Data;
    BinTree Left;
    BinTree Right;
};

void preOrderTraveser(BinTree t);
BinTree createBinTree();
BinTree Insert(int X,BinTree BST);

BinTree Insert(int X,BinTree BST){
    //若原树为空,生成并返回一个结点的二叉搜索树
    if(!BST){
        BST = malloc(sizeof(struct TreeNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    //开始找要插入元素的位置
    else{
        if(X < BST->Data){
            /*插入之后返回根节点的地址,再把新的结点连接到根结点上
              当要插入当前结点的左或右子树时,则申请一个新结点,然后
              该递归函数返回该结点并把该结点赋给它的根结点
              递归插入左子树
            */
            BST->Left = Insert(X,BST->Left);
        }
        //递归插入右子树
        else if(X > BST->Data){
            /*如果不赋值,改为return,这时就变成了查找
            */
          BST->Right = Insert(X,BST->Right);
          //return Insert(X,BST->Right);
        }
        //else X已经存在,什么都不做
    }
    return BST;
}

//先序创建二叉树
BinTree createBinTree(){
    BinTree treeNode;
    int data;
    scanf("%d",&data);
    if(data){
        treeNode = (BinTree)malloc(sizeof(BinTree));
        treeNode->Data = data;
        treeNode->Left = createBinTree();
        treeNode->Right = createBinTree();
    }else{
        treeNode = NULL;
    }
    return treeNode;
}

void preOrderTraveser(BinTree t){
    if(t){
      printf("%d\n",t->Data);
      preOrderTraveser(t->Left);
      preOrderTraveser(t->Right);
    }else{
      return;
    } 
}

int main () {
    BinTree T = createBinTree();
    BinTree afterInsertTree;
    int X;
    printf("请输入要插入的值:\n");
    scanf("%d",&X);
    afterInsertTree = Insert(X,T);
    printf("插入之后的树为:\n"); 
    preOrderTraveser(afterInsertTree);
}