c++二叉树

 1 #ifndef _TREE_H_
 2 #define _TREE_H_
 3 //此类用shared_ptr来管理节点内存，所以要包含<memory>头文件,不需要手动释放内存
 4 #include <memory>
 5 #include <iostream>
 6 
 7 using namespace std;
 8 
 9 struct Node{
10     int key;
11     shared_ptr<Node> parent;
12     shared_ptr<Node> left;
13     shared_ptr<Node> right;
14     Node(int k = 0) :key(k), parent(), left(), right() {}
15 };
16 
17 typedef shared_ptr<Node> Pnode;
18 
19 class Tree
20 {
21 private:
22     Pnode root;
23     //返回以current为根节点的所有节点个数
24     size_t __nodeSize(Pnode current) const;
25     //返回以current为根节点的叶节点（没有左右节点)个数
26     size_t __leafSize(Pnode current) const;
27     //返回以current为根节点树的深度
28     size_t __depth(Pnode current) const;
29     //返回k值节点的地址
30     const Pnode * __getNodeAddress(int k) const;
31     //返回current节点下的最大值的节点
32     Pnode __maxNode(Pnode current) const;
33     //返回current节点下的最小值节点
34     Pnode __minNode(Pnode current) const;
35     void showNode(Pnode current) const;
36 public:
37     Tree() :root() {}
38     //将k插入树
39     void insert(int k);
40     //删除值为k的节点
41     void delNode(int k);
42     //判断是否存在值为k的节点
43     bool isExist(int k);
44     //树中节点个数
45     size_t nodeSize() const;
46     //树中叶节点的个数
47     size_t leafSize() const;
48     //树的深度
49     size_t depth() const;
50     //树的宽度
51     size_t width() const;
52     //树的最大值
53     int maxVal() const;
54     //树的最小值
55     int minVal() const;
56     //打印所有节点
57     void showAll() const;
58 };
59 
60 
61 #endif

tree.h

  1 #include "Tree.h"
  2 
  3 //求树的宽度要用到队列
  4 #include <queue>
  5 
  6 using namespace std;
  7 
  8 //遍历节点
  9 //void static showNode(Pnode current);
 10 
 11 void Tree::showNode(Pnode current) const
 12 {
 13     if (current.get() == NULL)
 14         return;
 15     showNode(current->left);
 16     cout << current->key << " ";
 17     showNode(current->right);
 18 }
 19 
 20 void Tree::showAll() const
 21 {
 22     showNode(root);
 23     cout << endl;
 24 }
 25 
 26 void Tree::insert(int k)
 27 {
 28     //智能指针shared_ptr变量的初始化方式
 29     Pnode new_node(new Node(k));
 30     Pnode current = root;
 31     Pnode save = root;    
 32     while (current)
 33     {
 34         save = current;
 35         if (k < current->key)
 36             current = current->left;
 37         else current = current->right;
 38     }
 39     new_node->parent = save;
 40     if (!save)
 41         root = new_node;
 42     else if (k < save->key)
 43         save->left = new_node;
 44     else save->right = new_node;
 45 }
 46 
 47 void Tree::delNode(int k)
 48 {
 49     //__getNodeAddress返回的是带有顶层const类型的指针,
 50     //后面要改变指针指向的值，所以要先解除const限制.
 51     Pnode * pdel = const_cast<Pnode *>(__getNodeAddress(k));
 52     if (!pdel)
 53     {
 54         cout << k << " is not exist!
";
 55         return;
 56     }
 57     //save保存被删节点的父节点
 58     Pnode save = (*pdel)->parent;
 59     //被删节点没有子树
 60     if (!(*pdel)->left.get() && !(*pdel)->right.get())
 61         *pdel = NULL;
 62     //被删节点左子树为空
 63     else if (!(*pdel)->left.get())
 64     {
 65         *pdel = (*pdel)->right;
 66         (*pdel)->parent = save;
 67     }
 68     //被删节点右子树为空
 69     else if (!(*pdel)->right.get())
 70     {
 71         *pdel = (*pdel)->left;
 72         (*pdel)->parent = save;
 73     }
 74     //被删节点有左右子树
 75     else {
 76         //successor为被删节点的后继
 77         Pnode successor = __minNode((*pdel)->right);
 78         successor->left = (*pdel)->left;
 79         *pdel = (*pdel)->right;
 80         (*pdel)->parent = save;
 81     }
 82 }
 83 
 84 bool Tree::isExist(int k)
 85 {
 86     return __getNodeAddress(k) != NULL;
 87 }
 88 
 89 size_t Tree::__nodeSize(Pnode current) const
 90 {
 91     if (!current)
 92         return 0;
 93     return 1 + __nodeSize(current->left) + __nodeSize(current->right);
 94 }
 95 
 96 size_t Tree::nodeSize() const
 97 {
 98     return __nodeSize(root);
 99 }
