数据结构：树

CommonInc.h

 1 #pragma once
 2 #include <iostream>
 3 #include <vector>
 4 #include <deque>
 5 #include <stack>
 6 
 7 // BFS 使用了deque
 8 // DFS 使用了递归,什么时候使用了stack
 9 // DFS 不使用递归
10 // 创建前驱节点和后驱节点
11 
12 // 前序中序和后序
13 
14 using namespace std;
15 template<typename T>
16 struct Node
17 {
18     Node(T data)
19     {
20         this->data = data;
21         left = right = nullptr;
22     }
23     T data;
24     Node* left;
25     Node* right;
26 };
27 using IntNode = Node<int>;
28 using CharNode = Node<char>;

View Code

BinTree(二叉树的遍历，递归和非递归)

#include "CommonInc.h"
//Broad First Search
void BFS(IntNode* root)
{
    if (root == nullptr) return;
    deque<IntNode*> dqNodes;
    dqNodes.push_back(root);
    IntNode* tmpNode;
    while (dqNodes.size() > 0)
    {
        tmpNode = dqNodes.front();
        cout << tmpNode->data << endl;
        if (tmpNode->left != nullptr)
        {
            dqNodes.push_back(tmpNode->left);
        }
        if (tmpNode->right != nullptr)
        {
            dqNodes.push_back(tmpNode->right);
        }
        dqNodes.pop_front();
    }
}
//递归
void DFS_Recursive(IntNode* node)
{
    if (node == nullptr)    return;
    cout << node->data << endl;
    if (node->left != nullptr)
        DFS_Recursive(node->left);
    if (node->right != nullptr)
        DFS_Recursive(node->right);
}
//中序
void DFS_Recursive_Mid(IntNode* node)
{
    if (node == nullptr)    return;
    if (node->left != nullptr)
        DFS_Recursive(node->left);
    cout << node->data << endl;
    if (node->right != nullptr)
        DFS_Recursive(node->right);
}

//这一块逻辑不清晰
//没有使用递归借助了两个容器， 有问题：每一次添加到vector中都对其进行了判定
void DFS(IntNode* root)
{
    if (root == nullptr)    return;
    stack<IntNode*> skNodes;
    vector<IntNode*> vctNodes;
    IntNode* tmpNode = nullptr;
    bool bLeft = true;
    vctNodes.push_back(root);
    skNodes.push(root);
    bool bSearched = false;
    while (skNodes.size() > 0)
    {
        tmpNode = skNodes.top();
        bSearched = false;
        if (tmpNode->left != nullptr)
        {
            if (std::find(vctNodes.begin(), vctNodes.end(), tmpNode->left) == vctNodes.end())
            {
                skNodes.push(tmpNode->left);
                vctNodes.push_back(tmpNode->left);
                bSearched = true;
                continue;
            }
        }
        //最近弹出的节点为左子节点，那么判断右子节点
        if (tmpNode->right != nullptr)
        {
            if (std::find(vctNodes.begin(), vctNodes.end(), tmpNode->right) == vctNodes.end())
            {
                skNodes.push(tmpNode->right);
                vctNodes.push_back(tmpNode->right);
                bSearched = true;
                continue;
            }
        }
        if (tmpNode->left == nullptr && tmpNode->right == nullptr)
        {
            skNodes.pop();
        }
        else if (!bSearched)
        {
            skNodes.pop();
        }
    }

    for (int i = 0; i < vctNodes.size(); i++)
    {
        cout << vctNodes[i]->data << endl;
    }
}

//  15 - 23 - 44
//            - 25 - 32
//                 - 16

int maind()
{
    IntNode* root = new IntNode(15);
    IntNode* node = new IntNode(23);
    root->left = node;
    node->left = new IntNode(44);
    node->right = new IntNode(25);
    node = node->right;
    IntNode* node1 = new IntNode(32);
    IntNode* node2 = new IntNode(16);
    node->left = node1;
    node->right = node2;

    //BFS(root);
    DFS_Recursive_Mid(root);
    cout << "-----------------------------------------" << endl;
    DFS(root);
    return 0;
}

View Code

二叉树的前序中序和后序遍历

//所谓的前中后续遍历 都是基于深度优先
//打印的话 如果先打印则为前序
// 访问完左节点，再打印  则为中序
// 左右节点访问后，再打印则为后序遍历
//前序
void DSF_Prev(CharNode* node)
{
    if (node == nullptr)    return;
    cout << node->data;
    if (node->left != nullptr)
        DSF_Prev(node->left);
    if (node->right != nullptr)
        DSF_Prev(node->right);
}
//中序
void DSF_Mid(CharNode* node)
{
    if (node == nullptr)    return;
    if (node->left != nullptr)
        DSF_Mid(node->left);
    cout << node->data;
    if (node->right != nullptr)
        DSF_Mid(node->right);
}
//后序
void DSF_Next(CharNode* node)
{
    if (node == nullptr)    return;
    if (node->left != nullptr)
        DSF_Prev(node->left);
    if (node->right != nullptr)
        DSF_Prev(node->right);
    cout << node->data;
}


int main()
{
    CharNode* root = new CharNode('A');
    CharNode* left = new CharNode('B');
    CharNode* right = new CharNode('C');
    root->left = left;
    root->right = right;
    left->left = new CharNode('D');
    left->right = new CharNode('E');
    CharNode* cur = left->left;
    cur->left = new CharNode('H');
    cur->right = new CharNode('I');
    cur = left;
    cur->right = new CharNode('E');
    cur->right->left = new CharNode('J');

    cur = right;
    cur->left = new CharNode('F');
    cur->right = new CharNode('G');

    DSF_Prev(root);
    cout << endl;
    DSF_Mid(root);
    cout << endl;
    DSF_Next(root);
    return 0;
}

View Code