二叉树的链式实现

二叉树的定义见：二叉树实现：公式化描述

二叉树最常用的描述方法是用链表或指针。每个元素都用一个有两个指针域的节点表示，这两个域为 L e f t C h i l d和R i g h t C h i d。除此两个指针域外，每个节点还有一个 d a t a域。
二叉树的边可用一个从父节点到子节点的指针来描述。指针放在父节点的指针域中。因为包括n 个元素的二叉树恰有 n- 1 条边，因此将有2n- (n- 1 ) =n+ 1 个指针域没有值，这些域被置为0。

节点类：

 1 template<class T>
 2 class BinaryTreeNode
 3 {
 4     friend class BinaryTree<T>;
 5 public:
 6     //构造函数
 7     BinaryTreeNode(){ LeftChild = RightChild = 0; }
 8     BinaryTreeNode(const T& e){ data = e; LeftChild = RightChild = 0; }
 9     BinaryTreeNode(const T& e, BinaryTreeNode *l, BinaryTreeNode *r)
10     {
11         data = e;
12         LeftChild = l;
13         RightChild = r;
14     }
15 private:
16     T data;
17     BinaryTreeNode<T> *LeftChild;//左子树
18     BinaryTreeNode<T> *RightChild;//右子树
19 };

二叉树：

 1 template<class T>
 2 class BinaryTree
 3 {
 4 public:
 5     BinaryTree(){ root = NULL;
 6     }
 7 
 8     //复制构造函数
 9     BinaryTree(const BinaryTree<T> &t);
10     ~BinaryTree(){};
11     bool IsEmpty() const{ return root == NULL };
12     bool Root(T& x)const;//获取根节点值
13     void MakeTree(const T& element, BinaryTree<T>& left, BinaryTree<T>& right);//创建二叉树
14     void BreakTree(T& element, BinaryTree<T> &left, BinaryTree<T> &right);//分拆二叉树
15     void PreOrder(void (*Visit)(BinaryTreeNode<T> *u))//前序遍历
16     {
17         PreOrder(Visit, root);
18     }
19     void InOrder(void(*Visit)(BinaryTreeNode<T> *u))const//中序遍历
20     {
21         InOrder(Visit, root);
22     }
23     void PostOrder(void(*Visit)(BinaryTreeNode<T> *u))const//后序遍历
24     {
25         PostOrder(Visit, root);
26     }
27 
28     BinaryTreeNode<T>* CopyTree(const BinaryTreeNode<T>* t);//复制树
29 
30     void LevelOrder(void(*Visit)(BinaryTreeNode<T> *u))const;//层序遍历
　　　　//各种遍历输出
31     void PreOutput()const;
32     void InOutput()const;
33     void PostOutput()const;
34     void LevelOutput()const;
35     void Delete();
36     int Height()const//获取树的高度
37     {
38         return Height(root);
39     }
40 
41     int Size();//树的节点数
42 private:
43     BinaryTreeNode<T> *root;//根节点
44     void PreOrder(void (*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);
45     void InOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t)const;
46     void PostOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t)const;
47     int Height(BinaryTreeNode<T> *t)const;
48     
49 
50     static void output(BinaryTreeNode<T> *t)
51     {
52         std::cout << t->data << ' ';
53     }
54 
55     static void freeNode(BinaryTreeNode<T> *t)
56     {
57         delete t;
58         t = NULL;
59     }
60     
61     static void ctsize(BinaryTreeNode<T> *t)
62     {
63         ++count;
64     }
65 
66 };

  1 template<class T>
  2 BinaryTreeNode<T>* BinaryTree<T>::CopyTree(const BinaryTreeNode<T>* t)
  3 {
  4     if (t)
  5     {
  6         BinaryTreeNode<T>* lchild = CopyTree(t->LeftChild);
  7         BinaryTreeNode<T>* rchild = CopyTree(t->RightChild);
  8         root = new BinaryTreeNode<T>(t->data, lchild, rchild);
  9     }
 10 
 11     return root;
 12 }
 13 
 14 template<class T>
 15 BinaryTree<T>::BinaryTree(const BinaryTree<T> &t)
 16 {
 17     root = CopyTree(t.root);
 18 }
 19 
 20 
 21 
 22 template<class T>
 23 int BinaryTree<T>::Size()
 24 {
 25     count = 0;
 26     PreOrder(ctsize);
 27     return count;
 28 }
 29 

 30 template<class T>
 31 int BinaryTree<T>::Height(BinaryTreeNode<T> *t)const
 32 {
 33     if (!t)
 34     {
 35         return 0;
 36     }
 37     
 38     int ll = Height(t->LeftChild);
 39     int lr = Height(t->RightChild);
 40 
 41     if (ll > lr)
 42     {
 43         return ++ll;
 44     }
 45     else
 46         return ++lr;
 47 }
 48 
 49 template<class T>
 50 bool BinaryTree<T>::Root(T& x) const
 51 {
 52     if (root)
 53     {
 54         x = root->data;
 55         return true;
 56     }
 57     return false;
 58 }
 59 
