按之字顺序打印二叉树

蔚落 2023-03-13 13:52 105阅读 0赞

## 一、前言 ##

前文《上往下打印二叉树》是从上往下，从左往右打印，扩展一下这个问题，按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推，该怎样打印呢？

## 二、题目 ##

按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推

### 三、思路 ###

先回顾一下前文《上往下打印二叉树》，用一个队列来实现的，队列是先进先出，正好满足从左往右打印树。队列我们可以看着是一组数据正着进去，正着出来。现在我们要求是按之字顺序打印，也就是类似一组数据先正着读，再反着读，双向链表不是正好可以满足？。哈哈哈！我本来是想说用两个栈可以实现，栈1将栈2中的树子节点添加到栈1中，先添加左子节点再添加右子节点，栈2将栈1中的树子节点添加到栈2中，先添加右子节点再添加左子节点。算是意外收获了一种解法。

解法一：用两个栈实现

解法二：用连表实现

直接看图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

奇数行从左往右打印，偶数行从右往左打印。

当我们从左往右打印当前行的时候，可以获得下一行的数据，获得数据顺序是从左往右。

当我们从右往左打印当前行的时候，可以获得下一行的数据，获得数据顺序是从右往左。

发现不管我们是从左往右还是从右往左，获得下一行数据顺序和上一行是同方向，但是我们现在需要下一行读取顺序和上一行顺序是相反的。入栈和出栈顺序相反，可以满足，此时为解法一。读当前行数据的时候将下一行数据从头加到大连表中，读完当前行数据的时候，从头开始读取连表的数据，读取数据顺序和添加顺序相反，此时为解法二。

## 四、闲谈 ##

当对一个问题反复思考的时候，可能会有意想不到的收获。本质上栈底层可以用连表实现。

## 五、编码实现 ##

