44_栈的应用、二叉树

栈的应用

Char code[] = “1 + 2 + 3 *4”; //return 15,中缀表达式

后缀表达式 逆波兰表达式

1.计算

碰到数字就入栈

碰到符号就计算

2.转换

碰到数字打印

碰到运算符比较优先级小于等于出栈,其它入栈

3.Atoi转换字符的数组成基本类型

队列的应用

  1. 打印机

双向队列

  1. 可以操作头和尾,紧急插到头部,不紧急插到尾部

动态数据和链表

  1. 查询都慢

  1. 主要解决查找问题

定义

  1. 树是N(n>=0)个结点的有限集T,当n=0时,为空树
  2. 结点的度(degree):结点的子树数
  3. 树的度:树种各结点的最大值
  4. N度数:度为n的树
  5. 叶子(终端结点):度为0的结点
  6. 分枝结点(非终端结点,非叶子):度不为0的结点
  7. 双亲(父母,parent)和孩子(儿子,child)
  8. 结点的层:根的层为1,其余任一结点的层等于其双亲的层加1
  9. 树的深度:树中各结点的层的最大值
  10. 兄弟
  11. 堂兄弟

二叉树

  1. 树的度为2,最多两个孩子
  2. 二叉树的第n(n>1)层最多有2^n-1个结点
  3. 二叉搜索|排序树,增删改查的时间复杂度为log2^n,有排序的情况
  4. 二叉搜索树值由插入和移除查找,没有改的功能
  5. 前序遍历:根结点先输出,再左边,再右边
  6. 中序遍历:左孩子先输出,再输出根,再右边。有序输出
  7. 后序遍历:右孩子先输出,再输出根,再左边。删除某个叶子结点

作业

1.编写树遍历非递归(前序,中序,后序, 层序)
2.利用栈和队列结构完成

前序遍历序列: A B D E H I C F G
中序遍历序列: D B H E I A F C G
后序遍历序列: D H I E B F G C A

二叉树示意图:
A
/ \
B C
/ \ / \
D E F G
/ \
H I

10
/ \
4 20
/ \ / \
2 6 17 21
/ \
5 7

前序:10 4 2 6 5 7 20 17 21
中序:2 4 5 6 7 10 17 20 21
后序:2 5 7 6 4 17 21 20 10

//当左孩子不为空一直压栈当前结点,为空当前结点就为栈顶元素,出栈,当前结点为节点右孩子,如果结点不为空压栈右孩子,打印。

 //Queue.h
#pragma once

template 
class CQueue
{
private:
    class CLinkNode     //单向链表
    {
    public:
        CLinkNode()
        {
            m_pElement = nullptr;
            m_pNextNode = nullptr;
        }

        CLinkNode(const T& element)
        {
            m_pElement = new T(element);
            m_pNextNode = nullptr;
        }

        ~CLinkNode()
        {
            if (m_pElement != nullptr)
            {
                delete m_pElement;
            }
        }

    public:
        T* m_pElement;              //元素
        CLinkNode *m_pNextNode;     //下一个结点
    };

public:
    CQueue()
    {
        m_pQueueHead = nullptr;
        m_pQueueTail = nullptr;
        setSize(0U);
    }

    CQueue(const T& element)
    {
        CLinkNode *pNode = new CLinkNode(element);
        m_pQueueHead = m_pQueueTail = pNode;
        setSize(1U);
    }

    ~CQueue()
    {
        while (getSize() > 0U)
        {
            pop();
        }
    }

    void push(const T& element)                 //入队
    {
        if (getSize() == 0U)
        {
            CLinkNode *pNode = new CLinkNode(element);
            m_pQueueHead = m_pQueueTail = pNode;
            setSize(1U);
        }
        else
        {
            CLinkNode *pNode = new CLinkNode(element);
            m_pQueueTail->m_pNextNode = pNode;
            m_pQueueTail = pNode;
            setSize(getSize() + 1U);
        }
    }

