二叉树

Posted on | In , | |
Words count in article: 3k | Reading time ≈ 16 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// BinNode.h
// 二叉树的基本组陈实体是二叉树节点，而边则对应于节点之间的相互关系
#include <iostream>
#define BinNodePosi(T) BinNode<T>* //节点位置
#define stature(p)  ((p) ? (p)->height : -1)// 节点高度，约定空树高度为-1

//BinNode 状态与性质的判断：
#define IsRoot(x) ( !( (x).parent ) )
#define IsLChild(x) ( ! IsRoot(x) && ( &(x) == (x).parent->lc ) )
#define IsRChild(x) ( ! IsRoot(x) && ( &(x) == (x).parent->rc ) )
#define HasParent(x) ( ! IsRoot(x) )
#define HasLChild(x) ( (x).lc )
#define HasRChild(x) ( (x).rc )
#define HasChild(x) ( HasLChild(x) || HasRChild(x) )
#define HasBothChild(x) ( HasLChild(x) && HasRChild(x) )
#define IsLeaf(x) ( ! HasChild(x) )

// 与BinNode具有特定关系的节点以及指针:
#define sibling(p) ( IsLChild(*(p)) ? (p)->parent->rc: (p)->parent->lc ) //兄弟
#define uncle(x) ( IsLChild(*((x)->parent)) ? (x)->parent->parent->rc: (x)->parent->parent->lc ) //叔叔
#define FromParentTo(x) /*来自父亲的引用*/ ( IsRoot(x) ? _root: ( IsLChild(x) ? (x).parent->lc : (x).parent->rc ) ) //含有父指针的二叉树结点，一般会定义这样的一个宏（获取从父节点指向自己的指针）


typedef enum { RE_RED, RB_BLACK} RBColor; //节点颜色

template <typename T> struct BinNode{ //二叉树节点模板类
// 成员
	T data;
	BinNodePosi(T) parent; BinNodePosi(T) lc; BinNodePosi(T) rc; // 父节点以及左右孩子
	int height; //高度
	int npl; //Null Path Length (左式堆， 也可以用height代替)
	RBColor color; //颜色 红黑树
// 构造函数
	BinNode(): parent(NULL), lc(NULL), rc(NULL), height(0), npl(1), color(RE_RED) {}
	BinNode(T e, BinNodePosi(T) p = NULL, BinNodePosi(T) lc = NULL, BinNodePosi(T) rc = NULL, int h = 0, int l = 1, RBColor c = RE_RED): data(e), parent(p), lc(lc), rc(rc), height(h), npl(l), color(c){}
// 操作接口
	int size(); // 统计当前节点后代总数，亦即以其为根的子树的规模
	BinNodePosi(T) insertAsLC( T const& ); // 作为当前节点的左孩子插入新节点
	BinNodePosi(T) insertAsRC( T const& ); // 作为当前节点的右孩子插入新节点
	BinNodePosi(T) succ(); //取当前节点的直接后继
	template <typename VST> void travLevel( VST& ); //子树层次遍历
	template <typename VST> void travPre( VST& ); //子树先序遍历
	template <typename VST> void travIn( VST& ); //子树中序遍历
	template <typename VST> void travPost( VST& ); //子树后序遍历
// 比较器、判等器 
	bool operator< (BinNode const& bn) { return data < bn.data; }
	bool operator== (BinNode const& bn) { return data == bn.data; }
	bool operator> (BinNode const& bn) { return data > bn.data; }
	bool operator<= (BinNode const& bn) { return data <= bn.data; }
	bool operator>= (BinNode const& bn) { return data >= bn.data; }
	bool operator!= (BinNode const& bn) { return data != bn.data; }
};

// 插入儿子节点： 约定插入新节点之前，当前节点尚无左/右孩子
template <typename T> BinNodePosi(T) BinNode<T>::insertAsLC( T const& e)
{
	return lc = new BinNode( e, this );
	/* 相当于：
		this->lc = new BinNode(e, this);
		return this->lc;
	*/
}

