非二叉树的创建与遍历

装载请注明来源chengyaogen.blog.chinaunix.net

 

二叉树的创建和遍历网上资料很多，非二叉树的创建和遍历很少有人研究，今天研究了非二叉树创建和遍历。

 

先来看看我们的小树吧:

 

怎么创建，怎么遍历，一个字晕!

总有解决问题的办法的，提供一种思路:

1(2(5,6),3(7,8),4(9))

1是根节点，2是根的第一个孩子，3,4是2的兄弟结点

同理2的第一个孩子结点是5,6是5的兄弟结点

最后就变成了下面图形:

 

 

我们把1(2(5,6),3(7,8),4(9))作为输入，然后构建上面的图:

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

#define MAX 3

//树的数据结构设计
typedef struct _tree_
{
    int data;
    struct _tree_ *fchild;//第一个孩子结点
    struct _tree_ *schild;//兄弟结点
}Tree;

//分配一个树结点
Tree *space_tnode(char ch)
{
    Tree *cureent;

    cureent = (Tree *)malloc(sizeof(Tree));
    cureent->data = ch - '0';
    cureent->fchild = cureent->schild = NULL;

    return cureent;
}

//创建树
Tree *create_tree(char *str)
{
    int level = 0;//层次，我们知道上面的树可以看成三层

    Tree *L[MAX],*current;//L[0]指向第一层，L[1]第二层，依次类推

    if(*str >= '0' && *str <= '9' && *(str + 1) == '(')
    {
        L[0] = space_tnode(*str);

    }else{

        printf("format error!\n");
        return NULL;
    }

    while(*str)
    {
        switch(*str)
        {
            //进入一层
            case '(':
                str ++;
                current = space_tnode(*str);
                //链接第一个孩子结点
                L[level]->fchild = current;
                L[++level] = current;
                break;

            //链接兄弟结点
            case ',':
                str ++;
                current = space_tnode(*str);
                L[level]->schild = current;
                L[level] = current;
                break;

            //退出一层
            case ')':
                level --;
                break;
        }

        str ++;
    }

    return L[0];
}


//以下是队列的设计和实现
typedef Tree *DataType;

typedef struct node
{
    DataType data;
    struct node *next;
}ListNode;

typedef struct
{
    struct node *front;
    struct node *rear;

}ListQueue;

ListQueue *create_empty_queue()
{
    ListNode *temp;
    ListQueue *qhead;

    temp = (ListNode *)malloc(sizeof(ListNode));
    temp->next = NULL;

    qhead = (ListQueue *)malloc(sizeof(ListQueue));
    qhead->front = qhead->rear = temp;

    return qhead;
}

int is_empty_queue(ListQueue *p)
{
    if(p->front == p->rear)
        return 1;
    else
        return 0;
}

int enter_queue(ListQueue *p,DataType data)
{
    ListNode *temp;

    temp = (ListNode *)malloc(sizeof(ListNode));
    temp->data = data;
    temp->next = NULL;

    p->rear->next = temp;
    p->rear = temp;

    return 0;
}

DataType delete_queue(ListQueue *p)
{
    ListNode *temp;
    //保存第一个结点
    temp = p->front;
    //移动指针
    p->front = temp->next;
    //删除第一个结点
    free(temp);
    temp = NULL;

    return p->front->data;
}


int main()
{
    Tree *TreeHead,*current;
    char buf[100];
    ListQueue *QueueHead;

    QueueHead = create_empty_queue();

    scanf("%s",buf);
    TreeHead = create_tree(buf);

         //遍历的思想是树的按层次遍历
    //头结点先入队
    enter_queue(QueueHead,TreeHead);
    while(!is_empty_queue(QueueHead))
    {
        //头结点出队
        current = delete_queue(QueueHead);
        printf("%d ",current->data);

        //孩子结点入队
        if((current = current->fchild) != NULL)
        {
            enter_queue(QueueHead,current);

            //孩子的所有兄弟结点入队
            while((current = current->schild) !=NULL)
            {
                enter_queue(QueueHead,current);
            }
        }
    }

    printf("\n");

    return 0;
}

树在遍历的过程，用队列使用层次进行遍历的，先将根节点入队，然后出队，然后把其第一个孩子和第一个孩子的所有兄弟接点入队，依次类推...