| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 495 人关注过本帖
标题:求助。。层序遍历二叉树。。。
只看楼主 加入收藏
lllb123
Rank: 1
来 自:ustc
等 级:新手上路
帖 子:3
专家分:0
注 册:2014-10-15
收藏
 问题点数:0 回复次数:3 
求助。。层序遍历二叉树。。。
#include <stdlib.h>
#include <stdio.h>
#include<string.h>
#define size 100
#define N  15
typedef int DataType;        //二叉树的节点结构
typedef struct BiTNode
{
    DataType data;
    struct BiTNode *parent;
    struct BiTNode *lChild;
    struct BiTNode *rChild;
}BiTNode, *BiTree;

//返回二叉树的最小节点,空树返回NULL
BiTNode *minImum(BiTree *biTree)
{
    BiTNode *curNode = *biTree;
    while (curNode != NULL && curNode->lChild != NULL)
    {
        curNode = curNode->lChild;
    }
    return curNode;
}
//返回二叉树的最大节点,空树返回NULL
BiTNode *maxImum(BiTree *biTree)
{
    BiTNode *curNode = *biTree;
    while (curNode != NULL && curNode->rChild != NULL)
    {
        curNode = curNode->rChild;
    }
    return curNode;
}
//插入节点
void insertNode(BiTree *biTree, DataType data)
{
    //创建节点
    BiTNode *targetNode;
    targetNode = (BiTNode *)malloc(sizeof(BiTNode));
    //没有足够内存
    if (targetNode == NULL) return;
    if (data == 0) return;
    targetNode->data = data;
    targetNode->parent = NULL;
    targetNode->lChild = NULL;
    targetNode->rChild = NULL;
    BiTNode *p, *y;
    p = *biTree;
    y = NULL;
    while (p != NULL )
    {
        y = p;
        if (targetNode->data < p->data)
        {
            p = p->lChild;
        }
        else
        {
            p = p->rChild;
        }
    }
    //空树,将新节点置为树根
    if (y == NULL)
    {
        *biTree = targetNode;
    }
    else
    {
        if (targetNode->data < y->data)
        {
            y->lChild = targetNode;
        }
        else
        {
            y->rChild = targetNode;
        }
    }
    targetNode->parent = y;
}

//打印一个结点
void printNode(BiTNode *node)
{
    printf("%d ", node->data);
}


//队列节点结构
typedef struct queue
{
    BiTree *base;
    int front;
    int rear;
}queue;
//初始化队列
void QueueStart(queue &Q)
{
    Q.base=(BiTree*)malloc(size*sizeof(BiTree));
    if (!Q.base) return;
    Q.front=0;
    Q.rear=0;
}
//入队
void QueueInt(queue &Q,BiTree &p)
{
    if ((Q.rear+1)%size==Q.front) return;
    Q.base[Q.rear]=p;
    Q.rear=(Q.rear+1)%size;
}
//出队
void QueueOut(queue &Q,BiTree &p)
{
    printf("%d ",p->data);
    if (Q.rear==Q.front)  return;
    p=Q.base[Q.front];
    Q.front=(Q.front+1)%size;
}
//层序遍历
void levelTraversal(BiTree &T)
{
    queue S;
    BiTree p;
    p=T;
    QueueStart(S);
    if (p)     QueueInt(S,p);
    while (S.rear!=S.front)
    {
        QueueOut(S,p);
        if (p->lChild)
            QueueInt(S,p->lChild);
        if (p->rChild)
            QueueInt(S,p->rChild);
    }
}

int main()
{
    BiTNode *root;
    DataType k;
    int i;
    root = NULL;
    int data[N] = {5,3,1,0,0,4,0,0,7,6,0,0,8,0,0};
    for (i = 0; i < N; i++)
    {
        insertNode(&root, data[i]);
    }
    printf("层序遍历:");
    levelTraversal(root);
    printf("\n");
    printf("最小值:");
    printNode(minImum(&root));
    printf("\n最大值:");
    printNode(maxImum(&root));
    printf("\n插入节点值:%d",k=9);
    insertNode(&root,k);
    printf("插入后层序遍历:");
    levelTraversal(root);
    printf("\n");
}
搜索更多相关主题的帖子: include parent 二叉树 
2014-11-05 19:18
lllb123
Rank: 1
来 自:ustc
等 级:新手上路
帖 子:3
专家分:0
注 册:2014-10-15
收藏
得分:0 
自己写的。。二叉搜索树建立没有问题。。问题出在层序遍历上。。。上机实验的时候自己看了半天,给助教调了半个小时也没弄出来。。实在不知道问题出在哪。。来论坛求助大神。。
2014-11-05 19:20
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
程序代码:
//出队
void QueueOut(queue &Q, BiTree &p) {
    //printf("%d ", p->data);
    if (Q.rear == Q.front)
        return;
    p = Q.base[Q.front];
    printf("%d ", p->data);
    Q.front = (Q.front + 1) % size;
}


//不建议在这里写printf


[fly]存在即是合理[/fly]
2014-11-05 20:47
lllb123
Rank: 1
来 自:ustc
等 级:新手上路
帖 子:3
专家分:0
注 册:2014-10-15
收藏
得分:0 
回复 3 楼 azzbcc
解决了,谢谢啦。。我自己好好想想
2014-11-08 16:52
快速回复:求助。。层序遍历二叉树。。。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024828 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved