记一次Tree的遍历

统计利用先序遍历创建的二叉树的深度

利用先序递归遍历算法创建二叉树并计算该二叉树的深度。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树的深度（使用二叉树的后序遍历算法）。需要注意输入数据序列中的"#"字符和非"#"字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入为先序遍历二叉树结点序列。

输出

对应的二叉树的深度。

样例输入

A## 
ABC#### 
AB##C## 
ABCD###E#F##G## 
A##B##

样例输出

1 
3
2 
4
1

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

typedef struct BiTree
{
    char data;
    struct BiTree *lchild,*rchild;
}Tree;
int pos = 0;
BiTree * Create()             //我喜欢上了这种树的生成方式，以递归的方式。
{                             //递归真是一种神奇的东西。在计算机的世界里，递归是那么的美妙。
    char ch;
    Tree *T; 
    scanf("%c",&ch);
    if (ch == '#') T = NULL;
    else
    {
        T = (Tree *)malloc(sizeof(Tree));
        T -> data = ch;
        T -> lchild = Create();            //看不透哦，只能先死记了。渴望这时候出来个大佬给我讲讲。
        T -> rchild = Create();            //十分好奇这种函数
    }
    return T;
}
int Deep(BiTree * T)
{
    if (T != NULL)            //在T!= NULL，与单链表有些类似。不过在单链表中是p ->next != NULL
    {
        int sum1 = 0,sum2 = 0;
        sum1 = Deep(T->lchild);        //神递归，创这个方法的数学不知道有多好。
        sum2 = Deep(T->rchild);        //加油学好数学，这里的Deep是存在值的
        if (sum1 > sum2) return sum1+1;
        else return sum2+1;
    }
}

int main()
{
    Tree * T;
    T = Create();
    int t = 0;
    t = Deep(T);
    printf("%d",t);
}

统计利用先序遍历创建的二叉树的度为1的结点个数

利用先序递归遍历算法创建二叉树并计算该二叉树度为1结点的个数。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树度为1的结点个数。需要注意输入数据序列中的"#"字符和非"#"字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入为接受键盘输入的由大写英文字符和"#"字符构成的一个字符串（用于创建对应的二叉树）。

输出

每个用例用一行输出该用例对应的二叉树度为1的结点个数。

样例输入

# 
A## 
ABC#### 
AB##C## 
ABCD###EF##G### 
A##B## 
#A 

样例输出

0 
0 
2 
0 
2 
0 
0

//自己按上面的方法将原来自己的码改了
//没办法，上面的代码太TM有个性了
#include <stdio.h>
#include <stdlib.h>

typedef struct BiTree 
{
    int data;
    struct BiTree * lchild,* rchild;
}Tree;

BiTree * Create()
{
    char ch;
    Tree * T;
    scanf("%c",&ch);
    if (ch == '#') T = NULL;
    else
    {
        T = (Tree *)malloc(sizeof(Tree));
        T -> data = ch;
        T -> lchild = Create();
        T -> rchild = Create();
    }
    return T;
}

int s = 0;
int num(BiTree * T)
{
    if (T != NULL)
    {
        if ((T -> lchild != NULL && T -> rchild == NULL) || T -> lchild != NULL || T -> rchild != NULL)
        {
            s ++;
        }
        num(T -> lchild);
        num(T -> rchild);
        return s;
    }
}

int main()
{
    Tree * T;
    T = Create();
    int t;
    t = num(T);
    printf("%d",t);
    return 0;
}

统计利用先序遍历创建的二叉树的宽度

利用先序递归遍历算法创建二叉树并计算该二叉树的宽度。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树的宽度（是指二叉树每层节点数的最大值）。需要注意输入数据序列中"#"字符和非"#"字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入为接受键盘输入的由大写英文字符和"#"字符构成的一个字符串（用于创建对应的二叉树）。

输出

输出该用例对应的二叉树的宽度。

样例输入

A## 
ABC#### 
AB##C## 
ABCD###EF##G### 
A##B## 

样例输出

1 
1 
2
3 
1 

#include <stdio.h>
#include <stdlib.h>
int a[100] = {0};
int i = 0;
struct tree
{
    char data;
    struct tree * lchild,* rchild; 
};

tree * create()
{
    i ++;
    tree * T;
    char ch;
    scanf("%c",&ch);
    if (ch == '#') T = NULL;
    else
    {
        T = (tree *)malloc(sizeof(tree));
        T -> data = ch;
        T -> lchild = create();
        if (T -> lchild != NULL)
        {
            a[i] ++;
        }
        i --;
        T -> rchild = create();
        if (T -> rchild != NULL)
        {
            a[i] ++;
        }
        i --;
    }
    return T;
}

int main()
{
    tree * T;
    T = create();
    int biaoji;
    a[0] = 1;
    biaoji = 0;
    for (i = 0;i < 100;i ++)
    {
        if (a[biaoji] < a[i])
        {
            biaoji = i;
        }
    }
    printf("%d",a[biaoji]);
    return 0;
}