#pragma once
    
    #include <cstdio>
    #include <queue>
    #include <vector>
    #include <map>
    #include <stack>
    #include <list>
    #include "Common.h"
    using namespace std;
    
    #define NAMESPACE_GETTREELINES namespace GETTREELINES {
    #define NAMESPACE_GETTREELINESEND }
    
    
    // 从上往下，从左往右，按行输出节点，不包含空节点 
    //【队列实现】
    template<class T>
    void GetTreesInLines(BinaryTreeNode<T>* pRoot, map<int, vector<T>>& data)
    {
        if (pRoot == nullptr)
            return;
    
        std::queue<BinaryTreeNode<T>*> nodes;
        nodes.push(pRoot);
        int nextLevel = 0;
        int toBePrinted = 1;
        vector<T> vt;
        int line = 1;
        while (!nodes.empty())
        {
            BinaryTreeNode<T>* pNode = nodes.front();
            //printf("%d ", pNode->m_nValue);
            vt.push_back(pNode->m_nValue);
            if (pNode->m_pLeft != nullptr)
            {
                nodes.push(pNode->m_pLeft);
                ++nextLevel;
            }
            if (pNode->m_pRight != nullptr)
            {
                nodes.push(pNode->m_pRight);
                ++nextLevel;
            }
    
            nodes.pop();
            --toBePrinted;
            if (toBePrinted == 0)
            {
                //printf("\n");
                data[line++] = vt;
                vt.clear();
    
                toBePrinted = nextLevel;
                nextLevel = 0;
            }
        }
    }
    
    
    // 从上往下，从左往右，包含空节点
    //【队列实现】
    template<class T>
    void GetTreesInLines(BinaryTreeNode<T>* pRoot, map<int, vector<T>>& data, T empty)
    {
        if (pRoot == nullptr)
            return;
    
        std::queue<BinaryTreeNode<T>*> nodes;
        nodes.push(pRoot);
        int nextLevel = 0;
        int toBePrinted = 1;
        vector<T> vt;
        int line = 1;
        bool ret = false;
        while (!nodes.empty())
        {
            BinaryTreeNode<T>* pNode = nodes.front();
            if (pNode == nullptr)
            {
                vt.push_back(empty);
    
                //左节点
                nodes.push(nullptr);
                ++nextLevel;
    
                //又节点
                nodes.push(nullptr);
                ++nextLevel;
            }
            else
            {
                vt.push_back(pNode->m_nValue);
                
                nodes.push(pNode->m_pLeft);
                ++nextLevel;
              
                nodes.push(pNode->m_pRight);
                ++nextLevel;
    
                if (pNode->m_pLeft != nullptr || pNode->m_pRight != nullptr)
                {
                    ret = true;
                }
            }
    
            nodes.pop();
            --toBePrinted;
            if (toBePrinted == 0)
            {
                data[line++] = vt;
                vt.clear();
                toBePrinted = nextLevel;
                nextLevel = 0;
    
                if (ret == false)
                {
                    break;
                }
                ret = false;
            }
        }
    }
    
    
    //按行输出节点，不包含空节点
    //按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
    //【双栈实现】
    template<class T>
    void GetTreesInLines_Zigzag_Stack(BinaryTreeNode<T>* pRoot, map<int, vector<T>>& data)
    {
        data.clear();
        if (pRoot == nullptr)
        {
            return;
        }
    
        stack<BinaryTreeNode<T>*> stkR;      // 向右打印， 左 -> 右 
        stack<BinaryTreeNode<T>*> stkL;      // 向左打印， 右 -> 左
        int line = 1;
        stkR.push(pRoot);
        vector<T> vect;
        while (true)
        {
            vect.clear();
            if ((line & 1) == 1) // 奇数列，左 -> 右 
            {
                if (stkR.empty())
                {
                    break;
                }
    
                while (!stkR.empty())
                {
                    vect.push_back(stkR.top()->m_nValue);
                    // 先左
                    if (stkR.top()->m_pLeft != nullptr)
                    {
                        stkL.push(stkR.top()->m_pLeft);
                    }
    
                    // 再右
                    if (stkR.top()->m_pRight != nullptr)
                    {
                        stkL.push(stkR.top()->m_pRight);
                    }
    
                    stkR.pop();
                }
            }
            else // 偶数列，右 -> 左
            {
                if (stkL.empty())
                {
                    break;
                }
    
                while (!stkL.empty())
                {
                    vect.push_back(stkL.top()->m_nValue);
                    // 先右
                    if (stkL.top()->m_pRight != nullptr)
                    {
                        stkR.push(stkL.top()->m_pRight);
                    }
    
                    // 再左
                    if (stkL.top()->m_pLeft != nullptr)
                    {
                        stkR.push(stkL.top()->m_pLeft);
                    }
    
                    stkL.pop();
                }
            }
    
            data[line++] = vect;
        }
    }
    
    
    //按行输出节点，不包含空节点
    //按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
    //【一个连表实现】
    template<class T>
    void GetTreesInLines_Zigzag_List(BinaryTreeNode<T>* pRoot, map<int, vector<T>>& data)
    {
        data.clear();
        if (pRoot == nullptr)
        {
            return;
        }
    
        list<BinaryTreeNode<T>*> lt;
    	lt.push_back(pRoot);
    
    	auto itt = lt.begin();
    	auto ih = *itt;
    	ih->m_nValue;
    
    	T n = (*(lt.begin()))->m_nValue;
    
    	int line = 1;
    	int toBePrinted = 1;
    	int nextCount = 0;
    	vector<T> vect;
    	auto itBegin = lt.begin();
    	auto itEnd = lt.end();
    	auto it = itBegin;
    	while (true)
    	{
    		if (it == itEnd)
    		{
    			return;
    		}
    
    		vect.push_back((*it)->m_nValue);
    		if ((line & 1) == 1) // 奇数列，左 -> 右 
    		{
    			// 先左
    			if ((*it)->m_pLeft != nullptr)
    			{
    				lt.push_front((*it)->m_pLeft);
    				++nextCount;
    			}
    
    			// 再右
    			if ((*it)->m_pRight != nullptr)
    			{
    				lt.push_front((*it)->m_pRight);
    				++nextCount;
    			}
    
    		}
    		else // 偶数列，右 -> 左
    		{
    			// 先右
    			if ((*it)->m_pRight != nullptr)
    			{
    				lt.push_front((*it)->m_pRight);
    				++nextCount;
    			}
    
    			// 再左
    			if ((*it)->m_pLeft != nullptr)
    			{
    				lt.push_front((*it)->m_pLeft);
    				++nextCount;
    			}
    		}
    
    		++it;
    		if (--toBePrinted <= 0)
    		{
    			itEnd = itBegin;
    			itBegin = lt.begin();
    			it = itBegin;
    			toBePrinted = nextCount;
    			nextCount = 0;
    			data[line++] = vect;
    			vect.clear();
    		} 
    	}
    }
    
    NAMESPACE_GETTREELINES
    //
    // 测试
    template<class T>
    void Test(const char* testName, T* preorder, T* inorder, int length, T empty=0)
    {
    	map<int, vector<T>> data;
    	auto Print = [&]()
    	{
    		for (auto it = data.begin(); it != data.end(); ++it)
    		{
    			for (auto itv = it->second.begin(); itv != it->second.end(); ++itv)
    			{
    				cout << *itv << " ";
    			}
    			cout << endl;
    		}
    		cout << endl;
    	};
    
    	cout << testName << "从左往右，不含空节点打印，用【队列】实现" << endl;
    	BinaryTreeNode<T>* pRoot = Construct(preorder, inorder, length);
    	GetTreesInLines(pRoot, data);
    	Print();
    
    	cout << testName << "从左往右，含空节点打印，用【队列】实现" << endl;
    	GetTreesInLines(pRoot, data, empty);
    	Print();
    
    	cout << testName << "之字形打印，用两个【栈】实现" << endl;
    	GetTreesInLines_Zigzag_Stack(pRoot, data);
    	Print();
    
    	cout << testName << "之字形打印，用一个【连表】实现" << endl;
    	GetTreesInLines_Zigzag_List(pRoot, data); (pRoot, data);
    	Print();
    }
    
    // 普通二叉树
    //              1
    //           /     \
    //          2       3  
    //         /       / \
    //        4       5   6
    //         \         /
    //          7       8
    void Test1()
    {
        const int length = 8;
        char preorder[length + 1] = "12473568";
        char inorder[length + 1] = "47215386";
    	  char empty = 'X';
    
    	Test("Test1", preorder, inorder, length, empty);
    }
    
    // 完全二叉树
    //              1
    //           /     \
    //          2       3  
    //         / \     / \
    //        4   5   6   7
    void Test2()
    {
    	const int length = 7;
    	char preorder[length + 1] = "1245367";
    	char inorder[length + 1] = "4251637";
    	char empty = 'X';
    
    	Test("Test2", preorder, inorder, length, empty);
    }
    
    //                    1
    //              /           \
    //            2               3  
    //          /    \	        /   \
    //         4       5      6       7
    //       /   \   /   \   /   \   /   \
    //      8     9 10   11 12   13 14   15
    void Test3()
    {
        const int length = 15;
    	int preorder[length] = { 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15 };
        int inorder[length] = { 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15 };
    	int empty = -1;
    
    	Test("Test3", preorder, inorder, length, empty);
    }
    
    NAMESPACE_GETTREELINESEND
    
    void GetTreesInLines_Test()
    {
    	GETTREELINES::Test1();
    	GETTREELINES::Test2();
    	GETTREELINES::Test3();
    }

**执行结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: /images/20230312/5e4b528790714920b9120c0f029b2cdd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1]: /images/20230312/fc28508eed7243a3bd768aee5641736f.png