树与二叉树相互转换 树的遍历 源代码

广义表与森林相互转换，森林与二叉树相互转换，二叉树与遍历序列（先序/中序）相互转换，森林先根遍历和后根遍历

#include 
#include 
#include 
#include 

using namespace std;
//存有孩子结点索引的单链表结点
typedef struct TreelinkNode
{
    int index;
    struct TreelinkNode *next;
} TreelinkNode*pTreelinkNode;
//孩子链表结点（树结点）
typedef struct TreeNode
{
    pTreelinkNode link;
    int data;
} TreeNode*pTreeNode;
//森林结点
typedef struct FTreeNode
{
    pTreeNode tree;
    struct FTreeNode *next;
} FTreeNode*pFTreeNode;
//森林链表的初始化操作
void InitFTree（pFTreeNode &fTree）
{
    fTree = （pFTreeNode）malloc（sizeof（FTreeNode））;
    fTree->next = NULL;
}
//森林链表的插入操作
void InsertFTree（pFTreeNode &fTreepTreeNode node）
{
    pFTreeNode t_node = fTree;
    pFTreeNode newnode  = （pFTreeNode）malloc（sizeof（FTreeNode））;

    while（t_node->next != NULL）
    {
        t_node = t_node->next;
    }

    newnode->tree = node;
    t_node->next = newnode;
    newnode->next = NULL;
}
//广义表建立树链表（孩子链表）
void GListToTree（pTreeNode &treeint ¤t_indexint parent_index）
{
    char ch;
    pTreelinkNode newnode;

    pTreelinkNode link = （pTreelinkNode）malloc（sizeof（TreelinkNode））;
    link->index = current_index;
    link->next = NULL;
    tree[parent_index].link = link;

    while（true）
    {
        scanf（“%c“&ch）;

        if（ch == ‘（‘）
        {
            parent_index = current_index;
            current_index ++;
            scanf（“%d“&tree[current_index].data）;
            tree[current_index].link = NULL;

            GListToTree（treecurrent_indexparent_index）;
        }
        else if（ch == ‘‘）
        {
            current_index ++;
            scanf（“%d“&tree[current_index].data）;
            tree[current_index].link = NULL;

            newnode = （pTreelinkNode）malloc（sizeof（TreelinkNode））;
            newnode->index = current_index;
            newnode->next = NULL;
            link->next = newnode;
            link = link->next;
        }
        else
        {
            return;
        }
    }
}
//广义表组建立森林链表
void GListToFTree（pFTreeNode &fTree）
{
    char ch;
    int current_indexparent_index;
    pTreeNode tree;
    scanf（“%c“&ch）;

    while（ch != ‘#‘）
    {
        current_index = -1;
        tree=（pTreeNode）malloc（50*sizeof（TreeNode））;

        current_index ++;
        scanf（“%d“&tree[current_index].data）;
        tree[current_index].link = NULL;

        scanf（“%c“&ch）;

        if（ch != ‘）‘）
        {
            parent_index = current_index;
            current_index ++;
            scanf（“%d“&tree[current_index].data）;
            tree[current_index].link = NULL;

            GListToTree（treecurrent_indexparent_index）;
            scanf（“%c“&ch）;
        }

        InsertFTree（fTreetree）;
        scanf（“%c“&ch）;
    }
}
//存储先序遍历序列记录的单链表结点
typedef struct linkNode
{
    int data;
    struct linkNode *next;
} linkNode*plinkNode;
//单链表的初始化
void InitlinkList（plinkNode &link）
{
    link=（plinkNode）ma

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

    I.A....     14183  2012-03-22 22:13  树与二叉树\main.cpp

    I..D...         0  2012-04-08 11:11  树与二叉树

----------- ---------  ---------- -----  ----

                14183                    2