binarytree.h

一个我的数据结构解题集合

#ifndef BINARYTREE_H__
#define BINARYTREE_H__

#include <assert.h>

/* 二叉树数据结构，
 * 由于写iterator比较浪费时间， 
 * 没有做太多的封装 
 */


/* 二叉树结点
 */ 
template <typename T>
struct BTreeNode {

	BTreeNode *left;
	BTreeNode *right;
	T data;

	/* 构造函数
	 * dat: 数据场,
	 * leftchild: 左孩子指针场, rightchild: 右孩子指针场
	 */
    BTreeNode(T dat = T(),
			  BTreeNode *leftchild = 0,
			  BTreeNode *rightchild = 0)
        : data(dat), left(leftchild), right(rightchild) {}

	/* 清空以本结点为根的树
	 * 调用后本结点也不可再次使用
	 */
	void clear() {
		if (left) left->clear();
		if (right) right->clear();
		delete this;
	} // clear()

	/* 插入为左子结点, 若原来存在左子结点, 先清空
	 */
	void insertLeft(const T& e) {
		BTreeNode *node = new BTreeNode(e);
		if (left) left->clear();
		left = node;
	} // insertLeft(const T&)

	/* 插入为右子结点, 若原来存在右子结点, 先清空
	 */
	void insertRight(const T& e) {
		BTreeNode *node = new BTreeNode(e);
		if (right) right->clear();
		right = node;
	} // insertRight(const T&)

}; // BTreeNode

/* 二叉树雏形, 对于本题来说足够了
 * 实现句柄语义
 */
template <typename T>
class BTree {
private:
	int *refcnt_;		// 引用计数

public:

	/* 根结点
	 */
	BTreeNode<T> *root;

	/* 构造函数
	 */
	BTree(BTreeNode<T> *r = 0)
		: root(r), refcnt_(new int(1)) {}

	/* 拷贝构造函数
	 */
	BTree(BTree& other)
		: root(other.root), refcnt_(other.refcnt_)
		{ ++(*refcnt_);	}

	/* 赋值函数
	 */
	BTree& operator=(BTree& rhs) {
		++(*rhs.refcnt_);
		if ( --(*refcnt_) == 0 )
			clear();
		root = other.root;
		refcnt_ = other.refcnt_;
	} // operator=(BTree&)

	/* 析构函数
	 */
	~BTree() {
		if (--(*refcnt_) == 0 )
			clear();
	} // ~BTree();

	/* 清空整棵树
	 */
	void clear() {
		root->clear();
    } // clear()

	/* 前序遍历二叉树
	 */
	template<typename Func>
	void preorderTraverse(Func visit) {
		Stack<BTreeNode<T> *> stack;
		BTreeNode<T> *cur;
		
		stack.push(root);
		while ( !stack.isEmpty() ) {
			cur = stack.top(); stack.pop();
			visit(cur->data);
			if (cur->right) stack.push(cur->right);
			if (cur->left)  stack.push(cur->left);
		}
	} // preorderTraverse(Func)


	/* 中序遍历二叉树
	 */
	template<typename Func>
	void inorderTraverse(Func visit) {
		Stack<BTreeNode<T> *> stack;
		BTreeNode<T> *cur = root;

		while ( cur || !stack.isEmpty() ) {
			if (cur) {
				stack.push(cur);
				cur = cur->left;
			} else {
				cur = stack.top(); stack.pop();
				visit(cur->data);
				cur = cur->right;
			}
		}
	} // inorderTraverse(Func)

private:	// 后续遍历用到的辅助结构
	enum Status { goLeft, goRight, goUp };
	struct NodePair {
		NodePair() {}
		NodePair(BTreeNode<T> *n, Status s = goLeft)
			: node(n), status(s) {}
		BTreeNode<T> *node;
		Status status;
	};
public:
	/* 后序遍历二叉树
	 */
	template<typename Func>
	void postorderTraverse(Func visit) {
		Stack<NodePair> stack;
		stack.push(root);
		while ( !stack.isEmpty() ) {
			NodePair cur = stack.top();
			stack.pop();
			switch (cur.status) {
			case goLeft:				// 第一次访问: 向左走
				cur.status = goRight;
				stack.push(cur);		// 修改status
				if (cur.node->left)
					stack.push(cur.node->left);
				break;
			case goRight:				// 第二次访问: 向右走
				cur.status = goUp;
				stack.push(cur);		// 修改status
				if (cur.node->right)
					stack.push(cur.node->right);
				break;
			case goUp:					// 第三次访问: 向上走
				visit(cur.node->data);  // 前面已经pop()了
				break;
			default:					// 不可能情况
				assert(false);
			}
		}
	} // postorderTraverse(Func)

}; // BTree

#endif // BINARYTREE_H__