二叉树的建立、遍历、叶子节点计数、深度计算

二叉树的建立有三中方式：先序遍历建树，中序遍历建树，后序遍历建树

二叉树的遍历方式也有三种：先序遍历，中序遍历，后序遍历

另外还可以计算二叉树的深度，计算二叉树的叶子结点数

遍历倒是没有什么问题，但是我刚开始建树的时候总是出现问题；

先定义一个树节点，然后把这个树节点传进建树的函数中进行建树，这样的话建树的函数必须把树根的地址返回给建树之前定义的那个节点

总之就是：建树的函数必须能够把所建立的树的地址传回去(不管用什么传递方式);

下面粘贴两个代码（建树方式都是先序）;

sampleinput 

ABD*F***CE***

输出

先序遍历结果
ABDFCE
中序遍历结果
DFBAEC
后序遍历结果
FDBECA
树的深度为4
叶节点个数为2

代码一：

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

using namespace std;

struct Node
{
    char data;
    struct Node *l, *r;
};
int sum = 0;

struct Node *Creat(struct Node *p)
{
    char q;
    scanf("%c", &q);
    if(q == '*')
        p = NULL;
    else
    {
        p = (struct Node *)malloc(sizeof(struct Node));
        p->data = q;
        p->l = Creat(p->l);
        p->r = Creat(p->r);
    }
    return p;
}
int Xianxu(struct Node *p)
{
    if(p)
    {
        printf("%c", p->data);
        Xianxu(p->l);
        Xianxu(p->r);
    }
    return 0;
}
int Zhongxu(struct Node *p)
{
    if(p)
    {
        Zhongxu(p->l);
        printf("%c", p->data);
        Zhongxu(p->r);
    }
    return 0;
}
int Houxu(struct Node *p)
{
    if(p)
    {
        Houxu(p->l);
        Houxu(p->r);
        printf("%c", p->data);
    }
    return 0;
}
int Deep(struct Node *p)
{
    int c1, c2;
    if(!p)
        return 0;
    c1 = Deep(p->l);
    c2 = Deep(p->r);
    return c1 > c2 ? c1+1 : c2+1;
}
int Jiedian(struct Node *p)
{
    if(p)
    {
        Jiedian(p->l);
        Jiedian(p->r);
        if((p->l == NULL) && (p->r == NULL))
            sum++;
    }
    return sum;
}
int main()
{
    int sum;
    struct Node *head;
    head = (struct Node *)malloc(sizeof(struct Node));
    head = Creat(head);
    printf("先序遍历结果
");
    Xianxu(head);
    printf("
");

    printf("中序遍历结果
");
    Zhongxu(head);
    printf("
");

    printf("后序遍历结果
");
    Houxu(head);
    printf("
");

    printf("树的深度为%d
", Deep(head));
    sum = Jiedian(head);
    printf("叶节点个数为%d
", sum);
    return 0;
}

 代码二：

/*
    二叉树的二叉链表的存储方式
    注意二叉树也有三叉链表的存储方式，这种存储方式记录左右子树的根以及双亲节点的地址
    但是二叉树的三叉链表存储方式存储有n个节点的树会产生n+1个空的链域

    遍历是二叉树最基本的操作，对某个节点的改动可以通过遍历来实现，检索某个节点也可以通过遍历来实现
*/
#include <windows.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
int i = 0;
using namespace std;

typedef struct TreeNode //定义树上的每一个节点
{
    char data;
    struct TreeNode *lchild, *rchild;
}TreeNode;
int Preorder(struct TreeNode *p); //先序遍历
void Inorder(struct TreeNode *p); //中根遍历
void Posorder(struct TreeNode *p); //后根遍历
void CreatBiTree(TreeNode &p); // 建立二叉树

int Preorder(struct TreeNode *p)//先序遍历
{
    if(p)
    {
        cout << p->data;
        Preorder(p->lchild);
        Preorder(p->rchild);
    }
    return 0;
}
void Inorder(struct TreeNode *p) //中根遍历
{
    if(p)
    {
        Inorder(p->lchild);
        cout << p->data;
        Inorder(p->rchild);
    }
}
void Posorder(struct TreeNode *p)//后根遍历
{
    if(p)
    {
        Posorder(p->lchild);
        Posorder(p->rchild);
        cout << p->data;
    }
}
char Getonech(char ar[])
{
    return ar[i++];
}

TreeNode* CreatBiTree(TreeNode *p) //建立二叉树
{
    char ch;
    scanf("%c", &ch);
    if(ch != '*')
    {
        p = new TreeNode;
        p->data = ch;
        p->lchild = CreatBiTree(p->lchild);
        p->rchild = CreatBiTree(p->rchild);
    }
    else
        p = NULL;
    return p;
}
TreeNode* CreatBiTree(TreeNode *p, char ar[])
{
    char ch;
    ch = Getonech(ar);
    if(ch != '*')
    {
        p = new TreeNode;
        p->data = ch;
        p->lchild = CreatBiTree(p->lchild, ar);
        p->rchild = CreatBiTree(p->rchild, ar);
    }
    else
        p = NULL;
    return p;
}
int main()
{
    //第一种建树方式(用已经定义的字符串建树)
    char s[19] = "ABD*F***CE***";
    TreeNode *tree = new TreeNode;
    tree = CreatBiTree(tree, s);
    printf("先序遍历结果
");
    Preorder(tree);
    printf("
");
    printf("中序遍历结果
");
    Inorder(tree);
    printf("
");
    printf("后序遍历结果
");
    Posorder(tree);
    printf("
");

    //第二种建树方式（输入树）
    TreeNode *tree1 = new TreeNode;
    tree1 = CreatBiTree(tree1);
    printf("先序遍历结果
");
    Preorder(tree1);
    printf("
");
    system("pause");
    printf("中序遍历结果
");
    Inorder(tree1);
    system("pause");
    printf("
");
    printf("后序遍历结果
");
    Posorder(tree1);
    system("pause");
    printf("
");
    return 0;
}