template <typename T> BinNodePosi(T) BinNode<T>::insertAsRC( T const& e)
{
	return rc = new BinNode( e, this );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
// BinTree.h
#include "BinNode.h"
#include <queue>
template <typename T> class BinTree{
protected:
	int _size; //规模
	BinNodePosi(T) _root; //根节点
	virtual int updateHeight ( BinNodePosi(T) x ); //更新节点x的高度
	void updateHeightAbove ( BinNodePosi(T) x ); //更新节点x及其祖先的高度
public:
	BinTree(): _size(0), _root(NULL) {}
	~BinTree() {
		if(0 < _size)
			remove( _root );
	}
	int size() const { return _size; }
	bool empty() const { return !_root; }
	BinNodePosi(T) root() const { return _root; }
	BinNodePosi(T) insertAsRoot ( T const& e );
	BinNodePosi(T) insertAsLC ( BinNodePosi(T) x, T const& e);
	BinNodePosi(T) insertAsRC ( BinNodePosi(T) x, T const& e);
	BinNodePosi(T) attachAsLC ( BinNodePosi(T) x, BinTree<T>* &S);//T作为x左子树插入
	BinNodePosi(T) attachAsRC ( BinNodePosi(T) x, BinTree<T>* &S);
	int remove ( BinNodePosi(T) x); //删除以位置x处节点为根的子树，返回该子树原先的规模
	BinTree<T>* secede ( BinNodePosi(T) x ); // 将子树x从当前树中摘除，并将其转换为一颗独立的子树
	template <typename VST> void travLevel( VST& visit) { if(_root) _root->travLevel(visit); } // 层次遍历
	template <typename VST> void travPre (VST& visit) { if(_root) _root->travPre(visit); }
	template <typename VST> void travIn (VST& visit) { if(_root) _root->travIn(visit); }
	template <typename VST> void travPost (VST& visit) { if(_root) _root->travPost(visit); }
	bool operator< (BinTree<T> const& t) { return _root && t._root && (_root->data < t._root->data); }
	bool operator== (BinTree<T> const& t) { return _root && t._root && (_root->data == t._root->data); }
	bool operator!= (BinTree<T> const& t) { return _root && t._root && (_root->data != t._root->data); }
	bool operator> (BinTree<T> const& t) { return _root && t._root && (_root->data > t._root->data); }
	bool operator<= (BinTree<T> const& t) { return _root && t._root && (_root->data <= t._root->data); }
	bool operator>= (BinTree<T> const& t) { return _root && t._root && (_root->data >= t._root->data); }
};

// 一旦有节点加入/离开二叉树，则更新其所有祖先的高度
int max(int a,int b)
{
	return a > b ? a : b;
}

template <typename T> int BinTree<T>::updateHeight(BinNodePosi(T) x)
{
	return x->height = 1 + max(stature(x->lc), stature(x->rc));
}

template <typename T> void BinTree<T>::updateHeightAbove(BinNodePosi(T) x)
{
	while(x)
	{
		updateHeight(x); 
		x = x->parent;
	}
} // 在某些种类的二叉树（红黑树）中，高度的定义有所不同，因此这里updateHeight()定义为保护级的虚函数，以便派生类在必要时重写(override)

//节点插入：
template <typename T> BinNodePosi(T) BinTree<T>::insertAsRoot( T const& e){
	_size = 1;
	return _root = new BinNode<T>(e);
}

template <typename T> BinNodePosi(T) BinTree<T>::insertAsLC(  BinNodePosi(T) x, T const& e){
	_size++;
	x->insertAsLC(e);
	updateHeightAbove(x);
	return x->lc;
}

template <typename T> BinNodePosi(T) BinTree<T>::insertAsRC(  BinNodePosi(T) x, T const& e){
	_size++;
	x->insertAsRC(e);
	updateHeightAbove(x);
	return x->lc;
}

//子树接入：
//指针是一个存放地址的变量，而指针引用指的是这个变量的引用，众所周知C++中如果参数不是引用的话会调用参数对象的拷贝构造函数，所以如果有需求想改变指针所指的对象（换句话说，就是要改变指针里面存的地址），就要使用指针引用
template <typename T>
BinNodePosi(T) BinTree<T>::attachAsLC( BinNodePosi(T) x, BinTree<T>* &S){
	if(x->lc = S->_root) x->lc->parent = x;
	_size += S->_size;
	updateHeightAbove(x);
	S->root = NULL;
	S->_size = 0;
	release( S );
	S = NULL;
	return x;
}

template <typename T>
BinNodePosi(T) BinTree<T>::attachAsRC( BinNodePosi(T) x, BinTree<T>* &S){
	if(x->rc = S->_root) x->rc->parent = x;
	_size += S->_size;
	updateHeightAbove(x);
	S->root = NULL;
	S->_size = 0;
	release( S );
	S = NULL;
	return x;
}

//子树删除
template <typename T>
int BinTree<T>::remove( BinNodePosi(T) x )
{
	FromParentTo(*x) = NULL; //切断来自父节点的指针
	updateHeightAbove(x->parent);//更新祖先高度
	int n = removeAt(x);
	_size -= n;
	return n; // 删除子树x，更新规模，返回删除节点总数
}

template <typename T> 
static int removeAt( BinNodePosi(T) x )
{
	if( !x ) return 0;
	int n = 1 + removeAt( x->lc ) + removeAt( x->rc );
//	release( x->data );
//	release( x );
	delete x;
	return n;  
}

// 子树分离
template <typename T>
BinTree<T>* BinTree<T>::secede( BinNodePosi(T) x ){
	FromParentTo ( *x ) = NULL;
	updateHeightAbove( x->parent );
	BinTree<T>* S = new BinTree<T>;
	S->root = x;
	x->parent = NULL;
	S->_size = x->size();
	_size -= S->_size;
	return S;
}

// 遍历：
template <typename T, typename VST>
void travPre ( BinNodePosi(T) x, VST& visit ){
	if( !x ) return;
	visit (x->data);
	travPre (x->lc, visit);
	travPre (x->rc, visit);
} 

template <typename T, typename VST>
void travPost ( BinNodePosi(T) x, VST& visit ){
	if( !x ) return;
	travPre (x->lc, visit);
	travPre (x->rc, visit);
	visit (x->data);
} 

template <typename T, typename VST>
void travIn ( BinNodePosi(T) x, VST& visit ){
	if( !x ) return;
	travPre (x->lc, visit);
	visit (x->data);
	travPre (x->rc, visit);
} 

// 直接后继及其定位 (中序遍历)
template <typename T> BinNodePosi(T) BinNode<T>::succ(){
	BinNodePosi(T) s = this;
	if(rc) //若有右孩子，则直接后继必在右子树中
	{
		s = rc;
		while(HasLChild(*s)) s = s->lc;
	}
	else // 否则，直接后继应是“将当前节点包含于其左子树中的最低祖先”
	{
		while(IsRChild(*s)) s = s->parent;
		s = s->parent;
	}
	return s;
}

// 层次遍历
template <typename T> template <typename VST>
void BinNode<T>::travLevel(VST& visit)
{
	std::queue<BinNodePosi(T)> Q;
	Q.push (this);
	while( !Q.empty() ){
		BinNodePosi(T) x = Q.front(); Q.pop(); visit(x->data);
		if(HasLChild(*x)) Q.push(x->lc);
		if(HasRChild(*x)) Q.push(x->rc);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
//test.cpp
#include <iostream>
#include "BinTree.h"
using namespace std;

int main()
{
	BinTree<int> test;
	test.insertAsRoot(1);
	cout << test.size();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <queue>
using namespace std;

template < typename T >
struct TreeNode
{
	TreeNode(T s): data(s), left(NULL), right(NULL) {}
	T data;
	TreeNode* left;
	TreeNode* right;
};

template < typename T >
class Tree {
private:
	int size;
	TreeNode<T>* root;
public:
	Tree(): size(0), root(NULL){};
	Tree( T x ){
		size = 1;
		root = new TreeNode<T>(x);
	}
	~Tree(){
		if(size > 0){
			queue<TreeNode<T>*> delq;
			delq.push(root);
			while(!delq.empty()){
				TreeNode<T>* x = delq.front();
				delq.pop();
				if(x->left) delq.push(x->left);
				if(x->right) delq.push(x->right);
				delete( x );
			}
		}
	}
	Tree<T>& operator= (Tree<T>& t){
		if(this->root != t.root)
		{
			this->root = t.root;
		}
		return *this;
	}
	int getsize()const { return this->size; }
	TreeNode<T>* getroot() const { return this->root; }
	TreeNode<T>* insertasleft( TreeNode<T>* x, T data ){
		x->left = new TreeNode<T>(data);
		size++;
		return x;
	}
	TreeNode<T>* insertasright( TreeNode<T>* x, T data ){
		x->right = new TreeNode<T>(data);
		size++;
		return x;
	}
	void preorder( TreeNode<T>* root){
		cout << root->data << " ";
		if(root->left) preorder(root->left);
		if(root->right) preorder(root->right);
	}
	void inorder( TreeNode<T>* root){
		if(root->left) inorder(root->left);
		cout << root->data << " ";
		if(root->right) inorder(root->right);
	}
	void postorder( TreeNode<T>* root){
		if(root->left) postorder(root->left);
		if(root->right) postorder(root->right);
		cout << root->data << " ";
	}
	void levelorder( TreeNode<T>* root){
		queue<TreeNode<T>*> Q;
		Q.push(root);
		int levelcur = 0;
		while(!Q.empty())
		{
			levelcur ++;
			cout << "level " << levelcur << " : ";
			queue<TreeNode<T>*> rem;
			while(!Q.empty())
			{
				TreeNode<T>* x = Q.front();
				Q.pop();
				if(x->left) rem.push(x->left);
				if(x->right) rem.push(x->right);
				cout << x->data << " ";
			}
			queue<TreeNode<T>*> temp = Q;
			Q = rem;
			rem = temp;
			cout << endl;
		}
	}
	int find_leaf_size( TreeNode<T>* leaf ){
		if( !leaf ) return 0;
		if( leaf->left == NULL && leaf->right == NULL ) return 1;
		return find_leaf_size( leaf->left ) + find_leaf_size( leaf->right );
	}
	int find_leaf_depth( TreeNode<T>* leaf){
		if(!leaf) return 0;
		int size_left = find_leaf_depth( leaf->left );
		int size_right = find_leaf_depth( leaf->right );
		if( size_left > size_right )
			return size_left + 1;
		else
			return size_right + 1;
	}
	TreeNode<T>* find_x_leaf( TreeNode<T>* root, const T& x){
		if( !root ) return NULL;
		if( root->data == x )  return root;
		TreeNode<T>* find_left = find_x_leaf ( root->left, x );
		if( find_left )
			return find_left;
		else
			return find_x_leaf ( root->right, x );
	}
	int find_x_level_size( TreeNode<T>* root, const T& x){
		if( !root ) return 0;
		if( x == 1 ) return 1;
		else return find_x_level_size( root->left, x-1 ) +  find_x_level_size( root->right, x-1 );
	} 
};


int main(){
	Tree<int> test(1);
	cout << "getsize: " << test.getsize() << endl;
	test.insertasleft( test.getroot(), 2);
	test.insertasright( test.getroot(), 3);
	cout << "getsize: " << test.getsize() << endl;
	cout << "preorder: ";
	test.preorder( test.getroot() );
	cout << endl;
	cout << "inorder: ";
	test.inorder( test.getroot() );
	cout << endl;
	cout << "postorder: ";
	test.postorder( test.getroot() );
	cout << endl;
	Tree<int> test1;
	test1 = test;
	cout << "test1 after = : test1.root->data = " << test.getroot()->data << endl;
	cout << "leveltravel: " << endl;
	test.levelorder( test.getroot() );
	cout << endl;
	cout << "find_leaf_size : " << endl;
	cout << " test.root : " << test.find_leaf_size( test.getroot() ) << endl;
	cout << " test.root->left : " << test.find_leaf_size( test.getroot()->left ) << endl;
	cout << " test.root->right : " << test.find_leaf_size( test.getroot()->right ) << endl;
	cout << "find_leaf_depth : " << endl;
	cout << " test.root : " << test.find_leaf_depth( test.getroot() ) << endl;
	cout << " test.root->left : " << test.find_leaf_depth( test.getroot()->left ) << endl;
	cout << " test.root->right : " << test.find_leaf_depth( test.getroot()->right ) << endl;
	cout << "find_x_leaf : " << endl;
	cout << " 1 : " << test.find_x_leaf( test.getroot(), 1 )->data << endl;
	cout << "find_x_level_size : " << endl;
	cout << " level-2 : " << test.find_x_level_size( test.getroot(), 2 ) << endl;
	return 0;
}
Donate? comment?