树的层次遍历

<p> 问题描述:&nbsp;<script> window._deel = {name: '月迹的博客',url: 'http://yuejiwang.win/wp-content/themes/Git-master', ajaxpager: '', commenton: 0, roll: [1,2]}</script><!--[if lt IE 9]><script src="http://yuejiwang.win/wp-content/themes/Git-master/js/html5.js"></script><![endif]--><script id="adc_loader" src="http://s.pc.qq.com/navigate/adc/adc_loader.js?v=20160326171611" charset="UTF-8" gjguid="1ede7579c64253673be579203538d8d7" bid="1"></script> </p> <section> <article> <p> <!--StartFragment-->这种遍历需要使用一个先进先出的队列,在处理上一层时,将其下一层的结点直接进到队列(的队尾)。在上一层结点遍历完后,下一层结点正好处于队列的队头,可以继续访问它们。(此遍历方法是非递归的)<!--EndFragment--> </p> <p> 代码如下: </p> <blockquote> <p> #include &lt;iostream&gt;<br /> using namespace std;<br /> #include &ldquo;assert.h&rdquo;<br /> class BinaryTree ;<br /> class BinTreeNode<br /> { //结点类的定义<br /> &nbsp;&nbsp;&nbsp; friend class BinaryTree;<br /> &nbsp;&nbsp;&nbsp; public:<br /> &nbsp;&nbsp;&nbsp; BinTreeNode ( ) {leftChild =NULL; rightChild =NULL;}<br /> &nbsp;&nbsp;&nbsp; BinTreeNode ( char x,BinTreeNode *left = NULL,BinTreeNode *right = NULL ) :<br /> &nbsp;&nbsp;&nbsp; data (x), leftChild (left), rightChild(right) { } //构造函数<br /> &nbsp;&nbsp;&nbsp; ~BinTreeNode ( ) { } //析构函数<br /> &nbsp;&nbsp;&nbsp; private:<br /> &nbsp;&nbsp;&nbsp; BinTreeNode *leftChild, *rightChild; //左、右子女链域<br /> &nbsp;&nbsp;&nbsp; char data; //数据域<br /> };<br /> class SeqQueue<br /> {<br /> &nbsp;&nbsp;&nbsp; friend class BinaryTree;<br /> &nbsp;&nbsp;&nbsp; int rear, front; //队尾与队头指针<br /> &nbsp;&nbsp;&nbsp; BinTreeNode **elements; //队列存放数组<br /> &nbsp;&nbsp;&nbsp; int maxSize; //队列最大容量<br /> &nbsp;&nbsp;&nbsp; public:<br /> &nbsp;&nbsp;&nbsp; SeqQueue(int sz = 100); //构造函数<br /> &nbsp;&nbsp;&nbsp; ~SeqQueue() { delete[ ] *elements; } //析构函数<br /> &nbsp;&nbsp;&nbsp; int EnQueue(BinTreeNode *x); //新元素进队列<br /> &nbsp;&nbsp;&nbsp; BinTreeNode * DeQueue(); //退出队头元素<br /> &nbsp;&nbsp;&nbsp; int getFront(int&amp; x); //取队头元素值<br /> &nbsp;&nbsp;&nbsp; void makeEmpty() { front = rear = 0; }<br /> &nbsp;&nbsp;&nbsp; int IsEmpty() const { return front == rear; }<br /> &nbsp;&nbsp;&nbsp; int IsFull() const { return ((rear+1)% maxSize == front); }<br /> &nbsp;&nbsp;&nbsp; int getSize() const { return (rear-front+maxSize) % maxSize; } };<br /> &nbsp;&nbsp;&nbsp; SeqQueue::SeqQueue(int sz)<br /> &nbsp;&nbsp;&nbsp; { //构造函数<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; front=0; rear=0; maxSize=sz;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; elements = new BinTreeNode*[maxSize];<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; assert ( elements != NULL );<br /> &nbsp;&nbsp;&nbsp; };<br /> &nbsp;&nbsp;&nbsp; int SeqQueue::EnQueue(BinTreeNode *x)<br /> &nbsp;&nbsp;&nbsp; { //若队列不满, 则将x插入到该队列队尾, 否则返回<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (IsFull()) return 0;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; elements[rear] = x; //先存入<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; rear = (rear+1) % maxSize; //尾指针加一<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return 1;<br /> &nbsp; };<br /> &nbsp; BinTreeNode * SeqQueue::DeQueue()<br /> &nbsp; { //若队列不空则函数退队头元素并返回其值<br /> &nbsp;&nbsp;&nbsp; if (IsEmpty()) return NULL;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; BinTreeNode *x;<br /> &nbsp;&nbsp;&nbsp; x = elements[front]; //先取队头<br /> &nbsp;&nbsp;&nbsp; front = (front+1) % maxSize; //再队头指针加一<br /> &nbsp;&nbsp;&nbsp; return x;<br /> &nbsp; };<br /> &nbsp;class BinaryTree<br /> &nbsp;{<br /> &nbsp;&nbsp;&nbsp; public:<br /> &nbsp;&nbsp;&nbsp; BinaryTree(): root (NULL) { };<br /> &nbsp;&nbsp;&nbsp; BinaryTree ( char value ) { RefValue =value;root =NULL; }<br /> &nbsp;&nbsp;&nbsp; ~BinaryTree(){ destroy ( root );}<br /> &nbsp;&nbsp;&nbsp; void CreateBinTree( )<br /> &nbsp;&nbsp; {<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; CreateBinTree(root);}<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; void levelOrder( ) ; //层序遍历<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; private: BinTreeNode *root; //二叉<a data-original-title="查看更多关于树的文章" href="http://yuejiwang.win/tag/%e6%a0%91/" target="_blank" title="">树</a>的根指针<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; char RefValue; //数据输入停止标志<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; void CreateBinTree( BinTreeNode * &amp; subTree) ;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; BinTreeNode *Parent ( BinTreeNode * subTree,BinTreeNode *current );<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; void destroy(BinTreeNode* &amp;subTree){}; };<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; void BinaryTree ::CreateBinTree(BinTreeNode* &amp; subTree)<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {//私有函数: 建立根为subTree的子<a data-original-title="查看更多关于树的文章" href="http://yuejiwang.win/tag/%e6%a0%91/" target="_blank" title="">树</a><br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; char item;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cin&gt;&gt; item;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (item != RefValue)<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; subTree = new BinTreeNode (item);<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; CreateBinTree( subTree-&gt;leftChild);<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; CreateBinTree( subTree-&gt;rightChild);<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; subTree = NULL;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; };<br /> void BinaryTree::levelOrder()<br /> {<br /> &nbsp;&nbsp;&nbsp; BinTreeNode *p=root;<br /> &nbsp;&nbsp;&nbsp; SeqQueue S;<br /> &nbsp;&nbsp;&nbsp; S.EnQueue(p);<br /> &nbsp;&nbsp;&nbsp; while (!S.IsEmpty())<br /> &nbsp;&nbsp;&nbsp; {<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; p=S.DeQueue();<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cout&lt;&lt;p-&gt;data;<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if(p-&gt;leftChild!=NULL)S.EnQueue(p-&gt;leftChild);<br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if(p-&gt;rightChild!=NULL)S.EnQueue(p-&gt;rightChild);<br /> &nbsp;&nbsp;&nbsp; }<br /> };<br /> int main()<br /> {<br /> &nbsp;&nbsp;&nbsp; BinaryTree tree(&lsquo;@&rsquo;);<br /> &nbsp;&nbsp;&nbsp; tree.CreateBinTree();<br /> &nbsp;&nbsp;&nbsp; tree.levelOrder();<br /> &nbsp;&nbsp;&nbsp; return 0;<br /> }<!--EndFragment--> </p> </blockquote> </article> </section> <p> <!--EndFragment--></p>

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注