摘要：本文主要介绍了二叉树的基本操作的实现并且进行了测试。

SqBinaryTree.h

 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> &copy);
64     BinaryTree<ElemType> &operator=(const BinaryTree<ElemType> &copy);
65 
66 };
67 
68 #endif // !_BINARYTREE_

SqBinaryTree.cpp

  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> &copy) {
185     root = CopyTreeHelp(copy.root);
186 }
187 
188 template<class ElemType>
189 BinaryTree<ElemType> &BinaryTree<ElemType>::operator=(const BinaryTree<ElemType> &copy) {
190     if (&copy!=this) {
191         DestroyHelp(root);
192         root = CopyTreeHelp(copy.root);
193     }
194     return *this;
195 }

main.cpp

 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 }