二叉树的分层遍历

待我称王封你为后i 2022-02-01 18:23 145阅读 0赞

二叉树除了前、中、后序三种遍历方式外，有时候还要用到分层遍历。分层遍历就是二叉树的广度优先算法，暂时还没有见过图的广度优先算法，据说广度优先算法都要使用一个辅助队列。

题目一：分层遍历二叉树，从上往下打印二叉树的每一个节点，同一层次的节点按照从左到右的顺序打印。

下图顺序输出1 2 3 4 5 6 7 8

![20130609215605250][]

//用queue更好
    void PrintBinayTree(BinaryTreeNode* pRoot)
    {
    	if (!pRoot)
    		return;
    	std::deque<BinaryTreeNode*> dequeNode;
    	dequeNode.push_back(pRoot);
    	while(!dequeNode.empty())
    	{
    		BinaryTreeNode *p=dequeNode.front();
    		dequeNode.pop_front();
    		std::cout << p->m_nValue;
    		if(p->m_pLeft!=NULL)
    			dequeNode.push_back(p->m_pLeft);
    		if(p->m_pRight!=NULL)
    			dequeNode.push_back(p->m_pRight);
    	}
    }

题目二：上面的程序虽然是分层打印了，但是打印的时候是直接顺序输出的。并不能在输出中确定哪些数字属于哪层。如何使得程序分层打印，从上至下每层输出一行？

分析：可以用一个数组并用两个标号来表示。

解法一：

void PrintNodeByLevel(BinaryTreeNode*pRoot)
    {
           if(pRoot==NULL)
                  return;
           std::vector<BinaryTreeNode*>vec;
           //运用了vector可以利用其动态增长的特性
           //但是这个时候标号就不能用迭代器了，因为增长的时候迭代器会失效！！！
           vec.push_back(pRoot);
           intcur=0;//指向当前节点
           intlast=1;
           while(cur<vec.size())
           {
                  last=vec.size();//指向本层节点的后一个节点
                  std::cout<<vec[cur]->m_nValue<< " ";
                  if(vec[cur]->m_pLeft!=NULL)
                         vec.push_back(vec[cur]->m_pLeft);
                  if(vec[cur]->m_pRight!=NULL)
                         vec.push_back(vec[cur]->m_pRight);
                  cur++;
           }
           //每一次循环都将下一层的节点压入vector，并且打印完本层节点
           std::cout<<std::endl;//cur==last时说明该层访问结束
    }

当树的节点比较多的时候，上面运用vector存储了所有的节点，所以空间复杂度是O(n)，对空间消耗是比较大的。

解法二：运用两个队列来进行交换

void PrintNodeByLevel(BinaryTreeNode* pRoot)
    {
    	if (pRoot==NULL)
    		return;
    	//Q1为待打印层，Q2为下一待打印层
    	deque<BinaryTreeNode*> Q1, Q2; 
        Q1.push_back(pRoot); 
        do { 
            do { 
                BinaryTreeNode* node = Q1.front(); 
                Q1.pop_front(); 
                cout << node->m_nValue << " "; 
                if (node->m_pLeft) 
                    Q2.push_back(node->m_pLeft); 
                if (node->m_pRight) 
                    Q2.push_back(node->m_pRight); 
            } while (!Q1.empty()); 
            cout << endl; 
    		//这里需要运用daque而不是queue，因为deque才支持swap()操作。
    		//注意，swap()是O(1)的操作，实际上只是交换迭代器。 
            Q1.swap(Q2);  
        }while(!Q1.empty()); 
    }

能不能仅用一个队列模拟问题一中的分层遍历来实现打印？这样关键的问题是如何换行。所以提供一个标志就可以了，可以运用一个空指针来表示一行的结束。

解法三：

void PrintNodeByLevel(BinaryTreeNode* pRoot) 
    { 
    	if (pRoot==NULL)
    		return;
        queue<BinaryTreeNode*> Q; 
        Q.push(pRoot); 
        Q.push(0); //空指针
        do { 
            BinaryTreeNode* node = Q.front(); 
            Q.pop(); 
            if (node) { 
                cout << node->m_nValue << " "; 
                if (node->m_pLeft) 
                    Q.push(node->m_pLeft); 
                if (node->m_pRight) 
                    Q.push(node->m_pRight); 
            }
    		//当发现空指针(结束信号)时，要检查队列内是否还有节点，
    		//如果没有的话还插入新的结束信号，则会做成死循环
            else if (!Q.empty()) 
    		{ 
                Q.push(0); 
                cout << endl; 
            } 
        } while (!Q.empty()); 
    }

[20130609215605250]: /images/20220126/a8adcd6628fc46019341f0f3777fd002.png