树(5)二叉树层次遍历的应用

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
#include <Windows.h>
using namespace std;

typedef struct _Node
{
    int data;
    struct _Node *left;
    struct _Node *right;

    _Node()
    {
        data = 0;
        left = NULL;
        right = NULL;
    }
}Node, *_PNode;

//***************************************层次遍历的举例********************************************begin

//创建二叉树利用先序创建
/*
                                          /     \
      3
                                        / \      / 
  5    6
                                      / \   \  / \
  8  9  10 11
                                    /     \
     13

*/
void CreateBitree(_PNode &pNode)
{
    int dat;
    cin>>dat;
    if(dat==0)
    {
        pNode = NULL;
    }
    else 
    {
        pNode = new Node();
        pNode->data=dat;      
        CreateBitree(pNode->left);      
        CreateBitree(pNode->right);
    }
}

//二叉树的**自下而上，自右向左**的遍历方法
void ReverseLevel(_PNode pRoot)
{
    queue<_PNode> q;
    stack<_PNode> s;
    _PNode pNode = NULL;
    if (NULL == pRoot)
    {
        return;
    }
    q.push(pRoot);
    while (!q.empty())
    {
        pNode = q.front();//取队首元素
        q.pop();
        s.push(pNode);//将队首元素入栈
        if (NULL != pNode->left)
        {
            q.push(pNode->left);
        }
        if (NULL != pNode->right)
        {
            q.push(pNode->right);
        }
    }
    while (!s.empty())
    {
        pNode = s.top();
        s.pop();
        cout<<pNode->data<<"  ";
    }
    cout<<endl;
}

//统计二叉树中度为1的节点的个数,层次遍历
int CountOneDepth(_PNode pRoot)
{
    queue<_PNode> q;
    _PNode pNode = NULL;
    int count = 0;
    if (NULL == pRoot)
    {
        return count;
    }
    q.push(pRoot);
    while (!q.empty())
    {
        pNode = q.front();
        q.pop();
        if ((NULL != pNode->left && NULL == pNode->right)
            || (NULL == pNode->left && NULL != pNode->right))//这是度为1的核心代码,(树)节点拥有的子树树称为节点的度
        {
            count++;
        }
        if (NULL != pNode->left)
        {
            q.push(pNode->left);
        }
        if (NULL != pNode->right)
        {
            q.push(pNode->right);
        }
    }
    return count;
}

//查找二叉树最大宽度，没看懂？
int FindMaxWidth(_PNode pRoot)
{
    _PNode q[100] = {0};
    _PNode pNode = NULL;
    int front = 0;
    int rear = 0;
    int last = 0;
    int width = 0;
    int temp = 0;
    if (NULL == pRoot)
    {
        return width;
    }
    q[rear] = pRoot;
    while (front <= last)
    {
        pNode = q[front++];
        temp++;
        if (NULL != pNode->left)
        {
            q[++rear] = pNode->left;
        }
        if (NULL != pNode->right)
        {
            q[++rear] = pNode->right;
        }
        if (front > last)
        {
            last = rear;
            if (temp > width)
            {
                width = temp;
            }
            temp = 0;
        }
    }
    return width;
}

//***************************************层次遍历的举例********************************************end

//辅助函数，设置控制台的颜色
void SetConsoleTextColor(WORD dwColor)
{
    HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
    if (INVALID_HANDLE_VALUE == handle)
    {
        return;
    }
    SetConsoleTextAttribute(handle, dwColor);
}
int _tmain(int argc, _TCHAR* argv[])
{
    _PNode pRoot1 = NULL;

    SetConsoleTextColor(FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    fstream fin("level.txt");
    CreateBitree(pRoot1);
    cout<<endl<<"******************层次遍历举例********************"<<endl;
    cout<<endl<<"二叉树的自下而上，自右向左的遍历"<<endl;
    ReverseLevel(pRoot1);
    cout<<endl<<"二叉树中度为1的节点个数："<<CountOneDepth(pRoot1)<<endl;
    cout<<endl<<"二叉树中最大的宽度为   ："<<FindMaxWidth(pRoot1)<<endl;
    system("pause");
    cout<<endl;
    return 0;
}