BFS的应用

谁借莪１个温暖的怀抱￠ 2022-09-25 15:23 119阅读 0赞

# BFS在二叉树上的应用 #

## 二叉树的层次遍历 ##

// 一颗二叉树
             1
           /    \
          2      3
        /   \   /  \
       4     5 6    7

// 按照层次遍历的要求，把结果输出到一行中
    void levelTraverse(BTree tree)
    {
        queue<BTree> qTree;
        if (tree)
        {
            qTree.push(tree);
        }
        while (!qTree.empty())
        {
            // 根节点出队，访问根节点
            BTree curTree = qTree.front();
            qTree.pop();
            cout << curTree->value << " ";
    
            // 左子节点不为空，入队
            if (curTree->left)
                qTree.push(curTree->left);
            // 右子节点不为空，入队
            if (curTree->right)
                qTree.push(curTree->right);
        }
        cout << endl;
    }
    
    // 输出结果
    ////////////////////////
    // 1 2 3 4 5 6 7 
    ////////////////////////

// 按照层次遍历的要求，每一层单独输出一行
    void levelTraverse(BTree tree)
    {
        queue<BTree> qTree;
        if (tree)
        {
            qTree.push(tree);
        }
        while (!qTree.empty())
        {
            int size = qTree.size();
            for (int i = 0; i < size; i++) {
                BTree curTree = qTree.front();
                qTree.pop();
                cout << curTree->val << " ";
                // 左子节点不为空，入队
                if (curTree->left)
                    qTree.push(curTree->left);
                // 右子节点不为空，入队
                if (curTree->right)
                    qTree.push(curTree->right);
            }
            cout << endl;
        }
    }
    
    // 输出结果
    ///////////////////////
    // 1
    // 2 3
    // 4 5 6 7
    ///////////////////////

## 一颗二叉树从右边看，输出可以看到的节点 ##

// 一颗二叉树
             1          <--- 只能看到1
           /    \
          2      3      <--- 只能看到3,2 被 3 挡住
        /   \   /  \
       4     5 6    7   <--- 只能看到7， 4 5 6 被 7 挡住

void canSeeNode(BTree tree)
    {
        queue<BTree> qTree;
        if (tree)
        {
            qTree.push(tree);
        }
        while (!qTree.empty())
        {
            cout << qTree.back()->value << " ";
            int size = qTree.size();
            for (int i = 0; i < size; i++) {
                BTree curTree = qTree.front();
                qTree.pop();
                // 左子节点不为空，入队
                if (curTree->left)
                    qTree.push(curTree->left);
                // 右子节点不为空，入队
                if (curTree->right)
                    qTree.push(curTree->right);
            }
        }
        cout << endl;
    }