注册 登录
编程论坛 数据结构与算法

关于动态创建二叉树问题

cwl168 发布于 2012-12-20 22:04, 618 次点击

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
/*
  创建链表二叉树,这里大家要注意三点
  1,形参是个指向结构体变量的指针的指针,有关指针的指针的知识,
  同学们可参考c语言有关教材,在这里前往不要写错
  2,我们假定输入零表示该结点为空
  3. 我们是以先序的顺序来创建二叉树的但问题是无论以先序还是中序或者后序,
  我们都无法唯一确定该二叉树,解决的办法是“我们必须把那些节点为空的值
  也以先序或是中序又或者是后序的顺序来输入,这样就可以唯一确定该二叉树了”
*/
//动态造二叉树

typedef struct BiTNode
{
    int data;
    struct BiTNode * lchild,* rchild;
}BiTNode,*BiTree;


void CreateBiTree(BiTree *t);
void PreTraverseBTree(BiTree *t);

void CreateBiTree(BiTree *t)
{
    int temp;
    scanf("%d",&temp);
    if(temp)     //我们假定输入的结点值不能为0,即0表示空
    {//如果temp非零的话,我们为其分配储存空间
        (*t)=(BiTree)malloc(sizeof(BiTNode));
        if(!(*t))//若分配失败!
        {
            exit(-1);
        }
        (*t)->data=temp;
        CreateBiTree(&((*t)->lchild));  //递归创建左子树
        CreateBiTree(&((*t)->rchild));  //递归创建右子树
    }
    else
        (*t)=NULL;
}

void PreTraverseBTree(BiTree *t )//先序遍历函数
{
    if(NULL!= (*t))
    {
        printf("%c\n",(*t)->data);

        if(NULL!= ((*t)->lchild))
        {
            PreTraverseBTree(&((*t)->lchild));
        }
        if(NULL != ((*t)->rchild))
        {
            PreTraverseBTree(&((*t)->rchild));
        }
    }
}

int main(void)
{
    BiTree t;
    CreateBiTree(&t);
    PreTraverseBTree(&t);
    return 0;
}

这段程序运行成功应该怎么输入呢?
3 回复
#2
crystall2012-12-22 11:37
程序代码:
#include <stdlib.h>
#include <stdio.h>

struct BiTNode
{
    int data;
    struct BiTNode * lchild,* rchild;
};

struct BiTree
{
    //树的根结点
    BiTNode* pRoot;
};


void CreateBiTree(BiTree *t);
void PreTraverseBTree(BiTNode *pCurNode);

/*
void CreateBiTree(BiTree *t)
{
    int temp;
    scanf("%d",&temp);
    if(temp)     //我们假定输入的结点值不能为0,即0表示空
    {//如果temp非零的话,我们为其分配储存空间
        (*t)=(BiTree)malloc(sizeof(BiTNode));
        if(!(*t))//若分配失败!
        {
            exit(-1);
        }
        (*t)->data=temp;
        CreateBiTree(&((*t)->lchild));  //递归创建左子树
        CreateBiTree(&((*t)->rchild));  //递归创建右子树
    }
    else
        (*t)=NULL;
}
*/

void InitTree(BiTree *t)
{
    t->pRoot = NULL;
}

void CreateBiTree(BiTree *t)
{
    int temp = 0;
    BiTNode* pNewNode = NULL;
    BiTNode* pCurNode = NULL;

    while(true)
    {
        scanf("%d",&temp);


        if(temp == 0)
        {
            return;
        }
      
        //新结点
        pNewNode = (BiTNode*)malloc(sizeof(BiTNode));
        pNewNode->data = temp;
      
        //根节点为NULL
        if(t->pRoot == NULL)
        {
            t->pRoot = pNewNode;
            t->pRoot->lchild = t->pRoot->rchild = NULL;
            continue;
        }

        pCurNode = t->pRoot;

        //temp >= 当前数据 添加在右边
        if(temp >= pCurNode->data)
        {
            while(pCurNode)
            {
                if(pCurNode->rchild != NULL)
                {
                    pCurNode = pCurNode->rchild;
                }
                else
                {
                    pCurNode->rchild = pNewNode;
                    pCurNode->rchild->lchild = pCurNode->rchild->rchild = NULL;
                    break;
                }
            }
        }
        else
        {
            //temp < 当前数据 添加在左边
            while(pCurNode)
            {
                if(pCurNode->lchild != NULL)
                {
                    pCurNode = pCurNode->lchild;
                }
                else
                {
                    pCurNode->lchild = pNewNode;
                    pCurNode->lchild->lchild = pCurNode->lchild->rchild = NULL;
                    break;
                }                       
            }
        }
    }
}

void PreTraverseBTree(BiTree * Tree)
{
    PreTraverseBTree(Tree->pRoot);
}

void PreTraverseBTree(BiTNode *pCurNode)//先序遍历函数
{
    if (pCurNode == NULL)
    {
        return;
    }

    printf("%d\r\n", pCurNode->data);
    PreTraverseBTree(pCurNode->lchild);
    PreTraverseBTree(pCurNode->rchild);
    /*
    if(NULL != t)
    {
        printf("%c\n",(*t)->data);

        if(NULL!= ((*t)->lchild))
        {
            PreTraverseBTree(&((*t)->lchild));
        }
        if(NULL != ((*t)->rchild))
        {
            PreTraverseBTree(&((*t)->rchild));
        }
    }
*/
}

int main(void)
{
    BiTree MyTree;

    InitTree(&MyTree);

    CreateBiTree(&MyTree);

    PreTraverseBTree(&MyTree);

    return 0;
}
#3
cwl1682012-12-24 18:43
有问题
#4
crystall2012-12-25 12:06
回复 3楼 cwl168
什么问题?
1