链式二叉树

由于栈模拟递归还没学，所以各功能都是直接递归运行，感觉二叉树明显要比其他数据结构难，还是要打好基础。

#include<stdio.h>
#include<stdlib.h>
struct BTree{
    char data;//数据域
    struct BTree* lnode;//左节点指针
    struct BTree* rnode;//右节点指针
};//定义链树
 
BTree* createtree(){
    //测试输入样例:A B D G # # H # # # C E # I # # F # #
    char value;//新节点值
    scanf(" %c",&value);
    if(value!='#'){//输入#结束当前递归并返回上一层递归
        BTree* T=(BTree*)malloc(sizeof(BTree));//分配根节点内存
        T->data=value;//根节点赋值
        T->lnode=createtree();//递归创建左子节点
        T->rnode=createtree();//递归创建右子节点
        return T;
    }
    return NULL;
}//递归先序创建二叉树
 
void preorder(BTree* T){
    if(T==NULL)
        return;//空树或递归完成返回
    printf("%c ",T->data);
    preorder(T->lnode);//递归输出左子树
    preorder(T->rnode);//递归输出右子树
}//先序遍历
 
void midorder(BTree* T){
    if(T==NULL)
        return;//空树或递归完成返回
    midorder(T->lnode);//递归输出左子树
    printf("%c ",T->data);
    midorder(T->rnode);//递归输出右子树
}//中序遍历
 
void postorder(BTree* T){
    if(T==NULL)
        return;//空树或递归完成返回
    postorder(T->lnode);//递归输出左子树
    postorder(T->rnode);//递归输出右子树
    printf("%c ",T->data);
}//后序遍历
 
void seqorder(BTree* T){
  BTree* temp[100];   //创建pTreeNode指针类型的指针数组
  int in = 0;
  int out = 0;
  temp[in++] = T;  //先保存二叉树根节点
  while (in > out){
    if(temp[out]){
      printf("%c ",temp[out]->data);
      temp[in++] = temp[out]->lnode;
      temp[in++] = temp[out]->rnode;
    }
    out++;
  }
}//层序遍历
int max(int a,int b){
    if(a>b)
        return a;
    else
        return b;
}
 
BTree* searchnode(BTree* T,char x){
    //递归的结束条件:
    if (T==NULL)
        return NULL;
    if (T->data == x){
        printf("查询成功\n");
        return NULL;
    }
    //单边查找:先左后右
    if (searchnode(T->lnode, x))//如果左边为空则向右查找
        return searchnode(T->lnode,x); //不为空则向下递归查找
    else
        return searchnode(T->rnode,x);
}//查找节点
 
int searchsum(BTree* T){
    if(T==NULL)
        return 0;//空树或递归完成返回
    return searchsum(T->lnode)+searchsum(T->rnode)+1;
}//统计结点总个数
 
int searchlayer(BTree* T){
    if(T==NULL)
        return 0;
    int ldepth=searchlayer(T->lnode);
    int rdepth=searchlayer(T->rnode);
    return max(ldepth,rdepth)+1;
}//查询二叉树层数
 
BTree* cleartree(BTree* T){
    if(T){
        cleartree(T->lnode);
        cleartree(T->rnode);
        free(T);
    }
    return T;
}//清空二叉树
 
void destroytree(BTree* T){
    cleartree(T);
    T=NULL;
    printf("链表已销毁,程序自动结束运行\n");
    exit(0);
}//销毁二叉树
 
void treemenu(){
    printf("1.先序遍历输出二叉树\n");
    printf("2.中序遍历输出二叉树\n");
    printf("3.后序遍历输出二叉树\n");
    printf("4.层序遍历输出二叉树\n");
    printf("5.根据值查询节点\n");
    printf("6.统计节点个数\n");
    printf("7.统计二叉树层数\n");
    printf("8.清空二叉树\n");
    printf("9.销毁二叉树\n");
    printf("0.退出程序\n");
}//二叉树功能菜单
 
void endsystem(BTree* T){
    destroytree(T);
    exit(0);
}//结束程序
 
int main(){
    printf("请输入新结点的值(输入#为空节点):");
    BTree* T=createtree();//初始化创建栈
    int sort,flag=1;
    while(flag){
        treemenu();
        printf("请输入数字选择功能:");
        scanf("%d",&sort);
        switch(sort){
            case 1:{
                preorder(T);
                break;
            }
            case 2:{
                midorder(T);
                break;
            }
            case 3:{
                postorder(T);
                break;
            }
            case 4:{
                seqorder(T);
                break;
            }
            case 5:{
                char value;
                printf("请输入需查询的节点值:");
                scanf(" %c",&value);
                searchnode(T,value);
                break;
            }
            case 6:{
                printf("二叉树节点个数为:%d\n",searchsum(T));
                break;
            }
            case 7:{
                printf("二叉树最大深度为%d\n",searchlayer(T));
                break;
            }
            case 8:{
                cleartree(T);
                break;
            }
            case 9:{
                destroytree(T);
                break;
            }
            case 0:{
                endsystem(T);
                break;
            }
        }
        printf("\n");
    }
}

测试用例:A B D G # # H # # # C E # I # # F # #

图1