c++经典例题之先序二叉树的构建

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
#include <iostream>
#include <string>
#include <queue>
using namespace std;

template<typename T >class BinaryTree;
template <typename T> class BinaryTreeNode {
public:
    friend class BinaryTree<T>;
    BinaryTreeNode() {
        data = NULL;
        lChild = rChild = NULL;
    }
    BinaryTreeNode(T newdata) {
        this->data = newdata;
        lChild = rChild = NULL;
    }
    T getData() {
        return data;
    }
    BinaryTreeNode<T> * getLeftNode() {
        return lChild;
    }
    BinaryTreeNode<T> * getRightNode() {
        return rChild;
    }
    T data;
    BinaryTreeNode<T>* lChild;
    BinaryTreeNode<T>* rChild;
private:

};

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
124
template <typename T> class BinaryTree {
public:
    BinaryTreeNode<T> *root;
    char* p;
    BinaryTree() { root = NULL; }
    BinaryTree(T data) {
        root = new BinaryTreeNode<T>(data);
        root->lChild = NULL;
        root->rChild = NULL;
    }
    ~BinaryTree() {
        delete root;
    }

    //构建二叉树并返回
    BinaryTreeNode<T>* CreateTree() {
        BinaryTreeNode<int>* bt = NULL;
        char t;
        cin >> t;
        if (t == '#')
        {
            return NULL;
        }
        else {
            int num = t - '0';
            bt = new BinaryTreeNode<T>(num);
            bt->lChild = CreateTree();
            bt->rChild = CreateTree();
        }
        return bt;
    }

    //先序构建二叉树
    BinaryTreeNode<T>* PreCreateTree() {
        BinaryTreeNode<int>* bt = NULL;
        if (this->root == NULL)
        {
            cout << "请输入根节点（#代表空树）:";
        }
        else {
            cout << "请输入节点（#代表空树）:";
        }
        char t;
        cin >> t;
        if (t == '#')
        {
            return NULL;
        }
        else {
            int num = t - '0';
            bt = new BinaryTreeNode<T>(num);
            if (this->root == NULL)
            {
                this->root = bt;
            }
            cout << bt->data << "的左孩子";
            bt->lChild = PreCreateTree();

            cout << bt->data << "的右边孩子";
            bt->rChild = PreCreateTree();
        }
        return bt;
    }   

    void preOderTraversal(BinaryTreeNode<T> *bt);  //先序遍历
    void inOrderTraversal(BinaryTreeNode<T> *bt);  //中序遍历
    void postOrderTraversal(BinaryTreeNode<T> *bt);//后序遍历
    void levelTraversal(BinaryTreeNode<T> *bt);    //逐层遍历

private:

};

template <typename T>
void BinaryTree<T>::preOderTraversal(BinaryTreeNode<T> *bt) {
    if (bt)
    {
        cout << bt->data;
        BinaryTree<T>::preOderTraversal(bt->getLeftNode());
        BinaryTree<T>::preOderTraversal(bt->getRightNode());
    }
}

template <typename T>
void BinaryTree<T>::inOrderTraversal(BinaryTreeNode<T> *bt) {
    if (bt)
    {
        BinaryTree<T>::inOrderTraversal(bt->getLeftNode());
        cout << bt->data;
        BinaryTree<T>::inOrderTraversal(bt->getRightNode());
    }
}

template <typename T>
void BinaryTree<T>::postOrderTraversal(BinaryTreeNode<T> *bt) {
    if (bt)
    {
        BinaryTree<T>::postOrderTraversal(bt->getLeftNode());
        BinaryTree<T>::postOrderTraversal(bt->getRightNode());
        cout << bt->data;
    }
}

template <typename T>
void BinaryTree<T>::levelTraversal(BinaryTreeNode<T> *bt) {

    queue<BinaryTreeNode<T>*> que;
    que.push(bt);
    while (!que.empty())
    {
        BinaryTreeNode<T>* proot = que.front();
        que.pop();
        cout << proot->data;

        if (proot->lChild != NULL)
        {
            que.push(proot->lChild);//左孩子入队
        }
        if (proot->rChild != NULL)
        {
            que.push(proot->rChild);//右孩子入队
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "pch.h"
#include <iostream>
#include "BinaryTree.h"

int main()
{
    //场景测试2
    BinaryTree<int> btree;
    btree.PreCreateTree();//先序构建二叉树
    cout << "先序遍历:";
    btree.preOderTraversal(btree.root); cout << endl;//先序遍历    
    cout << "中序遍历:";
    btree.inOrderTraversal(btree.root); cout << endl;//中序遍历
    cout << "后序遍历:";
    btree.postOrderTraversal(btree.root); cout << endl;//后序遍历
    cout << "逐层序遍历:";
    btree.levelTraversal(btree.root);

}