多叉树的后序遍历，先序遍历，及其释放操作 - vfdff的博客

作者在 2011-04-01 00:53:26 发布以下内容

/************************************************************************/
/* coder:huifeng00                                                      */
/* 时间：2010-5-12 下午 9点                                             */
/* 实现：多叉树的后序遍历，先序遍历，及其释放操作                       */
/* 语言：C       工具：VC++6.0                                          */
/************************************************************************/
#include <stdlib.h>
#include <memory.h>
#include <stdio.h>

#define MAXSIZE 5//这是多叉树最多可以的分支数
typedef struct _TREENODE
{
    int data;
    int cnChild;
    struct _TREENODE *parent;
    struct _TREENODE *child[MAXSIZE];
} TREENODE, *PTREENODE;

PTREENODE InsertNode(PTREENODE *ppNode,int data)//向一个多叉树节点插入一个孩子节点
{
    int cnChild = (*ppNode)->cnChild;
    PTREENODE temp = (PTREENODE)malloc(sizeof(TREENODE));
    temp->data = data;
    temp->cnChild =0;
    temp->parent = *ppNode;
    memset(temp->child,0,MAXSIZE);

    (*ppNode)->child[cnChild] = temp;
    (*ppNode)->cnChild++;
    return temp;
}

void PrintTree(PTREENODE root)//递归格式化先序打印多叉树
{
    static depth = 0;
    int i;
    if (root == NULL)
    {
        return;
    }
    for (i=0;i<depth;i++)
    {
        printf(" ");
    }
    printf("%d\n",root->data);
    for (i=0;i<root->cnChild;i++)
    {
        depth++;
        PrintTree((root->child)[i]);
        depth--;
    }
}

void PrintTreelast(PTREENODE root)//递归格式化后序打印多叉树
{
    static depth = 0;
    int i;
    if (root == NULL)
    {
        return;
    }

    for (i=0;i<root->cnChild;i++)
    {
        depth++;
        PrintTreelast((root->child)[i]);
        depth--;
    }
    for (i=0;i<depth;i++)
    {
        printf(" ");
    }
    printf("%d\n",root->data);
}
void destroyTree(PTREENODE root)//释放多叉树节点所占内存
{
    int i;
    if (root == NULL)
    {
        return;
    }
    for (i=0;i<root->cnChild;i++)
    {
        destroyTree((root->child)[i]);
    }
    free(root);
}

int main()
{
    PTREENODE root = (PTREENODE)malloc(sizeof(TREENODE));//根节点
    PTREENODE temp1,temp2;
    root->data = 1;
    root->cnChild =0;
    root->parent = NULL;
    memset(root->child,0,MAXSIZE);


    //对根节点插入2个孩子
    temp1 = InsertNode(&root,11);
    temp2 = InsertNode(&root,12);

    //对第一个孩子节点插入3个孩子节点
    InsertNode(&temp1,111);
    InsertNode(&temp1,112);
    InsertNode(&temp1,113);

    //对第二个孩子节点插入3个孩子节点
    InsertNode(&temp2,121);
    InsertNode(&temp2,122);
    InsertNode(&temp2,123);

    PrintTree(root);//先序打印多叉树
    printf("*****************\n");
    PrintTreelast(root);//后序打印多叉树
    destroyTree(root);//后序释放多叉树节点
    return 0;
}