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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
lintcode-二叉树的锯齿形层次遍历-71
给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行)  样例 给出一棵二叉树 {3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15 7 返回其锯齿形的层次遍历为: [ [3], [20,9], [15,7] ] /** * Definition
二叉树---层次遍历
就是按层次来 首先是根节点A入队列 然后是根节点的左B右C子树 根节点A出队列 左子B的左D右子树入队列然后B出队列 C的左右子树入对列C出队列 然后是D以此循环知道队列的头部和尾部重合队列空 输出完毕 思路并不难,但是在网上看的写的有点麻烦 照着一个ppt写了个简单一点的 可能不是最优的代码 但是很容易能理解这个思想和过程 #include #include #define LEN si
二叉树的层次遍历输出
从上到下层次遍历二叉树,并打印输出,使用的是队列,依次存储,输出的时候先把队首输出,同时去除队首元素。 上代码:package binaryTree;import java.util.LinkedList; import java.util.Queue;/** * 二叉树的层次遍历,使用队列 * * @author duola * */ public class cengcibianl
二叉树之层次遍历
下面是对层次遍历的一个实例,如果对二叉树不太了解请点击这里 任务要求:输入一棵二叉树,进行层次遍历,每个节点都按照从根节点到他的移动序列给出(L表示左,R表示右)。在输入中,每个节点的左右括号之间没有空格,相邻节点之间用一个空格隔开。每棵数的输入用一队空括号 () 表示结束(这对括号本身并不代表一个节点),如图所示。 (画的略丑) 注意:如果从根到某个叶节点的路径上有的
LintCode:二叉树的层次遍历 II
LintCode:二叉树的层次遍历 II""" Definition of TreeNode: class TreeNode: def __init__(self, val): self.val = val self.left, self.right = None, None """ class Solution: """ @param roo
如何实现二叉树层次遍历
完整 #include using namespace std; typedef struct biTreeNode { char data; struct biTreeNode *LChild; struct biTreeNode *RChild; }BiTreeNode; void Initiate_Tree(BiTreeNode **head) { (*head)=(BiTr
lintcode-二叉树的层次遍历-69
给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问) 您在真实的面试中是否遇到过这个题? 样例 给出一棵二叉树 {3,9,20,#,#,15,7},     3    / \   9  20     /  \    15   7 返回它的层次遍历为: [   [3],   [9,20],   [15,7] ] 挑战 只使
中序遍历,层次遍历构建二叉树
题目链接:点击打开链接 问题 C: 还原二叉树时间限制: 1 Sec内存限制: 128 MB提交: 324解决: 155提交状态题目描述给一棵二叉树的层序遍历序列和中序遍历序列,求这棵二叉树的先序遍历序列和后序遍历序列。输入每个输入文件中一组数据。第一行一个正整数N(1输出输出两行,每行N个正整数,分别代表二叉树的先序遍历序列和后序遍历序列。每行末尾不输出额外的空格。样例输入73 5 4 2 6
107. 二叉树的层次遍历 II
107. 二叉树的层次遍历 II class Solution { public: vector&amp;lt;vector&amp;lt;int&amp;gt;&amp;gt; levelOrderBottom(TreeNode* root) { vector&amp;lt;vector&amp;lt;int&amp;gt;&amp;gt; res; lOBhelp(res,root,0); reve...
LeetCode---二叉树的层次遍历(2)
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶节点所在层到根节点所在的层,逐层从左向右遍历)例如:给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其自自底向上的层次遍历为:[ [15,7], [9,20], [3] ]该题两种做法,一种就是递归,一种使用队列。/** * De...