Tree...

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。输出这棵二叉树的先序、中序和后序遍历序列。

二叉树结点的data是字符类型数据, 其中#表示空格字符。

/*************************************************************************
        > File Name: 先序创建二叉树.c
      > Author: dongmengyuan
      > Mail: 1322762504@qq.com
      > Created Time: 2016年11月20日 星期日 18时42分50秒
 ************************************************************************/

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

typedef char datatype;
typedef struct Node 
{
    datatype data;
    struct Node *lchild;
    struct Node *rchild;
}BiTNode, *BiTree;

//先序创建二叉树
void Creat(BiTree *root)
{
    char ch;
    ch = getchar();
    if(ch == '#') {
        *root = NULL;
    }
    else {
        *root = (BiTree)malloc(sizeof(BiTNode));
        (*root) -> data = ch;
        Creat(&((*root) -> lchild));
        Creat(&((*root) -> rchild));
    }
}

//先序遍历输出二叉树
void PreOrder(BiTree root) 
{
    if(root) {
        printf("%c",root->data);
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}

//中序遍历输出二叉树
void InOrder(BiTree root)
{
    if(root) {
        InOrder(root->lchild);
        printf("%c",root->data);
        InOrder(root->rchild);
    }

}

//后序遍历输出二叉树
void PostOrder(BiTree root)
{
    if(root) {
        PostOrder(root->lchild);
        PostOrder(root->rchild);
        printf("%c",root->data);
    }
}

int main()
{
    BiTree root;
    Creat(&root);
    PreOrder(root);
    printf("\n");
    InOrder(root);
    printf("\n");
    PostOrder(root);
    printf("\n");
    return 0;
}

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。分别统计二叉树中叶子结点、度为1的结点、度为2的结点的个数，并输出。

第一行依次输出叶子结点个数、度为1的结点个数、度为2的结点个数，以空格隔开。
第二行连续输出叶子结点，中间不间隔。

/*************************************************************************
        > File Name: 结点个数.c
      > Author: dongmengyuan
      > Mail: 1322762504@qq.com
      > Created Time: 2016年11月20日 星期日 22时34分26秒
 ************************************************************************/

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

typedef char datatype;
typedef struct Node
{
    datatype data;
    struct Node *lchild;
    struct Node *rchild;
}BiTNode, *BiTree;

//先序创建二叉树
BiTree creat()
{
    char ch;
    ch = getchar();
    if(ch == '#') {
        return NULL;
    }
    else {
        BiTree root = malloc(sizeof(BiTNode));
        root->data = ch;
        root -> lchild = creat();
        root -> rchild = creat();
        return root;
    }
}

int a = 0,b = 0,c = 0;
char s[10000];
int k = 0;

void printleaf(BiTree root)
{
    if(root) {
        if(root->lchild == NULL && root->rchild == NULL) {
            s[k++] = root->data;
            a++;
        }
        if((root->lchild == NULL && root->rchild != NULL) || (root->lchild != NULL && root->rchild == NULL) ) {
            b++;
        }
        if(root->lchild != NULL && root->rchild !=NULL) {
            c++;
        }
        printleaf(root->lchild);
        printleaf(root->rchild);
    }
}

void PreOrder(BiTree root)
{
    if(root) {
        printf("%c",root->data);
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }  
}

int main()
{
    BiTree root;
    root = creat();
    printleaf(root);
    printf("%d %d %d\n",a,b,c);
    for(int i = 0; i < k; i++)
    printf("%c",s[i]);
    return 0;
}

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。按先序遍历次序输出各结点的内容及相应的层次数，要求以二元组的形式输出，其所对应的输出结果为：（data,level）

data是二叉树结点数据域值，level是该结点所在的层次。
设根节点在第一层。
输出的元素间不用间隔，（）都是英文字符

/*************************************************************************
        > File Name: 输出结点及相应的层数.c
      > Author: dongmengyuan
      > Mail: 1322762504@qq.com
      > Created Time: 2016年11月22日 星期二 10时41分37秒
 ************************************************************************/

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

typedef char datatype;
typedef struct Node
{
    datatype data;
    struct Node *lchild;
    struct Node *rchild;
}BiTNode, *BiTree;

//先序创建二叉树
void creat(BiTree *root)
{
    char ch;
    ch = getchar();
    if(ch == '#') {
        *root = NULL;
    }
    else {
        *root = (BiTree) malloc (sizeof(BiTNode));
        (*root) -> data = ch;
        creat(&((*root)->lchild));
        creat(&((*root)->rchild));
    }
}

void preorder(BiTree root, int n)
{
    if(root) {
        printf("(%c,%d)",root->data,n);
        preorder(root->lchild,n+1);
        preorder(root->rchild,n+1);
    }
}

int main()
{
    int n;
    BiTree root;
    creat(&root);
    preorder(root,n+1);
    printf("\n");
    return 0;
}

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。输出从根结点到每个叶子结点的路径。

输出的元素间不用间隔，都是英文字符,每个路径均占一行。

/*************************************************************************
        > File Name: 输出路径.c
      > Author: dongmengyuan
      > Mail: 1322762504@qq.com
      > Created Time: 2016年11月22日 星期二 10时12分48秒
 ************************************************************************/

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

typedef char datatype;
typedef struct Node
{
    datatype data;
    struct Node *lchild;
    struct Node *rchild;
}BiTNode, *BiTree;

void creat(BiTree *root)
{
    char ch;
    ch = getchar();
    if(ch == '#') {
        *root = NULL;
    }
    else {
        *root = (BiTree) malloc (sizeof(BiTNode));
        (*root) -> data = ch;
        creat(&((*root)->lchild));
        creat(&((*root)->rchild));
    }
}

void outpath(BiTree root, char path[], int n)
{
    if(root->lchild == NULL && root->rchild == NULL) {
        printf("%c:",root->data);
        for(int i = 0; i < n; i++) {
            printf("%c",path[i]);
        }
        printf("\n");
    }
    else {
        path[n] = root->data;
        if(root->lchild != NULL) {
            outpath(root->lchild,path,n+1);
        }
        if(root->rchild != NULL) {
            outpath(root->rchild,path,n+1);
        }
    }
}

int main()
{
    char path[1000];
    int n = 0;
    BiTree root;
    creat(&root);
    outpath(root,path,n);
    return 0;
}

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。将这棵二叉树的左右子树进行交换，并输出交换后二叉树的先序、中序、后序遍历序列

/*************************************************************************
        > File Name: 交换左右子树.c
      > Author: dongmengyuan
      > Mail: 1322762504@qq.com
      > Created Time: 2016年11月22日 星期二 12时02分23秒
 ************************************************************************/

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

typedef char datatype;
typedef struct Node 
{
    datatype data;
    struct Node *lchild;
    struct Node *rchild;
}BiTNode, *BiTree;

void creat(BiTree *root)
{
    char ch;
    ch  = getchar();
    if(ch == '#') {
        *root = NULL;
    }
    else {
        *root = (BiTree) malloc (sizeof(BiTNode));
        (*root) -> data = ch;
        creat(&(*root) -> lchild);
        creat(&(*root) -> rchild);

    }
}

BiTree change(BiTree root)
{
    BiTree t;
    if(root == NULL || (root -> lchild == NULL && root -> rchild == NULL)) {
        return root;
    }
    t = root -> lchild;
    root->lchild = root->rchild;
    root->rchild = t;
    if(root -> lchild) {
        root -> lchild = change(root->lchild);
    }
    if(root -> rchild) {
        root -> rchild = change(root->rchild);
    }
    return root;
}

void preorder(BiTree root)
{
    if(root) {
        printf("%c",root->data);
        preorder(root->lchild);
        preorder(root->rchild);
    }
}

void inorder(BiTree root)
{
    if(root) {
        inorder(root->lchild);
        printf("%c",root->data);
        inorder(root->rchild);
    }
}

void postorder(BiTree root)
{
    if(root) {
        postorder(root->lchild);
        postorder(root->rchild);
        printf("%c",root->data);
    }
}

int main()
{
    BiTree root;
    creat(&root);
    change(root);
    preorder(root);
    printf("\n");
    inorder(root);
    printf("\n");
    postorder(root);
    printf("\n");
    return 0;
}