二叉树的定义和递归实现_递归满二叉树实现递归定义

1.树的相关概念

1.1基本慨念

  (1)节点：结点包含数据和指向其它节点的指针。  

  (2)根节点：树第一个结点称为根节点。  

  (3)结点的度：结点拥有的子节点个数。  

  (4)叶节点：没有子节点的节点(度为0)。  

  (5)父子节点：一个节点father指向另一个节点child，则child为孩子节点，father为父亲节点。  

  (6)兄弟节点：具有相同父节点的节点互为兄弟节点。  

  (7)节点的祖先：从根节点开始到该节点所经的所有节点都可以称为该节点的祖先。  

  (8)子孙：以某节点为根的子树中任一节点都称为该节点的子孙。 

  (9)树的高度：树中距离根节点最远节点的路径长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.2 二叉树的定义

满足以下两个条件的树结构称为二叉树：

   （1）每个结点的度不大于2。
   （2）每个节点的孩子结点次序不能任意颠倒。
1
2

二叉树的五种基本形态：

1.3完全二叉树和满二叉树

   在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且叶子结点都在同一层上，这样的二叉树称作满二叉树。一棵深度为k且由2^k-1个结点的二叉树称为满二叉树。
   如果一棵具有n个结点的二叉树的结构与满二叉树的前n个结点的结构相同，这样的二叉树称作完全二叉树。
1
2

注：满二叉树一定是完全二叉树而完全二叉树不一定是满二叉树

1.4二叉树的性质

1.5二叉树的链式存储

2 二叉树的递归实现

2.1创建二叉树的递归过程示例

2.2代码：

//BinaryTree.hpp

#pragma once
template <class T>
struct BinaryTreeNode
{
    T _data;
    BinaryTreeNode<T>* _left;    //左孩子
    BinaryTreeNode<T>* _right;  // 右孩子
    BinaryTreeNode(const T& x)
        :_left(NULL)
        , _right(NULL)
        , _data(x)
    {}
};

template <class T>
class BinaryTree
{
public:
    typedef BinaryTreeNode<T> Node;
    //构造
    BinaryTree()
        :_root(NULL)
    {
    }
    //用一个数组创建一个二叉树
    BinaryTree(T* a,size_t n, const T& invalid)
    {
            size_t index = 0;
            _root = CreatBinaryTree(a, n, invalid, index);
    }

    //创建二叉树为先序遍历
    //index必须取引用的原因:当数组中的元素为非法值时,index的值并没有改变
    Node* CreatBinaryTree(T* a, size_t n, const T& invalid, size_t& index)
    {
        Node* _root = NULL;
        if ((a[index] != invalid)&& index < n )
        {
            _root = new Node(a[index]);
            _root->_left = CreatBinaryTree(a, n, invalid, ++index);
            _root->_right = CreatBinaryTree(a, n, invalid, ++index);
        }
        return _root;
    }


    Node* CreatBinaryTree(Node* root) 
    {
        Node* _root = NULL;
        if (root !=NULL )
        {
            _root = new Node(root->_data);
            _root->_left = CreatBinaryTree(root->_left);
            _root->_right = CreatBinaryTree(root->_right);
        }
        return _root;
    }
    //拷贝构造
    BinaryTree(const BinaryTree<T>& root)
    {
        _root = CreatBinaryTree(root._root);
    }

    BinaryTree<T>& operator=(const BinaryTree<T>& root)
    {
        if (_root != root._root)
        {
            this->~BinaryTree();
            _root = CreatBinaryTree(root._root);
        }
        return *this;
    }


    //析构函数  一个一个结点析构
    ~BinaryTree()
    {
        if (_root)
        {
            Destroy(_root);
        }
    }
    //遍历总是先遍历左子树,再遍历右子树,先中后只是根的顺序不同罢了
    //先序遍历  dlr

    void PrevOrder()
    {
        _PrevOrder(_root);
        cout << endl;
    }

