按层换行打印二叉树-创新互联
题目描述: 二叉树,按层打印,并且每层换行
成都创新互联公司专注于光泽企业网站建设,自适应网站建设,商城网站建设。光泽网站建设公司,为光泽等地区提供建站服务。全流程按需定制开发,专业设计,全程项目跟踪,成都创新互联公司专业和态度为您提供的服务分析: 我们知道,二叉树的层序遍历需要借助队列来实现,每取出一个节点打印,并将该节点的左右孩子放入队列中,依此反复,直到队列为空时,也就完成了二叉树的按层打印。
基本过程如图所示:
但是,关键是怎么换行?
分析:要换行则需要知道什么时候换行,由二叉树我们可以分析,我们需要知道每一层最右边的节点,每次打印完这个节点的值后,再打印一个换行即可。于是我们这样做:
定义两个变量,last 和 nlast
last : 表示正在打印的当前行的最右节点
nlast : 表示下一行的最右节点
步骤:
开始让 last 等于二叉树的根节点,并将其点放入队列中。
队头节点出队列,并打印,将该节点的左孩子入队,并让 nlast 等于该节点,将该节点的右孩子入队,并让 nlast 等于该节点。
如果打印的节点等于 last 当前指向的节点,则打印一次换行,同时让 last 等于 nlast。
重复步骤2,3,知道队列为空为止。
图示过程如下:
先将 1 入队
再将 1 出队,并将 2 ,3 入队,并让 nlast 分别指向 2, 3
此时发现,出队列的节点与 last 指向的节点相等,此时,打印换行符。同时让 last 等于 nlast
重复上述步骤,将 2 出队列,并将 4 入队列,让 nlast 指向 4
再将 3 出队列,并将 5,6 入队列,让 nlast 分别指向 5,6 ,此时发现3 等于 last ,则再打印一次换行,并让 last 等于 nlast
重复上述步骤,最终结果如下:
这样,按层换行打印二叉树就完成啦!
代码如下:
#pragma once #include#include #include using namespace std; template struct BinaryTreeNode { BinaryTreeNode(const T& x) :_data(x) , _left(NULL) , _right(NULL) {} T _data; BinaryTreeNode * _left; BinaryTreeNode * _right; }; template class BinaryTree { public: BinaryTree() :_root(NULL) {} BinaryTree(const T* a, size_t size) { size_t index = 0; _root = _CreateTree(a, size, index); } ~BinaryTree() { _DestroyTree(_root); _root = NULL; } void LevelOrder() //层次遍历 { _LevelOrder(_root); //每层换行! } protected: BinaryTreeNode * _CreateTree(const T*& a, size_t size, size_t& index) //创建二叉树 { assert(a); BinaryTreeNode * NewNode = NULL; if (index < size && '#' != a[index]) { NewNode = new BinaryTreeNode (a[index]); NewNode->_left = _CreateTree(a, size, ++index); NewNode->_right = _CreateTree(a, size, ++index); } return NewNode; } void _DestroyTree(BinaryTreeNode *& root) //销毁二叉树 { if (NULL == root) return; //后序遍历删除结点 _DestroyTree(root->_left); _DestroyTree(root->_right); delete root; root = NULL; } void _LevelOrder(BinaryTreeNode *& root) { if (NULL == root) return; std::queue *> q; q.push(root); BinaryTreeNode * last = root; BinaryTreeNode * nlast = NULL; while (!q.empty()) { BinaryTreeNode * cur = q.front(); cout << cur->_data << " "; q.pop(); if (cur->_left) { q.push(cur->_left); nlast = cur->_left; } if (cur->_right) { q.push(cur->_right); nlast = cur->_right; } if (cur == last) { cout << endl; last = nlast; } } cout << endl; } protected: BinaryTreeNode * _root; }; void Test1() { int array[] = { 1, 2, 4, '#', '#', '#', 3, 5, 7, '#', '#', 8, '#', '#', 6 }; BinaryTree t1(array, sizeof(array)/sizeof(int)); t1.LevelOrder(); }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
分享标题:按层换行打印二叉树-创新互联
新闻来源:http://myzitong.com/article/dhecje.html