二叉树的算法

1.编一C程序，它能根据输入的字符（字母或*）序列来构造一棵二叉树，并能输出该二叉树后序和中序序列，
并计算出该二叉树度数为2的节点个数。输入是该二叉树经扩充后的结点前序遍历序列，扩充方法是：
对无左孩子的结点，增加一个标记为的做孩子结点：对无右孩子的结点，增加一个标记为的右孩子结点。
例如，若要构造的二叉树为AB*D**CE****

#include<stdio.h>
#include<stdlib.h>
int num,nun=0;
typedef char datatype;
typedef struct node
{//结点
    datatype data;
    struct node *lchild,*rchild;
}BinTNode;

typedef BinTNode *BinTree;

//前序遍历
void InorderBefore(BinTree T){
    if(T){
        char a = T ->data;
        printf("%c",T->data);
        InorderBefore(T->lchild);
        InorderBefore(T->rchild);
    }
}

//中序遍历
void InorderMid(BinTree T){
    if(T){
        char a = T->data;
        InorderMid(T->lchild);
        printf("%c",T->data);
        InorderMid(T->rchild);
    }
}

//后序遍历
void InorderAfter(BinTree T){
    if(T){
        char a = T->data;
        InorderAfter(T->lchild);
        InorderAfter(T->rchild);
        printf("%c",T->data);
    }
}

//构建二叉树
void CreateBinTree(BinTree *T){
    char ch;
    scanf("%c", &ch);
    if(ch=='*'){
        *T = NULL;
    }else{
        *T =(BinTNode *)malloc(sizeof(BinTNode));//生成结点
        if(!*T)
             exit(-1);
        (*T)->data = ch;
        CreateBinTree(&(*T)->lchild);//构造左子树
        CreateBinTree(&(*T)->rchild);//构造右子树
    }
}


//二叉树度数为2的结点个数
void Degree2Num(BinTree T){
    if(T == NULL){
        return;
    }else{
        if(T->lchild!=NULL && T->rchild!=NULL){
            num++;
        }
        Degree2Num(T->lchild);
        Degree2Num(T->rchild);
    }
}

//树的深度
int deepTree(BinTree T){
    int deepLchild,deeprchild;
    if(T==NULL){
        return 0;
    }else{
        deepLchild = deepTree(T->lchild);
        deeprchild = deepTree(T->rchild);
    }
    return deepLchild>deeprchild?deepLchild+1:deeprchild+1;
}

void main(){
    BinTree T;
    printf("请输入二叉树前序遍历:");
    CreateBinTree(&T);
    printf("中序遍历:");
    InorderMid(T);
    printf("\n后序遍历:");
    InorderAfter(T);
    printf("\n前序遍历:");
    InorderBefore(T);
    Degree2Num(T);
    printf("\n该二叉树度数为2的结点个数为%d\n",num);
    nun = deepTree(T);
    printf("该二叉树深度为%d\n",nun);
}

2.编一C程序，它能根据输入的二叉树前序和中序序列来构造该二叉树，并能输出该二叉树的后续序列和该二叉树树度为2的结点个数。
前序：a b c
中序：b a c

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