    //中序遍历 ldr

    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }

    //后序遍历 lrd

    void PostOrder()
    {
        _PostOrder(_root);
        cout << endl;
    }

    //层序遍历  采用队列---先进先出

    void LevelOrder()
    {
        queue<Node*> q;
        if (_root)
        {
            q.push(_root);
        }
        while (q.size())
        {
            Node* cur = q.front();
            if (cur->_left != NULL)
                q.push(cur->_left);
            if (cur->_right != NULL)
                q.push(cur->_right);
            cout << cur->_data << " ";
            q.pop();
        }
        cout << endl;
    }


    //找数据
    Node* Find(const T& x)
    {
        return  _Find(_root, x);
    }

    //求叶子节点(没有左孩子,没有右孩子的节点)个数
    size_t LeafSize()
    {
        if (_root != NULL)
            return _LeafSize(_root);
        return 0;
    }


    //求总结点的个数
    size_t Size()
    {
        if (_root)
            return _Size(_root);
        return 0;
    }


    //求第k层的结点的个数
    size_t GetKLevel(size_t k)
    {
        if (_root)
            return _GetKLevel(_root, k);
        return 0;
    }


    //求二叉树的深度
    size_t Depth()
    {
        if (_root)
            return _Depth(_root);
        return 0;
    }
protected:

    void Destroy(Node* root)
    {
        if ( root !=NULL )
        {
            Destroy(root->_left);
            Destroy(root->_right);
        }
        delete root;
        root = NULL;
        return;
    }

    void _PrevOrder(Node* root)
    {
        if ( root !=NULL )
        {
            cout << root->_data << " ";
            _PrevOrder(root->_left);
            _PrevOrder(root->_right);
        }
        return;
    }

    void _InOrder(Node*  root)
    {
        if ( root !=NULL )
        {
            _InOrder(root->_left);
            cout << root->_data << " ";
            _InOrder(root->_right);
        }
    }

    void _PostOrder(Node* root)
    {
        if ( root !=NULL )
        {
            _PostOrder(root->_left);
            _PostOrder(root->_right);
            cout << root->_data << " ";
        }
    }

    Node* _Find(Node* root,const T& x)
    {
        static Node* node = NULL;
        if (root == NULL)
        {
            return NULL;
        }
        if (root->_data == x)
        {   
            node = root;
            return node;
        }
        else
        {
            if (_Find(root->_left, x) == NULL)
            {
                return _Find(root->_right, x);
            }
            else
            {
                return node;
            }
        }
    }

    size_t _Size(Node* root)
    {
        static int count = 0;
        if ( root !=NULL )
        {
            count++;
            _Size(root->_left);
            _Size(root->_right);
        }
        return count;
    }

    size_t _Depth(Node* root)
    {
        if (root == NULL)
            return 0;
        size_t L_Depth = 1;
        L_Depth += _Depth(root->_left);
        size_t R_Depth = 1;
        R_Depth += _Depth(root->_right);
        return L_Depth > R_Depth ? L_Depth : R_Depth;
    }

    //第k层左子树+第k层右子树的结点的个数
    size_t _GetKLevel(Node* root, size_t k)
    {
        if (k == 0 || root == NULL)
            return 0;
        if (k == 1)
            return 1;
        int numleft = _GetKLevel(root->_left, k - 1);
        int numright = _GetKLevel(root->_right, k - 1);
        return(numleft + numright);
    }

    size_t _LeafSize(Node* root)
    {
        static int count = 0;
        if ((root->_left == NULL) && (root->_right == NULL))
            return ++count;
        if (root != NULL)
        {
            _LeafSize(root->_left);
            _LeafSize(root->_right);
        }
        return count;
    }


    Node* _root;
};




void TestBinaryTree()
{
    int array[] = { 1, 2, 3, '*', '*', 4, '*', '*', 5, 6,'*','*',7 };
    BinaryTree<int> t(array,sizeof(array)/sizeof(array[0]),'*');
    BinaryTree<int> t1(t); 
    t.PrevOrder();                            // 先序遍历
    t.InOrder();                             //  中序遍历
    t.PostOrder();                          //   后序遍历
    t.LevelOrder();                        //    层序遍历
    cout << t.Size() << endl;              //    二叉树结点个数
    cout << t.LeafSize() << endl;         //     二叉树叶子结点的个数
    cout << t.GetKLevel(3) << endl;      //      二叉树第k层的结点的个数
    cout << t.Depth() << endl;          //       二叉树的深度
    BinaryTreeNode<int>* node = t.Find(2);
    BinaryTree<int> t2;
    t2 = t;                          
}


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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317

测试用例：

#include <iostream>
#include <queue>
using namespace std;
#include "BinaryTree.hpp"
int main()
{
    TestBinaryTree();
    return 0;
}
1
2
3
4
5
6
7
8
9

测试用例用图来描述：

实际运行结果图：