在满二叉树中，每一层节点都达到了最大个数。
完全二叉树的每一个节点都与满二叉树中的节点对应。
抽象数据类型
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));
}部分成员函数的实现
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（后序遍历）。这三种遍历过程的路线其实是相同的，只是结果不同。对于每种遍历，每个节点都要经过三次，只不过前序遍历在第一次遇到节点时立即访问，中序遍历在第二次遇到节点时访问，后序遍历要到第三次遇到节点时才访问。
遍历的递归算法
中序遍历。
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);
}
};中序遍历可能会丢失信息。
前序遍历。
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);
}
};##遍历的应用
###后序遍历的应用
计算二叉树的节点个数，可以遍历根节点的左子树和右子树，分别计算出左右子树的节点个数，然后把访问根节点的语句改为相加。
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;
}
};计算二叉树高度的思路与前面类似。
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;
}
};###前序遍历的应用
复制构造函数。
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;
};判断两棵树是否相等。
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;
}
};##遍历的非递归算法
要把递归改为非递归，一般需要一个工作栈，记录遍历时的回退路径。
###前序遍历
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);
}
}
};另一种思路，进栈时先进右子女，后进左子女。
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);
}
}
};###层次序遍历
按层次顺序访问二叉树的处理需要利用一个队列。
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);
}
}
};###中序遍历的非递归算法
类似前序遍历。
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) {}
};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());
};