1 说明二叉树的层序遍历是面试中经常考虑的知识点，甚至要求当场写下实现过程。 笔者向腾讯和滴滴面试官询问了这个问题，腾讯面试官让他讲述了整个实现过程，本人信心满满地说，所以对具体的实现不太关心。 等到滴滴面试的时候，让我详细写下实现，发现真的做好了才明白原理，但是如果没有朝着正确的方向努力本来就相当麻烦，稍后我会说出本人的卡壳在哪里。
2 原理介绍层序遍历需要解决的问题可以很好地理解。 用二叉树从上到下，从左到右依次打印存储在各个节点上的数据。 下图：
根据层序遍历原则，打印顺序应该是A-B-C-D-E-F-G的顺序。
看完是不是感触非常深，这不就是队列数据结构最拿手的绝活吗，FIFO，先进先出！我从上到下，从左到右依次将每个数放入到队列中，然后按顺序依次打印就是想要的结果。
实现方案确实很容易思考，但具体实现很容易就卡在你排队的是什么。 本人面试通过只将各数据排队，访问a后，将b和c (左右孩子)排队，删除开头的数量(当前即a )，从而使b成为开头。 我想按顺序走，但是如果队列中还有数据，我就不知道从后面按什么顺序访问，也不知道二叉树什么时候停止。 因此，队列中的每个节点都必须存储二叉树指针，以便可以依次依赖指针left和right进行访问。
原理很简单，笔者觉得除了上述需要以外都很容易理解，下面就直接看c程序及程序中的注释吧。 33558 www.Sina.com/# include cstdio # includequeusingnamespacestd； /*二叉树结构，且带参数的构造函数* /结构二进制树{ int vec； 二进制树*左； 二进制树*光； 二进制树(int data ) :vec (数据)、左(nullptr )、右(nullptr ) }； /*队列是层序遍历*/voidprinttree (二进制树* arr [ ] ) { queueBinaryTree* rel； //定义队列，数据类型是二叉树指针，不能只包含int！ 否则无法遍历rel.push(ARR[0] )； while (！ rel.empty () { BinaryTree* front=rel.front； printf(%d(n )、front-vec )； rel.pop (； //删除第一个节点if (前左！=nullptr(//)判断开头的左节点是否为空，否则放入队列rel.push(front-left )的if(front-right！=nullptr(//确定第一个右节点是否为空，否则将其放入队列rel.push (前光线) ) }intmain(((/*二叉树(/二进制树) s_arr(6 s_ARR[0]=newbinarytree(0； s_ARR[1]=newbinarytree(1； s_ARR[2]=newbinarytree(2； s_ARR[3]=newbinarytree(3； s_ARR[4]=newbinarytree(4； s_ARR[5]=newbinarytree(5； s_arr[0]-left=s_arr[1]； //0 s_arr[0]-right=s_arr[2]； //1 2 s_arr[1]-left=s_arr[3]； //3 5 s_arr[3]-left=s_arr[4]； //4 s_arr[2]-right=s_arr[5]； //所以层序遍历的结果是0 1 2 3 5 4 /*层次遍历打印的所有节点* /打印树(s _ arr )； /*释放所有空间*/for(intI=0； i 6； I ) delete s_arr[i]； 返回0； }
个人学习记录，能力和时间有限，如有错误，请读者改正，谢谢。
请注明出处。 http://blog.csdn.net/FX 677588/article/details/74276513