100 
101 size_t Tree::__leafSize(Pnode current) const
102 {
103     if (current.get() == NULL)
104         return 0;
105     if (current->left.get() == NULL && current->right.get() == NULL)
106         return 1;
107     return __leafSize(current->left) + __leafSize(current->right);
108 }
109 
110 size_t Tree::leafSize() const
111 {
112     return __leafSize(root);
113 }
114 
115 size_t Tree::__depth(Pnode current) const
116 {
117     if (!current)
118         return 0;
119     size_t leftSize = 1 + __depth(current->left);
120     size_t rightSize = 1 + __depth(current->right);
121     return leftSize > rightSize ? leftSize: rightSize;
122 }
123 
124 size_t Tree::depth() const
125 {
126     return __depth(root);
127 }
128 
129 size_t Tree::width() const
130 {
131     if (!root)
132         return 0;
133     Pnode current = root;
134     int maxNode = 1;
135     int ct = 0;
136     queue<Pnode> qu;
137     qu.push(current);
138     while (qu.size() != 0)
139     {
140         ct = qu.size();
141         for (int i = 0; i < ct; i++)
142         {
143             current = qu.front();
144             qu.pop();
145             if (current->left.get() != NULL)
146                 qu.push(current->left);
147             if (current->right.get() != NULL)
148                 qu.push(current->right);
149         }
150         maxNode = maxNode > qu.size() ? maxNode : qu.size();
151     }
152     return maxNode;
153 }
154 
155 /*
156 * 此处返回指针是考虑到方便delNode调用，内存本身的地址和内存指向的值会带来很大困惑，
157 * 要仔细品味,此前写delNode方法从节点本身来考虑，反复建立节点关系，写下的代码长度
158 * 大概是现在delNode长度的2倍,效率也会打折扣.
159 */
160 const Pnode  * Tree::__getNodeAddress(int k) const
161 {
162     Pnode ret = root;
163     Pnode save = {};
164     if (root->key == k)
165         return &root;
166     while (1)
167     {
168         save = ret;
169         if (k < ret->key)
170         {
171             if (!(ret = ret->left).get())
172                 break;
173             if (ret->key == k)
174                 return &(save->left);
175         }
176         else {
177             if(!(ret = ret->right).get())
178                 break;
179             if (ret->key == k)
180                 return &(save->right);
181         }
182     }
183     return NULL;
184 }
185 
186 Pnode Tree::__maxNode(Pnode current) const
187 {
188     
189     while (current->right.get() != NULL)
190         current = current->right;
191     return current;
192 }
193 
194 Pnode Tree::__minNode(Pnode current) const
195 {
196     while (current->left.get() != NULL)
197         current = current->left;
198     return current;
199 }
200 
201 int Tree::maxVal() const
202 {
203     if (root.get() == NULL)
204         return 0x80000000;
205     return __maxNode(root)->key;
206 }
207 
208 int Tree::minVal() const
209 {
210     if (root.get() == NULL)
211         return 0x7FFFFFFF;
212     return __minNode(root)->key;
213 }

tree.cpp

 1 #include <iostream>
 2 #include "Tree.h"
 3 
 4 using namespace std;
 5 
 6 void showArray(int * arr, int n);
 7 void loadArrayToTree(Tree & t, int * arr, int n);
 8 
 9 const int ASIZE = 13;
10 
11 int main()
12 {
13     int arr[ASIZE] = { 54,19,18,39,76,15,80,70,25,41,83,79,71 };
14     cout << "show array: 
";
15     showArray(arr, ASIZE);
16     Tree t;
17     loadArrayToTree(t, arr, ASIZE);
18     cout << "show Tree: 
";
19     t.showAll();
20     cout << "nodeSize() = " << t.nodeSize() << endl;
21     cout << "leafSize() = " << t.leafSize() << endl;
22     cout << "depth() = " << t.depth() << endl;
23     cout << "width() = " << t.width() << endl;
24     cout << "isExist(41) = " << t.isExist(41) << endl;
25     t.delNode(41);
26     t.showAll();
27     cout << "nodeSize() = " << t.nodeSize() << endl;
28     cout << "isExist(41) = " << t.isExist(41) << endl;
29     cout << "isExist(80) = " << t.isExist(80) << endl;
30 
31 
32     return 0;
33 }
34 
35 void showArray(int * arr, int n)
36 {
37     for (int i = 0; i < n; i++)
38         cout << arr[i] << " ";
39     cout << endl;
40 }
41 
42 void loadArrayToTree(Tree & t, int * arr, int n)
43 {
44     for (int i = 0; i < n; i++)
45         t.insert(arr[i]);
46 }

treeMain.cpp测试代码