    void pop()                                //出队
    {
        if (getSize() == 0U)
        {
            return;
        }
        else
        {
            CLinkNode *pNode = m_pQueueHead;
            m_pQueueHead = pNode->m_pNextNode;
            delete pNode;
            setSize(getSize() - 1U);
        }
    }

    T* getTail() const    //获得队列尾部元素
    {
        if (getSize() > 0)
        {
            return m_pQueueTail->m_pElement;
        }
        else
        {
            throw 0;
        }
    }

    T* getHead() const  //获得队列头部元素
    {
        if (getSize() > 0)
        {
            return m_pQueueHead->m_pElement;
        }
        else
        {
            throw 0;
        }
    }

    const unsigned getSize() const  //获得队列的大小
    {
        return m_uSize;
    }

private:
    void setSize(const unsigned size)   //设置队列大小
    {
        m_uSize = size;
    }

private:
    CLinkNode *m_pQueueHead;    //队列头
    CLinkNode *m_pQueueTail;     //队列尾
    unsigned m_uSize;           //队列的大小
};
 //Stack.h
#pragma once

template 
class CStack
{
private:
    class CLinkNode     //单向链表
    {
    public:
        CLinkNode()
        {
            m_pElement = nullptr;
            m_pNextNode = nullptr;
        }

        CLinkNode(const T& element)
        {
            m_pElement = new T(element);
            m_pNextNode = nullptr;
        }

        ~CLinkNode()
        {
            if (m_pElement != nullptr)
            {
                delete m_pElement;
            }
        }

    public:
        T* m_pElement;              //元素
        CLinkNode *m_pNextNode;     //下一个结点
    };

public:
    CStack()
    {
        m_pStackTop = nullptr;
        setSize(0U);
    }

    CStack(const T& element)
    {
        m_pStackTop = new CLinkNode(element);
        setSize(1U);
    }

    ~CStack()
    {
        while (m_pStackTop != nullptr)
        {
            pop();
        }
    }

    void push(const T& element)                 //压栈
    {
        CLinkNode *pNode = new CLinkNode(element);
        pNode->m_pNextNode = m_pStackTop;
        m_pStackTop = pNode;
        setSize(getSize() + 1U);
    }

    void pop()                                //出栈
    {
        if (getSize() > 0)
        {
            CLinkNode *pOldNode = m_pStackTop;
            m_pStackTop = pOldNode->m_pNextNode;
            delete pOldNode;
            setSize(getSize() - 1U);
        }
    }

    T* getTop() const    //获得栈顶元素
    {
        return m_pStackTop->m_pElement;
    }

    const unsigned getSize() const  //获得栈的大小
    {
        return m_uSize;
    }

private:
    void setSize(const unsigned size)   //设置栈大小
    {
        m_uSize = size;
    }

private:
    CLinkNode *m_pStackTop;     //栈顶
    unsigned m_uSize;           //栈的大小
};
 //BInaryTree.h
#pragma once
#include "Stack.h"
#include "Queue.h"

#include 
using namespace std;

template 
class CBinaryTree
{
private:
    class TreeNode
    {
    public:
        
        TreeNode(const T &element,
            TreeNode *left = nullptr,
            TreeNode *right = nullptr)
        {
            m_pElement = new T(element);
            m_pLeft = left;
            m_pRight = right;
        }

    public:
        T *m_pElement;          //元素
        TreeNode *m_pLeft;      //左儿子
        TreeNode *m_pRight;     //右儿子
    };

public:
    CBinaryTree()
    {
        m_pTreeRoot = nullptr;
    }

    CBinaryTree(const T& element)
    {
        m_pTreeRoot = new TreeNode(element);
    }

    CBinaryTree& insert(const T& element)       //增加结点
    {
        if (empty())
        {
            m_pTreeRoot = new TreeNode(element);
        }
        else
        {
            insert(element, m_pTreeRoot);
        }

        return *this;
    }

