精华内容
下载资源
问答
  • 创建一棵二叉树,以二叉链表作存储结构,实现先根遍历算法
  • 二叉树遍历算法集合(前后序遍历的递归和非递归算法,层序遍历算法) 费了两天时间写的,包括前后序遍历的递归和非递归算法,还有层序遍历总共2*3 + 1 = 7遍历二叉树的算法,感觉其中后序遍历的非递归算法比较...

    二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)

    费了两天时间写的,包括前中后序遍历的递归和非递归算法,还有层序遍历总共2*3 + 1 = 7中遍历二叉树的算法,感觉其中后序遍历的非递归算法比较困难,想了很久最后的实现还是不够优雅,请大家指正~~

    总共三个文件,一个头文件,一个对应的cpp文件,还有一个用于测试的文件.

    头文件:
    /********************************************************************
        created:    2006/07/04
        filename:     BinaryTree.h
        author:        李创
                    
    http://www.cppblog.com/converse/

        purpose:    演示二叉树的算法
    ********************************************************************
    */


    #ifndef BinaryTree_H
    #define BinaryTree_H

    #include <stdlib.h>
    #include <stack>

    class BinaryTree
    {
    private:
        typedef int Item;
        typedef struct TreeNode
        {
            Item        Node;
            TreeNode*   pRight;
            TreeNode*   pLeft;

            TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
                : Node(node)
                , pRight(pright)
                , pLeft(pleft)
            {
            }


        }
    TreeNode, *PTreeNode;

    public:
        enum TraverseType
        {
            PREORDER    = 0,        // 前序
            INORDER        = 1,        // 中序
            POSTORDER    = 2,        // 后序
            LEVELORDER    = 3            // 层序
        }
    ;

        BinaryTree(Item Array[], int nLength);
        ~BinaryTree();

        PTreeNode GetRoot()
        {
            return m_pRoot;
        }


        // 遍历树的对外接口
        
    // 指定遍历类型和是否是非递归遍历,默认是递归遍历
        void Traverse(TraverseType traversetype, bool bRec = true);

    private:
        PTreeNode   CreateTreeImpl(Item Array[], int nLength);
        void        DetroyTreeImpl(PTreeNode pTreenode);

        void        PreTraverseImpl(PTreeNode pTreenode);        // 递归前序遍历树
        void        InTraverseImpl(PTreeNode pTreenode);        // 递归中序遍历树
        void        PostTraverseImpl(PTreeNode pTreenode);        // 递归后序遍历树

        void        NoRecPreTraverseImpl(PTreeNode pTreenode);    // 非递归前序遍历树
        void        NoRecInTraverseImpl(PTreeNode pTreenode);    // 非递归中序遍历树
        void        NoRecPostTraverseImpl(PTreeNode pTreenode);    // 非递归后序遍历树

        void        LevelTraverseImpl(PTreeNode pTreenode);

        PTreeNode   m_pRoot;        // 根结点

        
    // 采用STL里面的stack作为模拟保存链表结点的stack容器
        typedef std::stack<BinaryTree::PTreeNode> TreeNodeStack;
    }
    ;

    #endif


    实现文件:
    /********************************************************************
        created:    2006/07/04
        filename:     BinaryTree.cpp
        author:        李创
                    
    http://www.cppblog.com/converse/

        purpose:    演示二叉树的算法
    ********************************************************************
    */


    #include <iostream>
    #include <assert.h>
    #include <queue>
    #include "BinaryTree.h"

    BinaryTree::BinaryTree(Item Array[], int nLength)
        : m_pRoot(NULL)
    {
        assert(NULL != Array);
        assert(nLength > 0);

        m_pRoot = CreateTreeImpl(Array, nLength);
    }


    BinaryTree::~BinaryTree()
    {
        DetroyTreeImpl(m_pRoot);
    }


    // 按照中序递归创建树
    BinaryTree::PTreeNode BinaryTree::CreateTreeImpl(Item Array[], int nLength)
    {
        int mid = nLength / 2;
        PTreeNode p = new TreeNode(Array[mid]);

        if (nLength > 1)
        {
            p->pLeft    = CreateTreeImpl(Array, nLength / 2);
            p->pRight   = CreateTreeImpl(Array + mid + 1, nLength / 2 - 1);
        }


        return p;
    }


    void BinaryTree::DetroyTreeImpl(PTreeNode pTreenode)
    {
        if (NULL != pTreenode->pLeft)
        {
            DetroyTreeImpl(pTreenode->pLeft);
        }

        if (NULL != pTreenode->pRight)
        {
            DetroyTreeImpl(pTreenode->pRight);
        }


        delete pTreenode;
        pTreenode = NULL;
    }


    // 遍历树的对外接口
    // 指定遍历类型和是否是非递归遍历,默认是递归遍历
    void BinaryTree::Traverse(TraverseType traversetype, bool bRec /*= true*/)
    {
        switch (traversetype)
        {
        case PREORDER:    // 前序
            {            
                if (true == bRec)
                {
                    std::cout << "递归前序遍历树\n";
                    PreTraverseImpl(m_pRoot);
                }

                else
                {
                    std::cout << "非递归前序遍历树\n";
                    NoRecPreTraverseImpl(m_pRoot);
                }

            }

            break;

        case INORDER:    // 中序
            {            
                if (true == bRec)
                {
                    std::cout << "递归中序遍历树\n";
                    InTraverseImpl(m_pRoot);
                }

                else
                {
                    std::cout << "非递归中序遍历树\n";
                    NoRecInTraverseImpl(m_pRoot);
                }

            }

            break;

        case POSTORDER:    // 后序
            {            
                if (true == bRec)
                {
                    std::cout << "递归后序遍历树\n";
                    PostTraverseImpl(m_pRoot);
                }

                else
                {
                    std::cout << "非递归后序遍历树\n";
                    NoRecPostTraverseImpl(m_pRoot);
                }

            }

            break;

        case LEVELORDER:    // 层序
            {
                std::cout << "层序遍历树\n";
                LevelTraverseImpl(m_pRoot);
            }

        }


        std::cout << std::endl;
    }


    // 递归前序遍历树
    void BinaryTree::PreTraverseImpl(PTreeNode pTreenode)
    {
        if (NULL == pTreenode)
            return;

        std::cout << "Item = " << pTreenode->Node << std::endl;

        PreTraverseImpl(pTreenode->pLeft);

        PreTraverseImpl(pTreenode->pRight);
    }


    // 非递归前序遍历树
    void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)
    {
        if (NULL == pTreenode)
            return;

        TreeNodeStack NodeStack;
        PTreeNode pNode;
        NodeStack.push(pTreenode);

        while (!NodeStack.empty())
        {
            while (NULL != (pNode = NodeStack.top()))    // 向左走到尽头
            {
                std::cout << "Item = " << pNode->Node << std::endl;    // 访问当前结点
                NodeStack.push(pNode->pLeft);                    // 左子树根结点入栈
            }

            NodeStack.pop();                                    // 左子树根结点退栈
            if (!NodeStack.empty())
            {
                pNode = NodeStack.top();
                NodeStack.pop();                                // 当前结点退栈
                NodeStack.push(pNode->pRight);                // 当前结点的右子树根结点入栈
            }

        }

    }


    // 中序遍历树
    // 中序遍历输出的结果应该和用来初始化树的数组的排列顺序一致
    void BinaryTree::InTraverseImpl(PTreeNode pTreenode)
    {
        if (NULL == pTreenode)
            return;

        if (NULL != pTreenode->pLeft)
        {
            InTraverseImpl(pTreenode->pLeft);
        }


        std::cout << "Item = " << pTreenode->Node << std::endl;

        if (NULL != pTreenode->pRight)
        {
            InTraverseImpl(pTreenode->pRight);
        }

    }


    // 非递归中序遍历树
    void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)
    {
        if (NULL == pTreenode)
            return;

        TreeNodeStack NodeStack;
        PTreeNode pNode;
        NodeStack.push(pTreenode);

        while (!NodeStack.empty())
        {
            while (NULL != (pNode = NodeStack.top()))    // 向左走到尽头
            {
                NodeStack.push(pNode->pLeft);
            }


            NodeStack.pop();

            if (!NodeStack.empty() && NULL != (pNode = NodeStack.top()))
            {
                std::cout << "Item = " << pNode->Node << std::endl;
                NodeStack.pop();
                NodeStack.push(pNode->pRight);
            }

        }

    }


    // 后序遍历树
    void BinaryTree::PostTraverseImpl(PTreeNode pTreenode)
    {
        if (NULL == pTreenode)
            return;

        if (NULL != pTreenode->pLeft)
        {
            PostTraverseImpl(pTreenode->pLeft);
        }


        if (NULL != pTreenode->pRight)
        {
            PostTraverseImpl(pTreenode->pRight);
        }


        std::cout << "Item = " << pTreenode->Node << std::endl;
    }


    // 非递归后序遍历树
    void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)
    {
        if (NULL == pTreenode)
            return;

        TreeNodeStack NodeStack;
        PTreeNode pNode1, pNode2;
        NodeStack.push(pTreenode);
        pNode1 = pTreenode->pLeft;
        
        bool bVisitRoot = false;            // 标志位,是否访问过根结点
        while (!NodeStack.empty())
        {
            while (NULL != pNode1)            // 向左走到尽头
            {
                NodeStack.push(pNode1);
                pNode1 = pNode1->pLeft;
            }


            pNode1 = NodeStack.top();
            NodeStack.pop();

            if (NULL == pNode1->pRight)            // 如果没有右子树就是叶子结点
            {
                std::cout << "Item = " << pNode1->Node << std::endl;
                pNode2 = pNode1;
                pNode1 = NodeStack.top();

                if (pNode2 == pNode1->pRight)    // 如果这个叶子结点是右子树
                {
                    std::cout << "Item = " << pNode1->Node << std::endl;
                    NodeStack.pop();
                    pNode1 = NULL;
                }

                else                            // 否则访问右子树
                {
                    pNode1 = pNode1->pRight;
                }

            }

            else                                // 访问右子树
            {
                if (pNode1 == pTreenode && true == bVisitRoot)    // 如果已经访问过右子树那么就退出
                {
                    std::cout << "Item = " << pNode1->Node << std::endl;
                    return;
                }

                else
                {
                    if (pNode1 == pTreenode)
                    {
                        bVisitRoot = true;
                    }


                    NodeStack.push(pNode1);
                    pNode1 = pNode1->pRight;
                }

            }

        }

    }


    // 按照树的层次从左到右访问树的结点
    void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode)
    {
        if (NULL == pTreenode)
            return;

        // 层序遍历用于保存结点的容器是队列
        std::queue<PTreeNode> NodeQueue;
        PTreeNode pNode;
        NodeQueue.push(pTreenode);

        while (!NodeQueue.empty())
        {
            pNode = NodeQueue.front();
            NodeQueue.pop();
            std::cout << "Item = " << pNode->Node << std::endl;

            if (NULL != pNode->pLeft)
            {
                NodeQueue.push(pNode->pLeft);    
            }

            if (NULL != pNode->pRight)
            {
                NodeQueue.push(pNode->pRight);
            }
        
        }

    }

    测试文件:
    /********************************************************************
        created:    2006/07/04
        filename:     main.cpp
        author:        李创
                    
    http://www.cppblog.com/converse/

        purpose:    测试二叉树的算法
    ********************************************************************
    */


    #include "BinaryTree.h"

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <iostream>

    void DisplayArray(int array[], int length)
    {
        int i;

        for (i = 0; i < length; i++)
        {
            printf("array[%d] = %d\n", i, array[i]);
        }

    }


    void CreateNewArray(int array[], int length)
    {
        for (int i = 0; i < length; i++)
        {
            array[i] = rand() % 256 + i;
        }

    }


    int main()
    {
        int array[10];
        srand(time(NULL));

        // 创建数组
        CreateNewArray(array, 10);
        DisplayArray(array, 10);

        BinaryTree *pTree = new BinaryTree(array, 10);

        // 测试前序遍历
        pTree->Traverse(BinaryTree::PREORDER);
        std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
        std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
        std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
        pTree->Traverse(BinaryTree::PREORDER, false);
        
        // 测试中序遍历
        pTree->Traverse(BinaryTree::INORDER);
        std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
        std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
        std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
        pTree->Traverse(BinaryTree::INORDER, false);
        // 测试后序遍历
        pTree->Traverse(BinaryTree::POSTORDER);
        std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
        std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
        std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
        pTree->Traverse(BinaryTree::POSTORDER, false);
        // 测试层序遍历
        pTree->Traverse(BinaryTree::LEVELORDER);

        system("pause");
        
        delete pTree;

        return 0;
    }
    展开全文
  • 非递归先根遍历二叉树 当栈不为空或者当前节点为不为空,执行操作: 从根节点开始,依次访问树最左端的节点并入栈,当节点为空停止入栈。 取栈顶元素为当前节点并出栈,如果当前节点有右子树,则遍历其右子树。 ...

    二叉树的非递归遍历

    • 二叉树的三种遍历方式也可以通过非递归的方法借助栈来实现。
    • 通过控制节点的出栈和入栈先后顺序来实现对树的不同方式的遍历。

    非递归先根遍历二叉树

    • 当栈不为空或者当前节点为不为空,执行操作:
    • 从根节点开始,依次访问树中最左端的节点并入栈,当节点为空停止入栈。
    • 取栈顶元素为当前节点并出栈,如果当前节点有右子树,则遍历其右子树。
    void PreorderPrint(SearchBTree T)       // 先序根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                cout << pT->data << " ";    // 打印当前结点
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S);                  // 若pT为空表示左子树的左孩子全部遍历完,依次出栈
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }

    非递归中根遍历二叉树

    • 当栈不为空或者当前节点为不为空,执行操作:
    • 同样地,先依次将根节点及其左子树最左端的节点入栈,但不进行访问。当节点为空,则停止入栈。
    • 访问栈顶元素作为当前节点并出栈,如果当前节点有右子树,则遍历访问其右子树。
    void InorderPrint(SearchBTree T)        // 中根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S); cout << pT->data << " ";    // 若pT为空表示左子树的左孩子全部遍历完,依次出栈并打印
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }

    非递归后根遍历二叉树

    • 非递归后根遍历相比前两个有点麻烦,需要引入一个中间变量标记已经访问节点。
    • 当栈不为空或者当前节点为不为空,执行操作:
    • 依次将根节点及其左子树的左端节点入栈,但不进行访问,当节点为空,停止入栈。
    • 取栈顶元素作为当前节点,如果当前节点的右孩子(右子树)不为空且其右孩子不是上一次访问的节点。则当前节点变为其右子树,遍历其右子树。如果当前节点的右孩子为空或者其右孩子已经被访问,则访问当前节点,标记当前节点为已访问节点,出栈。将当前节点置为空(此时右孩子访问过了),继续取栈顶元素(为了访问根节点)。
    void PostorderPrint(SearchBTree T)      // 先根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
        TreeNode* qT = nullptr;
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {
                pT = getTop(S);         // 取栈顶元素作为当前结点
                if (pT->right && pT->right != qT)   // 若当前节点有右孩子且不是上一次已经被访问的结点
                {
                    pT = pT->right;     // 指向其右孩子
                }
                else
                {                       // 若当前结点没有右孩子或者未被访问,则
                    Pop(S);             // 出栈
                    cout << pT->data << " ";    // 访问当前结点的数据
                    qT = pT;                    // 令pT记录当前结点,用于稍后判断是否已经被访问过
                    pT = nullptr;               // 将当前结点赋值为空
                }
                    // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }

    附总的代码实现

    #include<iostream>
    using namespace std;
    typedef int ElemType;
    
    typedef struct _TreeNode {  // 定义二叉查找树的结构
        ElemType data;          // 数据
        struct _TreeNode* left;         // 指向左孩子指针
        struct _TreeNode* right;        // 指向其右孩子指针 
    }TreeNode, *SearchBTree;
    
    typedef SearchBTree StackElemType;
    typedef struct StackNode {          // 定义栈的结构(基于链表)
        SearchBTree data;
        StackNode *next;
    }*Stack;
    
    void initStack(Stack St)        // 初始化栈,把头节点看作是栈顶
    {
        St->next = nullptr;
    }
    
    int isEmpty(Stack St)
    {
        return St->next == nullptr;
    }
    
    void Push(Stack St, SearchBTree x)      // 每次从将元素插入到头节点的位置,头节点上移
    {
        StackNode* q = new StackNode;
        q->data = x;
        q->next = St->next;     // q的next域指向St(头节点)的后继结点
        St->next = q;           // St(头节点/栈顶)next域指向q,实现栈往上移
    }
    
    void Pop(Stack St)      // 出栈
    {
        StackNode* p = St->next;        // 临时结点指向头结点(栈顶)的后继结点
        St->next = p->next;     // 栈顶下移
        delete p;           // 释放空间
    }
    
    SearchBTree getTop(Stack St)
    {
        return St->next->data;
    }
    
    SearchBTree EmptyTree(SearchBTree T)    // 初始化、构造一颗空树/销毁一颗树
    {
        if (!T)
        {
            EmptyTree(T->left);     // 递归地释放空间
            EmptyTree(T->right);
            delete T;
        }
        return nullptr;
    }
    
    void Insert(SearchBTree &T, ElemType x)
    {
        if (!T)
        {
            TreeNode* pT = new TreeNode;        // 申请节点空间
            pT->data = x;                       // 为节点赋值
            pT->left = pT->right = nullptr;
            T = pT;                             // 将pT赋给T
        }
        else
        {
            if (x < T->data)                // 如果x小于某个结点的数据
                Insert(T->left, x);         // 递归地在其左子树上寻找空结点插入
            else if (x > T->data)           // 如果x大于某个结点的数据
                Insert(T->right, x);        // 递归地在其左子树上寻找空结点插入
        }
    }
    
    void PreorderPrint(SearchBTree T)       // 先序根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                cout << pT->data << " ";    // 打印当前结点
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S);                  // 若pT为空表示左子树的左孩子全部遍历完,依次出栈
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }
    
    void InorderPrint(SearchBTree T)        // 中根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S); cout << pT->data << " ";    // 若pT为空表示左子树的左孩子全部遍历完,依次出栈并打印
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }
    
    void PostorderPrint(SearchBTree T)      // 先根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
        TreeNode* qT = nullptr;
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {
                pT = getTop(S);         // 取栈顶元素作为当前结点
                if (pT->right && pT->right != qT)   // 若当前节点有右孩子且不是上一次已经被访问的结点
                {
                    pT = pT->right;     // 指向其右孩子
                }
                else
                {                       // 若当前结点没有右孩子或者未被访问,则
                    Pop(S);             // 出栈
                    cout << pT->data << " ";    // 访问当前结点的数据
                    qT = pT;                    // 令pT记录当前结点,用于稍后判断是否已经被访问过
                    pT = nullptr;               // 将当前结点赋值为空
                }
                    // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }
    
    int main()
    {
        const ElemType rawdata[] = { 19, 7, 9, 15, 23, 39, 4, 2, 75, 100, 43, 58 };
        SearchBTree myTree = new TreeNode;
        myTree = EmptyTree(myTree);     // 初始化树
        for (int i = 0;i < sizeof(rawdata) / sizeof(ElemType);i++)
        {
            Insert(myTree, rawdata[i]);     // 向树中插入给定数据
        }
    
        cout << "The inorder print of the tree is: \n";
        InorderPrint(myTree);
        cout << "The preorder print of the tree is: \n";
        PreorderPrint(myTree);
        cout << "The postorder print of the tree is: \n";
        PostorderPrint(myTree);
    
        delete myTree;
        system("pause");
        return 0;
    }
    • 操作运行结果
    The preorder print of the tree is:
    19 7 4 2 9 15 23 39 75 43 58 100
    The inorder print of the tree is:
    2 4 7 9 15 19 23 39 43 58 75 100
    The postorder print of the tree is:
    2 4 15 9 7 58 43 100 75 39 23 19
    展开全文
  • 通过比较二叉树的先根遍历中根遍历,后根遍历的非递归算法可以发现:这三个算法的实现是极其相似的(如同它们递归算法的也很相似一般)。 1:都用到了栈来暂存节点。 2:都是两个while的嵌套循环。 3: ...

     

    后根遍历用到的栈有一些特殊,栈中元素要出栈两次才会被真正出栈。也就是说:

    该栈的链式存储节点的定义如下:

    例如:

    栈的某个节点的skip = 0时,只需执行一次出栈操作即可正常出栈。

    栈的某个节点的skip = 1时,第一次出栈操作只会返回该节点数据域中的数据,第二次出栈操作才会真正的出栈(当然数据域中的数据也返回)

    栈的某个节点的skip = 2时,前两次出栈操作只会返回该节点数据域中的数据,第三次出栈操作才会真正的出栈(当然数据域中的数据也返回)

    ......

     

    通过比较二叉树的先根遍历,中根遍历,后根遍历的非递归算法可以发现:这三个算法的实现是极其相似的(如同它们递归算法的也很相似一般)。

    1:都用到了栈来暂存节点。

    2:都是两个while的嵌套循环。

    3: 如果除去访问节点的语句,先根遍历和中根遍历是完全相同的,后根遍历也只是出栈函数的参数不同而已。

    展开全文
  • 二叉树层次遍历算法——C/C++

    万次阅读 多人点赞 2019-06-16 00:32:47
    在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的节点开始,首先将节点指针入队列,然后从队头取出一个元素,每取一个元素,执行下面两个操作: 访问该元素所指向的节点 若该元素所指节点的左右孩子...

    二叉树层次遍历

    层次遍历基础需要了解二叉树、队列。
    二叉树基本运算:https://blog.csdn.net/weixin_42109012/article/details/92000919
    顺序队基本运算:https://blog.csdn.net/weixin_42109012/article/details/92104948

    1. 算法思想

    用一个队列保存被访问的当前节点的左右孩子以实现层次遍历。
    在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的根节点开始,首先将根节点指针入队列,然后从队头取出一个元素,每取一个元素,执行下面两个操作:

    1. 访问该元素所指向的节点
    2. 若该元素所指节点的左右孩子节点非空,则将该元素所指节点的左孩子指针和右孩子指针顺序入队。此过程不断进行,当队列为空时,二叉树的层次遍历结束。

    2. 原理解释

    2.1. 二叉树图

    一个二叉树,层次遍历就是每一行每一行的取出数据。
    这个图的结果就是 ABCDEFGH
    在这里插入图片描述

    2.2. 层次遍历过程图

    就是先父节点进入队列,然后循环,出队时带入下一组子节点进队,没有就没有进入队列的,当队列为空时结束循环。
    在这里插入图片描述

    3. 代码实现

    3.1 实现步骤

    1、首先将二叉树的根节点进入队列中,判断队列不为NULL。
    2、打印输出该节点存储的元素。
    3、判断节点如果有孩子(左孩子、右孩子),就将孩子进入队列中。
    4、循环以上操作,直到 BT->lchild == NULL、BT->rchild=NULL。

    3.2 全部代码

    #define _CRT_SECURE_NO_WARNINGS // VS忽略警告,其它应该不需要
    
    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_SIZE 128
    #define STR_SIZE 1024
    
    typedef struct Node {    // 定义二叉链
        char         data;   // 数据元素
        struct Node* lchild; // 指向左孩子节点
        struct Node* rchild; // 指向右孩子节点
    } BTNode;                // struct Node 的别名
    
    typedef struct Quene {      // 定义顺序队
        int     front;          // 队头指针
        int     rear;           // 队尾指针
        BTNode* data[MAX_SIZE]; // 存放队中元素
    } SqQueue;                  // struct Queue 的别名
    
    /**
     * 队列函数
     */
    void initQueue(SqQueue** q);             // 初始化队列
    bool emptyQueue(SqQueue* q);             // 判断队列空
    bool enQueue(SqQueue* q, BTNode* node);  // 入队
    bool deQueue(SqQueue* q, BTNode** node); // 出队
    
    /**
     * 二叉树函数
     */
    // void createBTNode2(BTNode** BT);                  // 创建二叉树
    int  createBTNode(BTNode** BT, char* str, int n); // 创建二叉树
    void preOrder(BTNode* BT);                        // 前序遍历
    void inOrder(BTNode* BT);                         // 中序遍历
    void postOrder(BTNode* BT);                       // 后序遍历
    void levelOrder(BTNode* BT);                      // 层次遍历
    
    /**
     * 画树函数
     */
    void draw_level(BTNode* node, bool left, char* str); // 画分支
    void draw(BTNode* root);                             // 画根节点
    
    /***************************************************************************
     * @date    2019/12/08
     * @brief   层次遍历二叉树
     * @param   BT  二叉树根节点
     ***************************************************************************/
    void levelOrder(BTNode* BT) {
        SqQueue* q;       // 定义队列
        initQueue(&q);    // 初始化队列
        if (BT != NULL) { // 根节点指针进队列
            enQueue(q, BT);
        }
        // 一层一层的把节点存入队列,当没有孩子节点时就不再循环
        while (!emptyQueue(q)) {      // 队不为空循环
            deQueue(q, &BT);          // 出队时的节点
            printf("%c", BT->data);   // 输出节点存储的值
            if (BT->lchild != NULL) { // 有左孩子时将该节点进队列
                enQueue(q, BT->lchild);
            }
            if (BT->rchild != NULL) { // 有右孩子时将该节点进队列
                enQueue(q, BT->rchild);
            }
        }
    }
    
    int main() {
        // 例子:ABDH###E##CF##G##
        BTNode* BT;
        printf("请输入字符串:");
        char* str = (char*)malloc(sizeof(char) * STR_SIZE);
        scanf("%s", str);
        if (strlen(str) == createBTNode(&BT, str, 0)) {
            printf("二叉树建立成功\n");
        }
        // printf("请输入字符串:");
        // createBTNode2(&BT);
        // draw(BT);
    
        printf("\n先序遍历结果:");
        preOrder(BT);
    
        printf("\n中序遍历结果:");
        inOrder(BT);
    
        printf("\n后序遍历结果:");
        postOrder(BT);
    
        printf("\n层序遍历结果:");
        levelOrder(BT);
    
        return 0;
    }
    
    // 初始化队列
    void initQueue(SqQueue** q) {
        if (!((*q) = (SqQueue*)malloc(sizeof(SqQueue)))) {
            printf("内存分配失败!");
            exit(-1);
        }
        (*q)->front = (*q)->rear = -1; // 置 -1
    }
    
    // 判断队列是否为空
    bool emptyQueue(SqQueue* q) {
        // 首指针和尾指针相等,说明为空。空-返回真,不空-返回假
        if (q->front == q->rear) {
            return true;
        }
        return false;
    }
    
    // 进队列
    bool enQueue(SqQueue* q, BTNode* node) {
        // 判断队列是否满了。满(插入失败)-返回假,不满(插入成功)-返回真
        if (q->rear == MAX_SIZE - 1) {
            return false;
        }
        q->rear++;               // 头指针加 1
        q->data[q->rear] = node; // 传值
        return true;
    }
    
    // 出队列
    bool deQueue(SqQueue* q, BTNode** node) {
        // 判断是否空了。空(取出失败)-返回假,不空(取出成功)-返回真
        if (q->front == q->rear) {
            return false;
        }
        q->front++;                // 尾指针加 1
        *node = q->data[q->front]; // 取值
        return true;
    }
    
    // 创建二叉树
    int createBTNode(BTNode** BT, char* str, int n) {
        char ch = str[n++];  // 把第 n 个字符赋给ch,方便后面判断,字符下标后移
        if (ch != '\0') {    // 如果 ch 不等于结束符就继续创建,否则就结束
            if (ch == '#') { // 以 # 号代表 NULL,下面没有了
                *BT = NULL;
            } else {
                if (!(*BT = (BTNode*)malloc(sizeof(BTNode)))) {
                    printf("内存分配失败!");
                    exit(-1);
                } else {
                    (*BT)->data = ch;
                    n           = createBTNode(&((*BT)->lchild), str, n); // 左递归创建
                    n           = createBTNode(&((*BT)->rchild), str, n); // 右递归创建
                }
            }
        }
        // 返回 n,记录字符串使用到哪里了
        return n;
    }
    // 创建二叉树
    // void createBTNode2(BTNode** BT) {
    //     char ch;
    //     ch = getchar();
    //     if (ch == '#') {
    //         *BT = NULL;
    //     } else {
    //         if (!(*BT = (BTNode*)malloc(sizeof(BTNode)))) {
    //             printf("内存分配失败!");
    //             return;
    //         } else {
    //             (*BT)->data = ch;
    //             createBTNode2(&((*BT)->lchild)); // 分配成功则接着建立左子树和右子树
    //             createBTNode2(&((*BT)->rchild));
    //         }
    //     }
    // }
    
    // 先序遍历
    void preOrder(BTNode* BT) {
        if (BT != NULL) {           // 判断不为空
            printf("%c", BT->data); // 访问根节点
            preOrder(BT->lchild);   // 递归,先序遍历左子树
            preOrder(BT->rchild);   // 递归,先序遍历右子树
        }
    }
    
    // 中序遍历
    void inOrder(BTNode* BT) {
        if (BT != NULL) {
            inOrder(BT->lchild);
            printf("%c", BT->data);
            inOrder(BT->rchild);
        }
    }
    
    // 后序遍历
    void postOrder(BTNode* BT) {
        if (BT != NULL) {
            postOrder(BT->lchild);
            postOrder(BT->rchild);
            printf("%c", BT->data);
        }
    }
    
    /*****************************************************************************
    * @date   2020/4/19
    * @brief  水平画树
    * @param  node	二叉树节点
    * @param  left	判断左右
    * @param  str 	可变字符串
    *****************************************************************************/
    void draw_level(BTNode* node, bool left, char* str) {
        if (node->rchild) {
            draw_level(node->rchild, false, strcat(str, (left ? "|     " : "      ")));
        }
    
        printf("%s", str);
        printf("%c", (left ? '\\' : '/'));
        printf("-----");
        printf("%c\n", node->data);
    
        if (node->lchild) {
            draw_level(node->lchild, true, strcat(str, (left ? "      " : "|     ")));
        }
        //  "      " : "|     " 长度为 6
        str[strlen(str) - 6] = '\0';
    }
    
    /*****************************************************************************
    * @date   2020/4/19
    * @brief  根节点画树
    * @param  root	二叉树根节点
    *****************************************************************************/
    void draw(BTNode* root) {
        char str[STR_SIZE];
        memset(str, '\0', STR_SIZE);
    
        /**
         * 1. 在 windows 下,下面是可执行的
         * 2. 在 Linux   下,执行会报 Segmentation fault
         *      需要使用中间变量
         */
        if (root->rchild) {
            draw_level(root->rchild, false, str);
        }
        printf("%c\n", root->data);
        if (root->lchild) {
            draw_level(root->lchild, true, str);
        }
    }
    

    4. 结果展示

    创建二叉树是以 “#” 为结束符NULL。
    例子就是最上面的图:ABDH###E##CF##G##
    结果应该为:ABCDEFGH
    在这里插入图片描述

    展开全文
  • 二叉树遍历算法

    千次阅读 2019-10-27 01:02:12
    前言 二叉树的遍历是指从节点触发,按照某种次序依次访问二叉树所有的节点。 由于不同于线性结构,...下面的遍历算法用Python实现,不会Python的同学不用担心,因为算法逻辑很简单。 先看下我们的节点对象的定...
  • 遍历算法应用.pdf

    2020-03-16 21:25:47
    二叉树的遍历运算是一个重要的基础一是重点理解访问结点操作的含义二 是注意对具体的实现时是否需要考虑遍历的次序选择要求 1输出二叉树中的结点 算法思想 输出二叉树中的结点并无次序要求因此可用三种遍历算法中...
  • 二叉树遍历方法 、前序遍历算法 、中序遍历算法 、后序遍历算法 、层序遍历算法
  • 6.4遍历算法应用

    2020-07-03 10:26:47
    输出二叉树中的结点并无次序要求,因此可用三种遍历算法中的任何一种 完成,只需将访问操作具体变为输出操作即可。 下面给出采用先序遍历实现的算法。 【算法描述】 /* 先序遍历输出二叉树结点, root 为指向二叉树根...
  • //先根遍历右子树 } } //中根遍历二叉树的递归算法 public void inRootTraverse(BiTreeNode T) { if(T!=null) { inRootTraverse(T.lchild); //中根遍历左子树 System.out.print(T.data); //访问根...
  • 二叉树遍历算法实现

    2017-11-01 18:59:52
    二叉树的三种常见遍历方式:先根遍历中根遍历、后根遍历。 二叉树节点结构体如下: struct node //根节点结构体 { char name; Node* parent; Node* left_child; Node* right_child; }; 定义三个遍历函数: void ...
  • 二叉树遍历算法总结

    万次阅读 2016-03-20 18:43:19
    二叉树遍历算法总结    A. 二叉树的遍历  1.前序遍历二叉树:  (1)若二叉树为空,则为空操作,返回空。  (2)访问结点。  (3)前序遍历左子树。  (4)前序遍历右子树。  a.二叉树前序遍历的递归算法: ...
  • Python算法系列—深度优先遍历算法【二叉树】

    千次阅读 多人点赞 2020-04-14 17:14:12
    深度优先遍历算法之二叉树一、什么是深度优先遍历二、二叉树1. 二叉树简介2.二叉树类型3.二叉树相关术语4. 二叉树的节点代码5. 二叉树遍历顺序6.深度优先遍历和广度优先遍历三、面试题+励志 ``这不就是二叉树吗?嗯...
  • 二叉树的7种遍历算法

    2020-10-09 00:13:12
    二叉树的7种遍历算法
  • 二叉树遍历是非常经典的算法题,也是二叉树的一道基础算法题。 但是在平常的笔试面试,其出现的频率其实并不是特别的高,我推测是这种题目相对来说比较基础,算是一个基础知识点。 比如剑指offer出现的后序遍历...
  • 二叉树遍历算法之一:前序遍历

    千次阅读 2015-12-07 20:14:26
    当调用遍历算法的时候前序遍历的具体过程如下: 首先访问节点,如果节点不为空,执行输出语句,打印节点的值。 如果左子树不为空,则访问节点的左孩子,并输出节点做孩子的值 继续访问节点的左孩子的左...
  • 实现二叉树各种遍历算法

    千次阅读 多人点赞 2019-01-24 11:22:07
    * 实现二叉树各种遍历算法 * 实验目的: * 领会二叉树的各种遍历过程以及遍历算法设计 * 实验内容: * 设计程序,实现二叉树的先序遍历、中序遍历和后序遍历的 * 递归和非递归算法,以及层次遍历的算法。 */ #include...
  • 图解二叉树先根、根、后根遍历

    千次阅读 2020-09-02 09:23:17
    先根、根、后根遍历 三种遍历都是递归遍历 先根遍历 结果:ABCDEFGH 原理:先遍历根节点,再遍历左子树,最后遍历右子树; 中根遍历 结果:CBEDFAGH 原理:先遍历左子树,再遍历根节点,最后遍历右子树; 后...
  • 今天把二叉树的非递归遍历算法复习了下,在这总结下。 三个算法都使用了栈,中序和前序遍历算法大致相同,而后序遍历稍微复杂一点。 先写中序遍历。 //S是 栈,存储结点,t是树的结点 Inorder(t) //...
  • 二叉树层次遍历算法

    千次阅读 2020-08-27 01:23:39
    在二叉树,我们常见的遍历方式 主要有四种。分别是: 前序遍历节点->左节点->右节点) 中序遍历(左节点->节点->右节点) 后序遍历(左节点->右节点->节点) 层次遍历 其实记住以上的...
  • 二叉树遍历算法 二叉树的存储结构 typedef struct BTNode { char data; //这里默认结点data为char型 struct BTNode *lchild; struct BTNode *rchild; }BTNode; 二叉树的遍历算法 1 先序遍历 先序遍历的操作...
  • 文章目录二叉树的遍历算法 二叉树的遍历算法
  • 1、 定义左儿子—右兄弟链接存储的树类和森林类。 2、 实验验证如下算法的正确性、各种功能及指标: 1)创建树和森林; 2)树和森林的先根遍历的递归和迭代算法;... 4)树和森林的层次遍历算法
  • java二叉树的遍历算法

    2015-10-22 19:16:42
    java二叉树的遍历算法   转载▼ 今天练习用java实现二叉树的遍历算法,首先我先编写二叉树类BinaryTree,代码如下: package package2; public class BinaryTree {    int data; //节点数据 ...
  • 用java实现二叉树的遍历算法 用java实现二叉树的遍历算法,编写二叉树类BinaryTree 代码如下: package package2; public class BinaryTree { int data; //节点数据 BinaryTree left; //左子树 BinaryTree right; ...
  • 二叉树的遍历算法

    2020-12-27 15:52:44
    二叉树的遍历是指从节点出发,按照某种次序依次访问二叉树所有结点,使得每个结点被访问一次且仅被访问一次。 2. 前序遍历 遍历的顺序为:ABDGHCEIF 排序算法: /*二叉树的前序遍历递归算法*/ void ...
  • 从二叉树的递归定义可知,一棵非空的二叉树由结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作: (1)访问结点本身(N), (2)遍历该结点的左子树(L), (3)遍历该...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 137,597
精华内容 55,038
关键字:

中根遍历的算法