在满二叉树中，每一层节点都达到了最大个数。

完全二叉树的每一个节点都与满二叉树中的节点对应。

#抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class T>
class BinaryTree {
	public:
		BinaryTree();
		BinaryTree(BinTreeNode<T> *lch, BinTreeNode<T> *rch, T item);
		int Height();
		int Size();
		bool IsEmpty();
		BinTreeNode<T> *Parent(BinTreeNode<T> *current);
		BinTreeNode<T> *LeftChild(BinTreeNode<T> *current);
		BinTreeNode<T> *RightChild(BinTreeNode<T> *current);
		bool Insert(T item);
		bool Find(const T& item) const;
		bool getData(const T& item) const;
		BinTreeNode<T> *getRoot() const;
		void preOrder(void (*visit) (BinTreeNode<T> *p));
		void inOrder(void (*visit) (BinTreeNode<T> *p));
		void postOrder(void (*visit) (BinTreeNode<T> *p));
		void levelOrder(void (*visit) (BinTreeNode<T> *p));
}

#部分成员函数的实现

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
template <class T>
void BinaryTree<T>::destroy(BinTreeNode<T> *subTree) {
	if (subTree != NULL) {
		destroy(subTree->leftChild);
		destroy(subTree->rightChild);
		delete subTree;
	}
};
template <class T>
BinTreeNode<T> *BinaryTree<T>::Parent(BinTreeNode<T> *subTree, BinTreeNode <T> *current) {
	if (subTree == NULL) {
		return NULL;
	}
	if (subTree->leftChild == current || subTree->rightChild == current) {
		return subTree;
	}
	BinTreeNode<T> *p;
	if ((p = Parent(subTree->leftChild, current) != NULL) {
		return p;
	} else {
		return Parent(subTree->rightChild, current);
	}
};
template <class T>
void BinaryTree<T>::Traverse(BinTreeNode<T> *subTree, ostream& out) {
	if (subTree != NULL) {
		out << subTree->data << ' ';
		Traverse(subTree->leftChild, out);
		Traverse(subTree->rightChild, out);
	}
};
template <class T>
istream& operator >> (istream& in, BinaryTree<T>& Tree) {
	CreateBinTree(in, Tree.root);
	return in;
};
template <class T>
ostream& operator << (ostream& out, BinaryTree<T>& Tree) {
	out << "二叉树的前序遍历" << endl;
	Tree.Traverse(Tree.root, out);
	out << endl;
	return out;
};

#遍历

令L、R、V分别代表遍历一个节点的左子树、右子树和访问该节点的操作，则遍历二叉树有6种规则：VLR、LVR、LRV、VRL、RVL和RLV。若规定先左后右，则只剩三种规则，即VLR（前序遍历）、LVR（中序遍历）和LRV（后序遍历）。这三种遍历过程的路线其实是相同的，只是结果不同。对于每种遍历，每个节点都要经过三次，只不过前序遍历在第一次遇到节点时立即访问，中序遍历在第二次遇到节点时访问，后序遍历要到第三次遇到节点时才访问。

##遍历的递归算法

中序遍历。

1
2
3
4
5
6
7
8
9
template <class T>
void BinaryTree<T>::InOrder(BinTreeNode<T> *subTree,
	void (* visit)(BinTreeNode<T> *p)) {
	if (subTree != NULL) {
		InOrder(subTree->leftChild, visit);
		visit(subTree);
		InOrder(subTree->rightChild, visit);
	}
};

中序遍历可能会丢失信息。

前序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template <class T>
void BinaryTree<T>::PreOrder(BinTreeNode<T> *subTree,
	void (* visit)(BinTreeNode<T> *p)) {
	if (subTree != NULL) {
		visit(subTree);
		PreOrder(subTree->leftChild, visit);
		PreOrder(subTree->rightChild, visit);
	}
};
第一个被访问的元素一定是二叉树的根，如果根的左子树非空，则在根后紧随的一定是根的左子女；如果左子女为空，则其后紧跟的是其右子树的根。
后序遍历。
```cpp
template <class T>
void BinaryTree<T>::PostOrder(BinTreeNode<T> *subTree,
	void (* visit)(BinTreeNode<T> *p)) {
	if (subTree != NULL) {
		PostOrder(subTree->leftChild, visit);
		PostOrder(subTree->rightChild, visit);
		visit(subTree);
	}
};

##遍历的应用

###后序遍历的应用

计算二叉树的节点个数，可以遍历根节点的左子树和右子树，分别计算出左右子树的节点个数，然后把访问根节点的语句改为相加。

1
2
3
4
5
6
7
8
template <class T>
int BinaryTree<T>::Size(BinTreeNode<T> *subTree) const {
	if (subTree == NULL) {
		return 0;
	} else {
		return Size(subTree->leftChild) + Size(subTree->rightChild) + 1;
	}
};

计算二叉树高度的思路与前面类似。

1
2
3
4
5
6
7
8
9
10
template <class T>
int BinaryTree<T>::Height(BinTreeNode<T> *subTree) const {
	if (subTree == NULL) {
		return 0;
	} else {
		int i = Height(subTree->leftChild);
		int j = Height(subTree->rightChild);
		return (i < j) ? j + 1 : i + 1;
	}
};

###前序遍历的应用

复制构造函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class T>
BinaryTree<T>::BinaryTree(const BinaryTree<T>& s) {
	root = Copy(s.root);
};
template <class T>
BinTreeNode<T> *BinaryTree<T>::Copy(BinTreeNode<T> *orignode) {
	if (orignode == NULL) {
		return NULL;
	}
	BinTreeNode<T> *temp = new BinTreeNode<T>;
	temp->data = orignode->data;
	temp->leftChild = Copy(orignode->leftChild);
	temp->rightChild = Copy(orignode->rightChild);
	return temp;
};

判断两棵树是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class T>
int operator == (const BinaryTree<T>& s, const BinaryTree<T>& t) {
	return equal(s.root, t.root) ? true : false;
};
template <class T>
bool equal(BinTreeNode<T> *a, BinTreeNode<T> *b) {
	if (a == NULL && b == NULL) {
		return true;
	}
	if (a != NULL && b != NULL && a->data == b->data
		&& equal(a->leftChild, b->leftChild)
		&& equal(a->rightChild, b->rightChild)) {
		return true;
	} else {
		return false;
	}
};

##遍历的非递归算法

要把递归改为非递归，一般需要一个工作栈，记录遍历时的回退路径。

###前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class T>
void BinaryTree<T>::PreOrder(void (*visit)(BinTreeNode<T> *p)) {
	stack<BinTreeNode<T>*> S;
	BinTreeNode<T> *p == root;
	S.Push(NULL);
	while (p != NULL) {
		visit(p);
		if (p->rightChild != NULL) {
			S.Push(p->rightChild);
		}
		if (p->leftChild != NULL) {
			p = p->leftChild;
		} else {
			S.Pop(p);
		}
	}
};

另一种思路，进栈时先进右子女，后进左子女。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class T>
void BinaryTree<T>::PreOrder(void (*visit)(BinTreeNode<T> *p)) {
	stack<BinTreeNode<T>*> S;
	BinTreeNode<T> *p;
	S.Push(root);
	while (! S.IsEmpty()) {
		S.Pop(p);
		visit(p);
		if (p->rightChild != NULL) {
			S.Push(p->rightChild);
		}
		if (p->leftChild != NULL) {
			S.Push(p->leftChild);
		}
	}
};

###层次序遍历

按层次顺序访问二叉树的处理需要利用一个队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class T>
void BinaryTree<T>::LevelOrder(void (*visit)(BinTreeNode<T> *p) {
	Queue<BinTreeNode<T>*> Q;
	BinTreeNode<T> *p = root;
	Q.EnQueue(p);
	while (! Q.IsEmpty()) {
		Q.DeQueue(p);
		visit(p);
		if (p->leftChild != NULL) {
			Q.EnQueue(p->leftChild);
		}
		if (p->rightChild != NULL) {
			Q.EnQueue(p->rightChild);
		}
	}
};

###中序遍历的非递归算法

类似前序遍历。

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
template <class T>
void BinaryTree<T>::InOrder(void (*visit)(BinTreeNode<T> *p) {
	stack<BinTreeNode<T>*> S;
	BinTreeNode<T> *p = root;
	do {
		while (p != NULL) {
			S.Push(p);
			p = p->leftChild;
		}
		if (! S.IsEmpty()) {
			S.Pop(p);
			visit(p);
			p = p->rightChild;
		}
	} while (p != NULL || !S.IsEmpty());
};
###后序遍历的非递归算法
后序遍历比前序遍历和中序遍历复杂。在遍历完左子树时还不能访问根节点，需要再遍历右子树。所以在栈工作记录中必须注明刚才是在左子树还是在右子树中。所以，定义如下结构的栈节点。
```cpp
template <class T>
struct stkNode {
	BinTreeNode<T> *ptr;
	enum tag {L, R};
	stkNode(BinTreeNode<T> *N = NULL): ptr(N), tag(L) {}
};
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
template <class T>
void BinaryTree<T>::PostOrder(void (*visit)(BinTreeNode<T> *p)) {
	Stack<stkNode<T>> S;
	stkNode<T> w;
	BinTreeNode<T>* p = root;
	do {
		while (p != NULL) {
			w.ptr = p;
			w.tag = L;
			S.Push(w);
			p = p->leftChild;
		}
		int continuel = 1;
		while (continuel && !S.IsEmpty()) {
			S.Pop(w);
			p = w.ptr;
			switch (w.tag) {
				case L:
					w.tag = R;
					S.Push(w);
					continuel = 0;
					p = p->rightChild;
					break;
				case R:
					visit(p);
					break;
			}
		}
	} while (!S.IsEmpty());
};