#define N 100
typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int num=0;
//先序遍历
void preOrder(BiTNode *root){
    if(root==NULL){
        return;
    }else{
        printf("%c ",root->data);
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
}
//中序遍历
void midOrder(BiTNode *root){
    if(root==NULL){
        return;
    }else{
        midOrder(root->lchild);
        printf("%c ",root->data);
        midOrder(root->rchild);
    }
}
//先序遍历
void rearOrder(BiTNode *root){
    if(root==NULL){
        return;
    }else{
        rearOrder(root->lchild);
        rearOrder(root->rchild);
        printf("%c ",root->data);
    }
}

//根据先序遍历和中序遍历创建二叉树
BiTNode* createBiTree(char *pre,char *in,int n){

    int i=0;
    int n1=0,n2=0;
    int m1=0,m2=0;
    BiTNode *node=NULL;
    char lpre[N],rpre[N];
    char lin[N],rin[N];
    if(n==0){
        return NULL;
    }
    node = (BiTNode *)malloc(sizeof(BiTNode));
    if(node==NULL){
        return NULL;
    }
    memset(node,0,sizeof(BiTNode));
    //先序序列的第一个元素必为根节点
    node->data=pre[0];
    //根据根节点将中序序列分为左子树和右子树
    for(i=0;i<n;i++){
        if((i<=n1)&&(in[i]!=pre[0])){
            lin[n1++]=in[i];
        }else if(in[i]!=pre[0]){
            rin[n2++]=in[i];
        }
    }
    //根据数的先序序列的长度等于中序序列的长度
    //且先序遍历是先左子树后再右子树。无论先序还是中序 左子树和右子树的长度都是固定的
    //注意 从i=1开始 因为先序遍历的第一个是根
    for(i=1;i<n;i++){
        if(i<(n1+1)){//n1代表了左子树的长度
            lpre[m1++]=pre[i];
        }else{
            rpre[m2++]=pre[i];
        }
    }
    node->lchild = createBiTree(lpre,lin,n1);
    node->rchild = createBiTree(rpre,rin,n2);
    return node;
}

//度为2的节点个数
void Degree2Num(BiTree T){
    if(T==NULL){
        return;
    }else{
        if(T->lchild!=NULL&&T->rchild!=NULL){//如果当千层大于num就交换
            num++;
        }
        Degree2Num(T->lchild);
        Degree2Num(T->rchild);
    }
}


int main(){

    char preNode[N];
    char inNode[N];
    int n=0;
    char ch;
    BiTNode *root = NULL;
    printf("请输入先序序列\n");
    while((ch=getchar()) && ch!='\n'){
        preNode[n++] = ch;
    }
    printf("请输入中序序列\n");
    n=0;
    while((ch=getchar())&& ch!='\n'){
        inNode[n++] = ch;
    }
    root = createBiTree(preNode,inNode,n);

    printf("先序序列\n");
    preOrder(root);
    printf("\n中序序列\n");
    midOrder(root);
    printf("\n后序序列\n");
    rearOrder(root);
    printf("\n");
    system("pause");
    Degree2Num(root);
    printf("\n该二叉树度数为2的结点个数为%d",num);
    printf("\n");
    return 0;
}

3.构造一个二叉排序树输出它的前序序列和中序序列,深度。

#include<stdio.h>
#include<stdlib.h>
#define END -9999
int array[100],n;
int deep=0;
typedef struct node{
    char data;
    struct node *lchild,*rchild;
}BinTNode,*BinTree;

//前序遍历
void preTree(BinTree T){
    if(T==NULL){
        return;
    }else{
        printf("%c ",T->data);
        preTree(T->lchild);
        preTree(T->rchild);
    }
}

//中序遍历
void midTree(BinTree T){
    if(T==NULL){
        return;
    }else{
        midTree(T->lchild);
        printf("%c ",T->data);
        midTree(T->rchild);
    }
}

//后序遍历
void rearTree(BinTree T){
    if(T==NULL){
        return;
    }else{
        rearTree(T->lchild);
        rearTree(T->rchild);
        printf("%c ",T->data);
    }
}
//树的深度
int deepTree(BinTree T){
    int deepLchild,deeprchild;
    if(T==NULL){
        return 0;
    }else{
        deepLchild = deepTree(T->lchild);
        deeprchild = deepTree(T->rchild);
    }
    return deepLchild>deeprchild?deepLchild+1:deeprchild+1;
}

//二叉排序树插入
int treeInsert(BinTree &T,int k){
    if(T==NULL){
        BinTree T = new BinTNode;
        T->data = k;
        T->lchild = NULL;
        T->rchild = NULL;
        return 1;
    }else if(k == T->data){
        return 0;
    }else if(k < T->data){
        return treeInsert(T->lchild,k);
    }else{
        return treeInsert(T->rchild,k);
    }
}

//创建二叉树
void createTree(BinTree &T,int array[]){
    int n;
    T=NULL;
    n = sizeof(array)-1;
    for(int i=0;i<n;i++){
        treeInsert(T,array[i]);
    }
}

int main(){
    int x;
    BinTree T = NULL;
    printf("请输入一个树:\n");
    for(n=0;scanf("%d",&x) && x!=END;array[n++]=x){}
    createTree(T,array);
    printf("前序遍历:\n");
    preTree(T);
    printf("中序遍历:\n");
    midTree(T);
    deep = deepTree(T);
    printf("树的深度:%d\n",deep);
    return 0;
}