二叉树实现（主要是为了实现二叉搜索树时作为其父类）
1
//实现二叉树数据结构
2#ifndef BINTREE_H
3#define BINTREE_H
4
5
6//定义节点结构
7template<class T>
8class BinTreeNode
9
{
10
public:
11 BinTreeNode(const T &e,BinTreeNode<T> *l=0,BinTreeNode<T> *r=0)
12
{
13 data=e;
14 LeftChild=l;
15 RightChild=r;
16
}
17
18
19public:
20 T data;
21 BinTreeNode<T> *LeftChild,
22 *RightChild;
23
24
};
25
26
27//定义BinTree数据结构
28template<class E>//K关键子类型，E元素类型
29class BinTree
30{
31public:
32 BinTree(BinTreeNode<E>*r=0){root=r;}
33 virtual ~BinTree();
34
35//BinTree<K,E>& Insert(E &e);//插入新元素
36//BinTree<K,E>& Delete(K &k);//根据关键字进行删除
37
38 BinTree<E>& MeldTree(const E &e,BinTree<E>& left,BinTree<E>& right);//合并两棵树
39void BreakTree(E &e,BinTree<E>& left,BinTree<E>& right);//拆开两棵树
40
41void PreOrderVisit(void (*visit)(BinTreeNode<E> *node));//前序遍历
42void InOrderVisit(void (*visit)(BinTreeNode<E> *node));//中序遍历
43void PostOrderVisit(void (*visit)(BinTreeNode<E> *node));//后序遍历
44
45int Height(){return height(root);};//返回树的高度
46
47
48protected:
49
50 void PreOrderVisit(BinTreeNode<E> *t,void (*visit)(BinTreeNode<E> *node));
51 void InOrderVisit(BinTreeNode<E> *t,void (*visit)(BinTreeNode<E> *node));
52 void PostOrderVisit(BinTreeNode<E> *t,void (*visit)(BinTreeNode<E> *node));
53 static void Free(BinTreeNode<E> *node){delete node;}
54 int height(BinTreeNode<E>*t);
55 int leaves(BinTreeNode<E>*t);
56protected:
57 BinTreeNode<E> *root;//根节点指针
58
59};
60
61//---------------------------------------------------------------
62template<class E>
63BinTree<E>& BinTree<E>::MeldTree(const E &e,BinTree<E>& left,BinTree<E>& right)//合并两棵树
64{
65BinTreeNode<E> *NewNode=new BinTreeNode<E>(e,left.root,right.root);
66root=NewNode;
67left.root=right.root=0;
68return *this;
69}
70
71//---------------------------------------------------------------
72template<class E>
73void BinTree<E>::BreakTree(E &e,BinTree<E>& left,BinTree<E>& right)
74{
75
76e=root->data;
77left.root=root->LeftChild;
78right.root=root->RightChild;
79delete root;
80root=0;
81}
82
83//---------------------------------------------------------------
84template<class E>
85void BinTree<E>::PreOrderVisit(void (*visit)(BinTreeNode<E> *node))
86{
87PreOrderVisit(root,visit);
88}
89//---------------------------------------------------------------
90template<class E>
91void BinTree<E>::InOrderVisit(void (*visit)(BinTreeNode<E> *node))
92{
93InOrderVisit(root,visit);
94}
95//---------------------------------------------------------------
96template<class E>
97void BinTree<E>::PostOrderVisit(void (*visit)(BinTreeNode<E> *node))
98{
99PostOrderVisit(root,visit);
100}
101//---------------------------------------------------------------
102template<class E>
103 void BinTree<E>::PreOrderVisit(BinTreeNode<E> *t,void (*visit)(BinTreeNode<E> *node))
104{
105if(t)
106{
107visit(t);
108PreOrderVisit(t->LeftChild,visit);
109PreOrderVisit(t->RightChild,visit);
110}
111
112}
113//---------------------------------------------------------------
114template<class E>
115 void BinTree<E>::InOrderVisit(BinTreeNode<E> *t,void (*visit)(BinTreeNode<E> *node))
116{
117if(t)
118{
119InOrderVisit(t->LeftChild,visit);
120visit(t);
121InOrderVisit(t->RightChild,visit);
122}
123
124
125}
126//---------------------------------------------------------------
127template<class E>
128 void BinTree<E>::PostOrderVisit(BinTreeNode<E> *t,void (*visit)(BinTreeNode<E> *node))
129{
130if(t)
131{
132 PostOrderVisit(t->LeftChild,visit);
133 PostOrderVisit(t->RightChild,visit);
134 visit(t);
135}
136}
137//---------------------------------------------------------------
138template<class E>
139BinTree<E>::~BinTree()
140{
141PostOrderVisit(Free);
142}
143
144//---------------------------------------------------------------
145template<class E>
146int BinTree<E>::height(BinTreeNode<E>*t)
147{
148if(!t) return 0;
149else
150{
151int hl=height(t->LeftChild);
152int hr=height(t->RightChild);
153
154if(hl>hr) return ++hl;
155else return ++hr;
156}
157}
158
159
160
161
162#endif
posted on 2008-09-18 17:14
杨彬彬 阅读(544)
评论(0) 编辑 收藏 引用 所属分类:
数据结构