    void printTreePre()             //前序遍历
    {
        if (!empty())
        {
            CStack stackNode;
            TreeNode *pNode = m_pTreeRoot;
            while (pNode != nullptr
                    ||
                    stackNode.getSize() != 0U
                )
            {
                if (pNode != nullptr)
                {
                    cout << *pNode->m_pElement << "\t";
                    stackNode.push(pNode);
                    pNode = pNode->m_pLeft;
                }
                else
                {
                    pNode = *stackNode.getTop();
                    stackNode.pop();
                    pNode = pNode->m_pRight;
                }
            }
            cout << endl;
        }
    }

    void printTreeMid()             //中序遍历
    {
        if (!empty())
        {
            CStack stackNode;
            TreeNode *pNode = m_pTreeRoot;
            while (pNode != nullptr
                    ||
                   stackNode.getSize() != 0U
                )
            {
                if (pNode != nullptr)
                {
                    stackNode.push(pNode);
                    pNode = pNode->m_pLeft;
                }
                else
                {
                    pNode = *stackNode.getTop();
                    cout << *pNode->m_pElement << "\t";
                    stackNode.pop();
                    pNode = pNode->m_pRight;
                }
            }
            cout << endl;
        }
    }

    void printTreeAft()             //后序遍历
    {
        if (!empty())
        {
            CStack stackNode;

            TreeNode* pCur = m_pTreeRoot;
            TreeNode* pLastVisit = nullptr;

            while (pCur != nullptr)
            {
                stackNode.push(pCur);
                pCur = pCur->m_pLeft;
            }

            while (stackNode.getSize() != 0U)
            {
                pCur = *stackNode.getTop();
                stackNode.pop();

                if (pCur->m_pRight == NULL || pCur->m_pRight == pLastVisit)
                {
                    cout << *pCur->m_pElement << "\t";
                    pLastVisit = pCur;
                }
                else
                {
                    stackNode.push(pCur);
                    pCur = pCur->m_pRight;

                    while (pCur)
                    {
                        stackNode.push(pCur);
                        pCur = pCur->m_pLeft;
                    }
                }
            }
            cout << endl;
        }
    }

    void printTreeOrd()             //层序遍历
    {
        if (m_pTreeRoot != nullptr)
        {
            CQueue queueNode;
            TreeNode * pFront = nullptr;

            queueNode.push(m_pTreeRoot);

            while (queueNode.getSize() != 0U)
            {
                pFront = *queueNode.getHead();
                queueNode.pop();

                if (pFront->m_pLeft != nullptr)
                {
                    queueNode.push(pFront->m_pLeft);
                }

                if (pFront->m_pRight != nullptr)
                {
                    queueNode.push(pFront->m_pRight);
                }

                cout << *pFront->m_pElement << "\t";
            }

            cout << endl;
        }
    }

    bool empty()
    {
        if (m_pTreeRoot == nullptr)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    ~CBinaryTree()
    {
        ;
    }
private:
    CBinaryTree& insert(const T& element, TreeNode*& node)
    {
        if (element < *(node->m_pElement))
        {
            if (node->m_pLeft == nullptr)
            {
                node->m_pLeft = new TreeNode(element);
            }
            else
            {
                insert(element, node->m_pLeft);
            }
        }
        else if (element > *(node->m_pElement))
        {
            if (node->m_pRight == nullptr)
            {
                node->m_pRight = new TreeNode(element);
            }
            else
            {
                insert(element, node->m_pRight);
            }
        }
        return *this;
    }
    
private:
    TreeNode *m_pTreeRoot;  //树根
};
 //test.cpp
#include "BInaryTree.h"

int main()
{
    CBinaryTree tree;
    tree.insert(10);
    tree.insert(4);
    tree.insert(2);
    tree.insert(6);
    tree.insert(5);
    tree.insert(7);
    tree.insert(20);
    tree.insert(17);
    tree.insert(21);

    tree.printTreePre();
    tree.printTreeMid();
    tree.printTreeAft();
    tree.printTreeOrd();
    system("pause");
    return 0;
}
0 条评论
发表一条评论