2 p15989156422 p15989156422 于 2016.02.16 00:24 提问

求助关于二叉树层次遍历

向各位前辈求助。。。。。 小弟研究二叉树层次遍历三天了,始终不能结合队列写出可执行的代码。。。。真心求教。。。。万分感谢。。。。。!!!!

void Printbylevel(BTree T)
{
BNode *tmp = T;
CircleQueue *q = malloc(sizeof(CircleQueue));
Init(q);
if(T == NULL)
{
return ;//根节点为空,返回-1
}
else
{
InQueue(q, tmp);//根节点入队
}
while(q->num)//队列不为空
{
OutQueue(q, tmp); //出队,把出队元素保存在tmp上
printf("%d", tmp->data); //输出出队元素
if(tmp->lchild) //左子树不为空
{
InQueue(q, tmp->lchild);//左子树入队
}
if(tmp->rchild) //右子树不为空
{
InQueue(q, tmp->rchild);//右子树入队
}
}
return 0;
}


这个是我写的关于层次遍历的函数,一结合和队列就出问题了
请问应该怎样设计队列结构,。。。。。。。。。。。。

如果方便的话希望能否贴出源码参考学习

6个回答

caozhy
caozhy   Ds   Rxr 2016.02.16 08:35
已采纳

我这个程序比较简陋,队列用数组模拟,没有考虑下溢的问题,不过不影响你理解大概思路,和在我之上的完善。

caozhy
caozhy 回复梁智扬: 不好意思,我的程序还有个bug,Node* queuedata[100];,应该是101,因为下标是100开始。
接近 2 年之前 回复
caozhy
caozhy 回复梁智扬: 不好意思,我的程序还有个bug,Node* queuedata[100];,应该是101,因为下标是100开始。
接近 2 年之前 回复
caozhy
caozhy 回复梁智扬: 不好意思,我的程序还有个bug,Node* queuedata[100];,应该是101,因为下标是100开始。
接近 2 年之前 回复
p15989156422
p15989156422 非常感谢,我看了这两种方法,终于解决了。现在我正在试着写非递归的实现,好像有点难~。~不过写出一种来信心大多了~~
接近 2 年之前 回复
caozhy
caozhy   Ds   Rxr 2016.02.16 08:33
 #include <stdio.h>

struct Node
{
    Node * left;
    Node * right;
    int value;
};

Node* queuedata[100];
int qfront = 100;
int qend = 100;

Node* dequeue()
{
    return queuedata[qfront--];
}

void enqueue(Node * n)
{
    queuedata[qend--] = n;
}

int queuelength()
{
    return qfront - qend;
}

void enumtree(Node node)
{
    enqueue(&node);
    while (queuelength() > 0)
    {
        Node * n = dequeue();
        printf("%d ", n->value);
        if (n->left != NULL)
            enqueue(n->left);
        if (n->right != NULL)
            enqueue(n->right);
    }
}

int main(int argc, char* argv[])
{
/*
            0
     1            2
 3       4     5
6 7    8     9  10
     11 12  
*/
    Node * node = new Node[13];
    for (int i = 0; i < 13; i++)
    {
        node[i].value = i;
        node[i].left = NULL;
        node[i].right = NULL;
    }
    node[8].left = &node[11];
    node[8].right = &node[12];
    node[3].left = &node[6];
    node[3].right = &node[7];
    node[4].left = &node[8];
    node[5].left = &node[9];
    node[5].right = &node[10];
    node[1].left = &node[3];
    node[1].right = &node[4];
    node[2].left = &node[5];
    node[0].left = &node[1];
    node[0].right = &node[2];
    enumtree(node[0]);
    return 0;
}
caozhy
caozhy   Ds   Rxr 2016.02.16 08:34

0 1 2 3 4 5 6 7 8 9 10 11 12 Press any key to continue

Mr_dsw
Mr_dsw   Ds   Rxr 2016.02.16 08:55

你可以参照这个博客看下,详细:http://blog.csdn.net/lalor/article/details/7626854

p15989156422
p15989156422 非常感谢,我看了这两种方法,终于解决了。。。。现在正在研究非递归方法实现,楼上的哥们因为速度快,所以不能采纳你的答案了,抱歉了。。。。
接近 2 年之前 回复
mengyin521
mengyin521   2016.02.21 00:07

我就不写代码了 给你讲下原理 你用的是 C++ 指针完成操作 我就简单说下指针的解决方案
BTree 类中 需要有 两个 本类的指针 指向 左节点(本类的另一个对象 指针指向) 和 右节点 (本类的另一个对象 指针指向)
最好用一个值来 记录 该实例 节点的 层级(父节点的值+1)
二叉树遍历可以分为 深度优先 和 广度优先 如果你懂人工智能的话 会知道 还有多优化算法 例如权重定位 模糊预判 定位
指针是个 危险的 东东。。。。建议遗弃 不过还是要学好
注意 安全释放

mengyin521
mengyin521   2016.02.21 00:13

忘了提醒你下 二叉树遍历 禁忌WHILE 循环 和 FOR循环 都是 递归 操作 。。。在内部写 递归算法

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!