关于数据结构的知识整理

作者:陈劲灿 编辑日期: 2017年10月13日 14:17 阅读量: 351 分类: algorithm
二叉树的数据结构
  1.
  2.
  3.
  4.
  5.
  6.
  7.
  8.
  9.
 10.
 11.
 12.
 13.
 14.
 15.
 16.
 17.
 18.
 19.
 20.
 21.
 22.
 23.
 24.
 25.
 26.
 27.
 28.
 29.
 30.
 31.
 32.
 33.
 34.
 35.
 36.
 37.
 38.
 39.
 40.
 41.
 42.
 43.
 44.
 45.
 46.
 47.
 48.
 49.
 50.
 51.
 52.
 53.
 54.
 55.
 56.
 57.
 58.
 59.
 60.
 61.
 62.
 63.
 64.
 65.
 66.
 67.
 68.
 69.
 70.
 71.
 72.
 73.
 74.
 75.
 76.
 77.
 78.
 79.
 80.
 81.
 82.
 83.
 84.
 85.
 86.
 87.
 88.
 89.
 90.
 91.
 92.
 93.
 94.
 95.
 96.
 97.
 98.
 99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
template<typename DataType>
class BinaryTree
{
    typedef BinaryTree<DataType> Node;

public:
    DataType m_data;
    Node* m_parent;
    Node* m_left;
    Node* m_right;

    BinaryTree() {
        m_parent = nullptr;
        m_left = nullptr;
        m_right = nullptr;
    }

    BinaryTree(DataType p_data) {
        m_data = p_data;
        m_parent = nullptr;
        m_left = nullptr;
        m_right = nullptr;
    }

    ~BinaryTree() {
        Destory();
    }

    void Destory() {
        if (m_left)
            delete m_left;
        m_left = nullptr;

        if (m_right)
            delete m_right;
        m_right = nullptr;
    }

    int Count() {
        int c = 1;
        if (m_left)
            c += m_left->Count();
        if (m_right)
            c += m_right->Count();
        return c;
    }
};

//前序遍历
template<typename DataType>
void Preorder(BinaryTree<DataType>* p_node, void(* p_process)(BinaryTree<DataType>*))
{
    if (!p_node)
        return;
    p_process(p_node);

    if (p_node->m_left)
        Preorder(p_node->m_left);
    if (p_node->m_right)
        Preorder(p_node->m_right);
}

//中序遍历
template<typename DataType>
void Inorder(BinaryTree<DataType>* p_node, void(* p_process)(BinaryTree<DataType>*))
{
    if (!p_node)
        return;

    if (p_node->m_left)
        Inorder(p_node->m_left);

    p_process(p_node);

    if (p_node->m_right)
        Inorder(p_node->m_right);
}

//后序遍历
template<typename DataType>
void Postorder(BinaryTree<DataType>* p_node, void(*p_process)(BinaryTree<DataType>*))
{
    if (!p_node)
        return;

    if (p_node->m_left)
        Postorder(p_node->m_left);

    if (p_node->m_right)
        Postorder(p_node->m_right);

    p_process(p_node);
}

//获取二叉树深度
template<typename DataType>
int GetDepth(BinaryTree<DataType>* p_root)
{
    int left = -1;
    int right = -1;

    if (p_root->m_left)
        left = GetDepth(p_root->m_left);
    if (p_root->m_right)
        right = GetDepth(p_root->m_right);

    return (left > right ? left : right) + 1;
}

//翻转二叉树
template<typename DataType>
void InvertBinaryTree(BinaryTree<DataType>* p_root)
{
    if (!p_root)
        return;

    InvertBinaryTree(p_root->m_left);
    InvertBinaryTree(p_root->m_right);

    BinaryTree<DataType>* tmpNode = p_root->m_left;
    p_root->m_left = p_root->m_right;
    p_root->m_right = tmpNode;
}

使用Vector或者List来实现简单的stack
 1.
 2.
 3.
 4.
 5.
 6.
 7.
 8.
 9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
#include <iostream>
#include <list>
#include <vector>

template<typename DataType>
class VStack
{
public:
    void Push(DataType p_data) {
        m_datas.push_back(p_data);
    }

    void Pop() {
        m_datas.pop_back();
    }

    DataType& Top() {
        return m_datas.back();
    }

    int Count() {
        return m_datas.size();
    }

    std::vector<DataType> m_datas;
};

template<typename DataType>
class LStack
{
public:
    void Push(DataType p_data) {
        m_datas.push_back(p_data);
    }

    void Pop() {
        m_datas.pop_back();
    }

    DataType& Top() {
        return m_datas.back();
    }

    int Count() {
        return m_datas.size();
    }

    std::list<DataType> m_datas;
};

int main() {
    LStack<int>* ls = new LStack<int>(); //此处可以替换为LStack
    ls->Push(32);
    ls->Push(43);
    ls->Push(1);
    ls->Push(544);

    while (ls->Count() > 0) {
        std::cout << ls->Top() << std::endl;
        ls->Pop();
    }
    system("pause");
    return 0;
}

使用vector或者list实现简单的Queue
 1.
 2.
 3.
 4.
 5.
 6.
 7.
 8.
 9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
#include <iostream>
#include <vector>
#include <list>

template<typename DataType>
class LQueue 
{
public:
    void Enqueue(DataType p_data) {
        m_datas.push_back(p_data);
    }

    void Dequeue() {
        m_datas.pop_front();
    }

    DataType& Front() {
        return m_datas.front();
    }

    int Count() {
        return m_datas.size();
    }

    std::list<DataType> m_datas;
};

template<typename DataType>
class VQueue 
{
public:
    void Enqueue(DataType p_data) {
        m_datas.push_back(p_data);
    }

    void Dequeue() {
        int size = m_datas.size();
        for (int i = 1; i < size; ++i) {
            m_datas[i - 1] = m_datas[i];
        }
        m_datas.resize(size - 1);
    }

    DataType& Front() {
        return m_datas.front();
    }

    int Count() {
        return m_datas.size();
    }

    std::vector<DataType> m_datas;
}; 

int main() {
    VQueue<int>* lq = new VQueue<int>();
    lq->Enqueue(32);
    lq->Enqueue(43);
    lq->Enqueue(23);
    lq->Enqueue(53);

    while (lq->Count() > 0) {
        std::cout << lq->Front() << std::endl;
        lq->Dequeue();
    }

    system("pause");
    return 0;
}

上一篇
下一篇
TypeScript的入门-环境搭建
TensorFlow的深度学习文章->_->先导篇

asdfds