数据结构 树的遍历（递归遍历练习）

//树的遍历--练习
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct _TreeNode{
    //数据域
    char data;
    //指针域
    struct _TreeNode * leftchild;//左孩子指针
    struct _TreeNode * rightchild;//右孩子指针
}TreeNode, *TreeNodePointer;

//计算叶子节点的数目
void LeafCount(TreeNodePointer root,int *num){
    if (root!=NULL)
    {
        //判断是否是叶子节点
        if (root->leftchild == NULL&&root->rightchild==NULL)
        {
            (*num)++;
            //注意++的优先级
        }
        //遍历左子树
        LeafCount(root->leftchild, num);
        //遍历右子树
        LeafCount(root->rightchild, num);
    }
}

//计算树的深度
int Depth(TreeNodePointer root){
    int Depthleft = 0, Depthright = 0, Depthvalue = 0;
    if (root==NULL)
    {
        //叶子节点的深度是0
        return Depthvalue;
    }
    //获取左子树的深度
    Depthleft = Depth(root->leftchild);
    //获取右子树的深度
    Depthright = Depth(root->rightchild);
    //取左右两个子树的最大值 +1  因为根节点自己算一层
    Depthvalue = 1 + (Depthleft>Depthright ? Depthleft : Depthright);
    return Depthvalue;
}

//遍历树
void inOrder(TreeNodePointer root){
    if (root!=NULL)
    {
        //遍历左子树
        inOrder(root->leftchild);
        //打印根节点
        printf("%c", root->data);
        //遍历右子树
        inOrder(root->rightchild);
    }
}

//拷贝树
TreeNodePointer CopyTree(TreeNodePointer root){
    if (root==NULL)
    {
        return NULL;
    }
    //先拷贝根节点
    TreeNodePointer newroot = NULL, newleftnode = NULL, newrightnode = NULL;
    newroot = (TreeNodePointer)malloc(sizeof(TreeNode));
    memset(newroot, 0, sizeof(TreeNode));
    if (newroot==NULL)
    {
        printf("分配内存失败
");
        return NULL;
    }
    newroot->data = root->data;
    //拷贝左子树
    newleftnode = CopyTree(root->leftchild);
    //拷贝右子树
    newrightnode = CopyTree(root->rightchild);
    newroot->leftchild = newleftnode;
    newroot->rightchild = newrightnode;
    return newroot;
}

//销毁树---后序遍历比较合适,销毁了根节点就找不着子节点了
void DestroyTree(TreeNodePointer *root){
    //递归遍历树--并且销毁
    if (*root!=NULL)
    {
        //遍历左子树
        DestroyTree(&(*root)->leftchild);
        //遍历右子树
        DestroyTree(&(*root)->rightchild);
        //销毁根节点
        free(*root);
        *root = NULL;
    }
}

void Test2(){
    //定义结构体对象
    TreeNodePointer t1 = NULL, t2 = NULL, t3 = NULL, t4 = NULL, t5 = NULL;
    t1 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t1 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t1, 0, sizeof(TreeNode));
    t2 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t2 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t2, 0, sizeof(TreeNode));
    t3 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t3 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t3, 0, sizeof(TreeNode));
    t4 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t4 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t4, 0, sizeof(TreeNode));
    t5 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t5 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t5, 0, sizeof(TreeNode));
    //填充数据域
    t1->data = 'A';
    t2->data = 'B';
    t3->data = 'C';
    t4->data = 'D';
    t5->data = 'E';

    //建立树之间的关系
    t1->leftchild = t2;
    t1->rightchild = t3;

    t2->leftchild = t4;
    t2->rightchild = NULL;

    t3->leftchild = t5;
    t3->rightchild = NULL;

    // t5是t4的左孩子
    t4->leftchild = NULL;
    t4->rightchild = NULL;

    //t5没有孩子节点
    t5->leftchild = NULL;
    t5->rightchild = NULL;
    //获取叶子节点的数目
    {
        /*
        int numx = 0;
        LeafCount(t1, &numx);
        printf("叶子节点的数目是%d
", numx);
        */
    }
    //获取树的深度
    {
        //printf("树的深度是%d
", Depth(t1));
    }
    //树的拷贝
    {
        TreeNodePointer newtree = CopyTree(t1);
        //打印原来的树
        printf("打印原来的树
");
        inOrder(t1);
        printf("
");
        printf("打印拷贝的树
");
        inOrder(newtree);
        //销毁树
        DestroyTree(&newtree);
        printf("已经销毁了！
");
    }

END:
    if (t1 != NULL)
    {
        free(t1);
        t1 = NULL;
    }
    if (t2 != NULL)
    {
        free(t2);
        t2 = NULL;
    }
    if (t3 != NULL)
    {
        free(t3);
        t3 = NULL;
    }
    if (t4 != NULL)
    {
        free(t4);
        t4 = NULL;
    }
    if (t5 != NULL)
    {
        free(t5);
        t5 = NULL;
    }
}

void main(){
    Test2();
    printf("
");
    system("pause");
}