//当left和right以及this二叉树有重复时，利用拷贝构造函数复制一部分，以免左右子树指向同一个而引发错误
 60 template<class T>
 61 void BinaryTree<T>::MakeTree(const T& element, BinaryTree<T>& left, BinaryTree<T>& right)
 62 {
 63     if (&left==&right&&this==&left)
 64     {
 65         BinaryTree<T> newTree = right;
 66         BinaryTree<T> newTree2 = left;
 67         root = new BinaryTreeNode<T>(element, newTree2.root, newTree.root);
 68     }
 69     else if (&left==&right)
 70     {
 71         BinaryTree<T> newTree = right;
 72         root = new BinaryTreeNode<T>(element, left.root, newTree.root);
 73     }
 74     else if (this==&left||this==&right)
 75     {
 76         BinaryTree<T> newTree = *this;
 77         root = new BinaryTreeNode<T>(element, left.root, newTree.root);
 78     }
 79     else
 80     root = new BinaryTreeNode<T>(element, left.root, right.root);
 81 
 82     left.root = right.root = NULL;
 83 }
 84 
 85 template<class T>
 86 void BinaryTree<T>::BreakTree(T& element, BinaryTree<T> &left, BinaryTree<T> &right)
 87 {
 88     if (root==NULL)
 89     {
 90         std::cerr << "树为空，不能拆分" << std::endl;
 91         return;
 92     }
 93 
 94     BinaryTree<T> newTree = *this;
 95     element = newTree.root->data;
 96     left.root = newTree.root->LeftChild;
 97     right.root = newTree.root->RightChild;
 98 
 99     delete root;
100     root = NULL;
101 }
102 
103 template<class T>
104 void BinaryTree<T>::PreOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t)
105 {
106     if (t)
107     {
108         Visit(t);
109         PreOrder(Visit, t->LeftChild);
110         PreOrder(Visit, t->RightChild);
111     }
112 }
113 
114 template<class T>
115 void BinaryTree<T>::InOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t)const
116 {
117     if (t)
118     {
119         InOrder(Visit, t->LeftChild);
120         Visit(t);
121         InOrder(Visit, t->RightChild);
122     }
123 }
124 
125 template<class T>
126 void BinaryTree<T>::PostOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t)const
127 {
128     if (t)
129     {
130         PostOrder(Visit, t->LeftChild);
131         PostOrder(Visit, t->RightChild);
132         Visit(t);
133     }
134 }
135 
136 template<class T>
137 void BinaryTree<T>::LevelOrder(void(*Visit)(BinaryTreeNode<T> *u))const
138 {
139     LinkedQueue<T> Q;
140     BinaryTreeNode<T> *t = root;
141     while (t)
142     {
143         Visit(t);
144         if (t->LeftChild)
145         {
146             Q.Add(t->LeftChild);
147         }
148         if (t->RightChild)
149         {
150             Q.Add(t->RightChild);
151         }
152 
153         if (Q.IsEmpty())
154         {
155             return;
156         }
157         Q.Delete(t);
158     }    
159 }
160 
161 template<class T>
162 void BinaryTree<T>::PreOutput()const
163 {
164     PreOrder(output, root);
165 }
166 
167 template<class T>
168 void BinaryTree<T>::InOutput()const
169 {
170     InOrder(output, root);
171 }
172 
173 template<class T>
174 void BinaryTree<T>::PostOutput()const
175 {
176     PostOrder(output, root);
177 }
178 
179 template<class T>
180 void BinaryTree<T>::LevelOutput()const
181 {
182     LevelOutput(output, root);
183 }
184 
185 template<class T>
186 void BinaryTree<T>::Delete()
187 {
188     PostOrder(freeNode, root);
189     root = NULL;
190 }

几个操作的解释：

前三种遍历可以用递归完成，层次调用则利用队列

删除：

要删除一棵二叉树，需要删除其所有节点。可以通过后序遍历在访问一个节点时，把其删除。也就是说先删除左子树，然后右子树，最后删除根。

计算高度：

通过进行后序遍历，可以得到二叉树的高度。首先得到左子树的高度 h l，然后得到右子树的高度h r。此时，树的高度为：m a x { h l， hr} + 1

简单测试：

 1 #include<iostream>
 2 #include "binaryTree.h"
 3 
 4 int countx = 0;
 5 BinaryTree<int> a, x, y, z;
 6 
 7 template<class T>
 8 void ct(BinaryTreeNode<T> *t)
 9 {
10     ++countx;
11 }
12 
13 void main(void)
14 {
15     y.MakeTree(1, a, a);
16     z.MakeTree(2, y, y);
17     x.MakeTree(3, y, z);
18     y.MakeTree(4, x, a);
19     y.PreOrder(ct);
20     
21     std::cout << countx << std::endl;
22     std::cout << y.Height() << std::endl;
23     std::cout << y.Size() << std::endl;
24     y.Delete();
25     std::cout << y.Height() << std::endl;
26     std::cout << y.Size() << std::endl;    
27 }