二叉树二叉链表的构建遍历等操作（C语言）

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

/**
* 二叉树的链式存储——二叉链表 
*/

#define OK 1;
const int OVERFLOW = -2;

typedef int Status;
typedef char TElemType;
//二叉链表结构定义 
typedef struct BiNode{
    TElemType data;
    struct BiNode *lchild, *rchild;
} BiNode, *BiTree;


//由字符序列创建二叉树
Status CreateBiTree(BiTree *tree,TElemType data[],int *j,int len){
    if((*j)<=len-1){
        if(data[(*j)]==‘#‘){
            (*tree)=NULL;
            (*j)++;
        } else {
            (*tree)=(BiTree)malloc(sizeof(BiNode));
            if(!(*tree)) return OVERFLOW;
            (*tree)->data=data[(*j)];  //生成根结点 
            (*j)++;
            CreateBiTree(&((*tree)->lchild),data,j,len);  //构造左子树 
            CreateBiTree(&((*tree)->rchild),data,j,len);  //构造右子树
        }
    }
    return OK;
}

//二叉树的先序遍历（交换 Visit函数 和 遍历左右子树函数 的位置即得到中序遍历和后序遍历） 
Status PreOrderTraverse(BiTree tree){
    if(tree==NULL) return OK;  //空二叉树 
    Visit(tree);
    PreOrderTraverse(tree->lchild);  //递归遍历左子树 
    PreOrderTraverse(tree->rchild);  //递归遍历右子树 
} 
Status Visit(BiTree tree){
    printf("%c",tree->data);
    return OK;
}

//按先序遍历方式复制二叉树
void Copy(BiTree tree,BiTree *newTree){
    if(tree==NULL){
        (*newTree)=NULL;
    } else {
        //复制根结点 
        (*newTree)=(BiTree)malloc(sizeof(BiTree));
        (*newTree)->data=tree->data;
        //递归复制左右子树 
        Copy(tree->lchild,&((*newTree)->lchild));
        Copy(tree->rchild,&((*newTree)->rchild));
    }
} 


//计算二叉树深度
int Depth(BiTree tree){
    if(tree==NULL){
        return 0;
    } else {
        int lchildDepth=Depth(tree->lchild);
        int rchildDepth=Depth(tree->rchild);
        if(lchildDepth>rchildDepth){
            return lchildDepth+1;
        } else {
            return rchildDepth+1;
        }
    }
} 

//计算二叉树结点总数
int NodeCount(BiTree tree){
    if(tree==NULL){
        return 0;
    } else {
        return NodeCount(tree->lchild)+NodeCount(tree->rchild)+1;
    }
} 

//计算二叉树叶子结点数
int LeafCount(BiTree tree){
    if(tree==NULL){
        return 0;
    } else if(tree->lchild==NULL&&tree->rchild==NULL) {
        return 1;
    } else {
        return LeafCount(tree->lchild)+LeafCount(tree->rchild);
    }
} 

int main(void) {
    //待创建二叉树的结构
    /*
                A
              /
            B
          /          C      D
            /             E    F
                         G
    */ 
    
    //指向二叉树的指针 
    BiTree bitree1;
    
    //创建二叉树 待用数据 
    TElemType data1[]={‘A‘,‘B‘,‘C‘,‘#‘,‘#‘,‘D‘,‘E‘,‘#‘,‘G‘,‘#‘,‘#‘,‘F‘,‘#‘,‘#‘,‘#‘,};  //先序遍历序列 
    int len1=sizeof(data1)/sizeof(data1[0]);
    int* j1=(int*)malloc(sizeof(int));
    *j1=0;
    
    //按先序遍历序列创建二叉树 
    Status createBiTreeResult = CreateBiTree(&bitree1,data1,j1,len1);
    printf("二叉树创建结果：%d\n",createBiTreeResult);
    
    //测试 
    printf("\n手动测试");
    printf("\nA:%c\n",bitree1->data);  //A
    printf("B:%c\n",bitree1->lchild->data);  //B
    printf("C:%c\n",bitree1->lchild->lchild->data);  //C
    printf("D:%c\n",bitree1->lchild->rchild->data);  //D
    printf("E:%c\n",bitree1->lchild->rchild->lchild->data);  //E
    printf("G:%c\n",bitree1->lchild->rchild->lchild->rchild->data);  //G
    printf("F:%c\n",bitree1->lchild->rchild->rchild->data);  //F
    printf("手动测试结束\n\n");
    
    //先序遍历二叉树 
    Status preOrderTraverseResult = PreOrderTraverse(bitree1);
    printf("\n二叉树先序遍历结果：%d\n",preOrderTraverseResult);
    
    //复制二叉树
    printf("\n二叉树复制:\n");
    BiTree bitree2;  //将树bitree1复制到树bitree2 
    Copy(bitree1,&bitree2);
    PreOrderTraverse(bitree2);
    
    int depth = Depth(bitree2);
    printf("\n\n树深：%d\n",depth);
    
    int nodeCount = NodeCount(bitree2);
    printf("\n结点总数：%d\n",nodeCount);
    
    int leafCount = LeafCount(bitree2);
    printf("\n叶子结点数：%d\n",leafCount);
    
    printf("\nEND");
    return 0;
}