1 #ifndef _BINARYTREE_
2 #define _BINARYTREE_
3 #include<iostream>
4 using namespace std;
5
6 //首先定义二叉树结点类模板
7 template<class ElemType>
8 struct BinTreeNode
9 {
10 //数据成员
11 ElemType data;
12 BinTreeNode<ElemType> *leftChild; //左指针
13 BinTreeNode<ElemType> *rightChild; //右指针
14 //构造函数模板
15 BinTreeNode(); //无参构造函数
16 BinTreeNode(const ElemType &val,BinTreeNode<ElemType> *lchild=NULL, BinTreeNode<ElemType> *rchild = NULL);
17 };
18
19 //----------------------------------------------------------------------------------------------------------------------------------------
20
21 template<class ElemType>
22 class BinaryTree {
23 protected:
24 BinTreeNode<ElemType> *root;
25 //辅助函数
26 //创建二叉树
27 void CreateBinTree(BinTreeNode<ElemType> *&r,ElemType pre[],ElemType in[],
28 int preLeft,int preRight,int inLeft,int inRight);
29 //显示二叉树
30 void DisplayBTHelp(BinTreeNode<ElemType> *r,int Level);
31 //销毁二叉树
32 void DestroyHelp(BinTreeNode<ElemType> * &r);
33 //先序、中序、后序遍历二叉树
34 void PreOrderHelp(BinTreeNode<ElemType> *r,void(*visit)(ElemType &))const;
35 void InOrderHelp(BinTreeNode<ElemType> *r, void(*visit)(ElemType &))const;
36 void PostOrderHelp(BinTreeNode<ElemType> *r, void(*visit)(ElemType &))const;
37 //计算结点个数和树高
38 int NodeCountHelp(const BinTreeNode<ElemType> *r)const;
39 int HeightHelp(const BinTreeNode<ElemType> *r)const;
40 //复制二叉树
41 BinTreeNode<ElemType> *CopyTreeHelp(BinTreeNode<ElemType> *r);
42
43 public:
44 //通过有参构造直接创建一棵二叉树
45 BinaryTree(ElemType pre[],ElemType in[],int n);
46 //析构函数
47 ~BinaryTree();
48 //分层显示二叉树
49 void DisplayBT();
50 //获取二叉树的根
51 BinTreeNode<ElemType> *GetRoot();
52 //判断二叉树是否为空
53 bool Empty();
54 //遍历二叉树
55 void PreOrder(void(*visit)(ElemType &));
56 void InOrder(void(*visit)(ElemType &));
57 void PostOrder(void(*visit)(ElemType &));
58 //计算结点个数
59 int NodeCount()const;
60 //计算树高
61 int Height()const;
62 //复制构造函数和赋值运算符重载
63 BinaryTree(const BinaryTree<ElemType> ©);
64 BinaryTree<ElemType> &operator=(const BinaryTree<ElemType> ©);
65
66 };
67
68 #endif // !_BINARYTREE_ 1 #include "SqBinaryTree.h"
2
3 /******************二叉树结点类模板的实现***********************/
4
5 template<class ElemType>
6 BinTreeNode<ElemType>::BinTreeNode() {
7 //构造一个叶子结点
8 leftChild = rightChild = NULL;
9 }
10
11 template<class ElemType>
12 BinTreeNode<ElemType>::BinTreeNode(const ElemType &val, BinTreeNode<ElemType> *lchild, BinTreeNode<ElemType> *rchild) {
13 data = val;
14 leftChild = lchild;
15 rightChild = rchild;
16 }
17
18 /*******************二叉树类辅助函数的实现*********************/
19
20 template<class ElemType>
21 void BinaryTree<ElemType>::CreateBinTree(BinTreeNode<ElemType> *&r, ElemType pre[], ElemType in[],
22 int preLeft, int preRight, int inLeft, int inRight) {
23 if (preLeft>preRight || inLeft>inRight) {
24 r = NULL;
25 }
26 else {
27 r = new BinTreeNode<ElemType>(pre[preLeft]); //生成根结点
28 int mid = inLeft;
29 while (in[mid]!=pre[preLeft]) {
30 mid++;
31 }
32 CreateBinTree(r->leftChild,pre,in,preLeft+1,preLeft+mid-inLeft,inLeft,mid-1);
33 CreateBinTree(r->rightChild,pre,in,preLeft+mid-inLeft+1,preRight,mid+1,inRight);
34 }
35 }
36
37 template<class ElemType>
38 void BinaryTree<ElemType>::DisplayBTHelp(BinTreeNode<ElemType> *r, int Level) {
39 if (r!=NULL)
40 {
41 DisplayBTHelp(r->leftChild,Level+1);
42 cout << endl;
43 for (int i = 0; i < Level - 1;i++) {
44 cout << " ";
45 }
46 cout << r->data;
47 DisplayBTHelp(r->rightChild,Level+1);
48 }
49 }
50
51 template<class ElemType>
52 void BinaryTree<ElemType>::DestroyHelp(BinTreeNode<ElemType> * &r) {
53 if (r!=NULL) {
54 DestroyHelp(r->leftChild);
55 DestroyHelp(r->rightChild);
56 delete r;
57 r = NULL; //保险起见，防止野指针
58 }
59 }
60
61 template<class ElemType>
62 void BinaryTree<ElemType>::PreOrderHelp(BinTreeNode<ElemType> *r,
63 void(*visit)(ElemType &))const {
64 if(r!=NULL){
65 (*visit)(r->data);
66 PreOrderHelp(r->leftChild, visit);
67 PreOrderHelp(r->rightChild, visit);
68 }
69 }
70
71 template<class ElemType>
72 void BinaryTree<ElemType>::InOrderHelp(BinTreeNode<ElemType> *r,
73 void(*visit)(ElemType &))const {
74 if (r != NULL) {
75 InOrderHelp(r->leftChild, visit);
76 (*visit)(r->data);
77 InOrderHelp(r->rightChild, visit);
78 }
79 }
80
81 template<class ElemType>
82 void BinaryTree<ElemType>::PostOrderHelp(BinTreeNode<ElemType> *r,
83 void(*visit)(ElemType &))const {
84 if (r != NULL) {
85 PostOrderHelp(r->leftChild, visit);
86 PostOrderHelp(r->rightChild, visit);
87 (*visit)(r->data);
88 }
89 }
90
91 template<class ElemType>
92 int BinaryTree<ElemType>::NodeCountHelp(const BinTreeNode<ElemType> *r)const {
93 if (r==NULL) {
94 return 0;
95 }
96 else {
97 return NodeCountHelp(r->leftChild) + NodeCountHelp(r->rightChild) + 1;
98 }
99 }
100
101 template<class ElemType>
102 int BinaryTree<ElemType>::HeightHelp(const BinTreeNode<ElemType> *r)const {
103 if (r==NULL) {
104 return 0;
105 }
106 else {
107 int lHeight, rHeight;
108 lHeight = HeightHelp(r->leftChild);
109 rHeight = HeightHelp(r->rightChild);
110 return (lHeight>rHeight?lHeight:rHeight) + 1;
111 }
112 }
113
114 template<class ElemType>
115 BinTreeNode<ElemType> *BinaryTree<ElemType>::CopyTreeHelp(BinTreeNode<ElemType> *r) {
116 if (r == NULL) {
117 return NULL;
118 }
119 else {
120 BinTreeNode<ElemType> *lChild = CopyTreeHelp(r->leftChild);
121 BinTreeNode<ElemType> *rChild = CopyTreeHelp(r->rightChild);
122 BinTreeNode<ElemType> *rt = new BinTreeNode<ElemType>(r->data, lChild, rChild);
123
124 return rt;
125 }
126 }
127
128
129 /******************二叉树类函数的实现***************************/
130
131 template<class ElemType>
132 BinaryTree<ElemType>::BinaryTree(ElemType pre[], ElemType in[], int n) {
133 CreateBinTree(root,pre,in,0,n-1,0,n-1);
134 }
135
136 template<class ElemType>
137 BinaryTree<ElemType>::~BinaryTree(){
138 DestroyHelp(root);
139 cout << "析构函数调用" << endl;
140 }
141
142 template<class ElemType>
143 void BinaryTree<ElemType>::DisplayBT() {
144 DisplayBTHelp(root,1);
145 cout << endl;
146 }
147
148 template<class ElemType>
149 BinTreeNode<ElemType> *BinaryTree<ElemType>::GetRoot() {
150 return root;
151 }
152
153 template<class ElemType>
154 bool BinaryTree<ElemType>::Empty() {
155 return root == NULL;
156 }
157
158 template<class ElemType>
159 void BinaryTree<ElemType>::PreOrder(void(*visit)(ElemType &)) {
160 PreOrderHelp(root,visit);
161 }
162
163 template<class ElemType>
164 void BinaryTree<ElemType>::InOrder(void(*visit)(ElemType &)) {
165 InOrderHelp(root, visit);
166 }
167
168 template<class ElemType>
169 void BinaryTree<ElemType>::PostOrder(void(*visit)(ElemType &)) {
170 PostOrderHelp(root, visit);
171 }
172
173 template<class ElemType>
174 int BinaryTree<ElemType>::NodeCount()const {
175 return NodeCountHelp(root);
176 }
177
178 template<class ElemType>
179 int BinaryTree<ElemType>::Height()const {
180 return HeightHelp(root);
181 }
182
183 template<class ElemType>
184 BinaryTree<ElemType>::BinaryTree(const BinaryTree<ElemType> ©) {
185 root = CopyTreeHelp(copy.root);
186 }
187
188 template<class ElemType>
189 BinaryTree<ElemType> &BinaryTree<ElemType>::operator=(const BinaryTree<ElemType> ©) {
190 if (©!=this) {
191 DestroyHelp(root);
192 root = CopyTreeHelp(copy.root);
193 }
194 return *this;
195 } 1 #include<iostream>
2 #include"SqBinaryTree.cpp"
3
4 using namespace std;
5
6 void show(char &a) {
7 cout << a << " ";
8 }
9
10 void test() {
11 char pre[] = "ABCDEFGHI";
12 char in[] = "DCBAGFHEI";
13 int n = 9;
14 BinaryTree<char> Tree(pre,in,n);
15 //Tree.GetRoot();
16 //cout << Tree.GetRoot()->data<<endl;
17 //Tree.DisplayBT();
18 cout << Tree.Empty() << endl;
19 void (*visit) (char &);
20 visit = show;
21 Tree.PreOrder(visit);
22 cout << endl;
23 Tree.InOrder(visit);
24 cout << endl;
25 Tree.PostOrder(visit);
26 cout << endl;
27 cout << Tree.NodeCount() << endl;
28 cout << Tree.Height() << endl;
29 BinaryTree<char> T(Tree);
30 T.DisplayBT();
31 BinaryTree<char> T1 = T;
32 T1.DisplayBT();
33 }
34
35 int main() {
36
37 test();
38 system("pause");
39 return 0;
40 }