tree0.h

数据结构中 树的基本操作 可完成遍历 查找 删除子女 子树的功能

#ifndef TREE_H
#define TREE_H

#include <iostream.h>

template<class Type> class Tree;

template<class Type> class TreeNode {  // 树的节点类定义
	friend class Tree<Type>;
public:
	TreeNode(Type value = 0, TreeNode<Type> *fc = 0, TreeNode<Type> *ns = 0) :
	  data(value), firstChild(fc), nextSibling(ns) { }  // 构造函数
private:
	Type data;  // 数据
	TreeNode<Type> *firstChild;  // 孩子
	TreeNode<Type> *nextSibling;  // 兄弟
};

// 树类
template<class Type> class Tree {
public:
	Tree() { root = current = 0; }  // 构造函数，建立空树
	~Tree() { RemovesubTree(root); }
	void BuildRoot(Type);
	bool Root();
	bool FirstChild(); 
	bool NextSibling(); 
	bool Parent();
	bool Find(Type target);
	void InsertChild(Type value);
	bool RemoveChild(int i);
	void PreOrder();  // 先根次序遍历
	void PostOrder();  // 后根次序遍历
	bool IsEmpty() const { return current == 0; }
private:
	TreeNode<Type> *root;  // 根指针
	TreeNode<Type> *current;  // 当前指针
	bool FindParent(TreeNode<Type> *t, TreeNode<Type> *p);	
	bool Find(TreeNode<Type> *p, Type target); 
	void RemovesubTree(TreeNode<Type> *p);
	void RemoveTree();
	//void PreOrder(
};

template<class Type> void Tree<Type>::BuildRoot(Type rootVal) 
{
	root = current = new TreeNode<Type>(rootVal);   // 创建根节点
}

// 寻找根，使之成为当前节点
template<class Type> bool Tree<Type>::Root()
{
	if (root == 0) {
		current = 0;
		return false;
	}
	else {
		current = root;
		return true;
	}
}

// 寻找当前节点的第一个子女
template<class Type> bool Tree<Type>::FirstChild() 
{
	if (current != 0 && current->firstChild != 0) {
		current = current->firstChild;
		return true;
	}
	else {
		current = 0;
		return false;
	}
}

// 寻找当前节点的下一个兄弟
template<class Type> bool Tree<Type>::NextSibling() 
{
	if (current && current->nextSibling) {
		current = current->nextSibling;
		return true;
	}
	else {
		current = 0;
		return false;
	}
}

// 寻找当前节点的双亲节点
template<class Type> bool Tree<Type>::Parent() 
{
	if (current && current->nextSibling) {
		current = current->nextSibling;
		return true;
	}
	else {
		current = 0;
		return false;
	}

	t = root;  // 从根节点开始

	return FindParent(t, p);  // 从根节点t后序遍历找节点p的双亲节点
}

// 所有函数：从根节点t所指节点后序遍历，找节点p的双亲节点，记在current中
template<class Type> bool Tree<Type>::FindParent(TreeNode<Type> *t, TreeNode<Type> *p)
{
	TreeNode<Type> *q = t->firstChild;  // 找第一棵子树
	while (q && q != p) {  // q == 0, 无子树; q == p, 找到双亲
		if (FindParent(q, p))
			return true;
		q = q->nextSibling;   // 找下一棵子树
	}
	if (q && q == p) {   // 成功
		current = t;
		return true;
	}
	return false;  // 失败
}

// 在树中搜索符合给定值target的节点
template<class Type> bool Tree<Type>::Find(Type target)
{
	if (IsEmpty())  // 空树
		return false;
	return Find(root, target);
}

// 私有函数：在由根指针p所指的树或子树中搜索其数据成员等于target的节点
template<class Type> bool Tree<Type>::Find(TreeNode<Type> *p, Type target) 
{
	bool result = false;
	if (p->data == target) {  // 搜索成功，p成为当前节点
		current = p;
		result = true;
	}
	else {  // 继续搜索
		TreeNode<Type> *q = p->firstChild;
		while (q && !(result = Find(p, target)))
			q = q->nextSibling;
	}

	return result;
}

// 在当前节点下插入一个包含有值value的新节点
template<class Type> void Tree<Type>::InsertChild(Type value)
{
	TreeNode<Type> *newNode = new TreeNode<Type>(value);  // 创建新节点
	if (current->firstChild == 0)  // 当前节点无子女时，新节点成为其第一个子女
		current->firstChild = newNode;
	else {  // 当前节点有子女时
		TreeNode<Type> *p = current->firstChild;  // 找当前节点第一个子女
		while (p->nextSibling != 0)  // 扫描兄弟链，找最后一个子女
			p = p->nextSibling;
		p->nextSibling = newNode;   // 新节点成为其最后的子女
	}
}

// 删除树中当前节点的第i个子女及其全部子孙节点
template<class Type> bool Tree<Type>::RemoveChild(int i)
{
	if (i == 1) {  // 要删的是第一个子女
		TreeNode<Type> *s = current->firstSibling;  // 要删的节点是*s
		if (s != 0)
			current->firstSibling = s->nextSibling;  // 将s从链中摘下
		else
			return false;
	}
	else {  // 要删的不是第一个子女
		TreeNode<Type> *q = current->firstChild;
		int k = 1;
		while (q && k < i - 1) {  // 寻找第i-1个子女节点
			q = q->nextSibling;
			k++;
		}
		if (q) {
			TreeNode<Type> *s = q->nextSibling;
			if (s)
				q->nextSibling = s->nextSibling;
			else
				return false;
		}
		else 
			return false;
	}
	RemoveTree(s);
	return true;
}

// 私有函数: 删除以p为根的子树
template<class Type> void Tree<Type>::RemovesubTree(TreeNode<Type> *p) 
{
	TreeNode<Type> *q = p->firstChild;
	TreeNode<Type> *next;
	while (q) {
		next = q->nextSibling;
		RemovesubTree(q);
		q = next;
	}

	delete p;
}

// 私有函数: 删除以当前节点current为根的子树
template<class Type> void Tree<Type>::RemoveTree() 
{
	if (current) {
		if (current == root)
			root = 0;
		RemoveTree(current);
		current = 0;
	}
}

// 以当前指针current为根，进行先根次序遍历
template<class Type> void Tree<Type>::PreOrder()
{
	if (!IsEmpty()) {  // 非空
		cout << current->data << ' ';
		TreeNode<Type> *p = current; // 保存当前指针
		bool i = FirstChild();  // 找根的第一棵子树
		while (i) {
			PreOrder();
			i = NextSibling(); // 先根次序遍历所有子树
		}

		current = p;  // 恢复当前指针
	}
}

// 以当前指针current为根，进行后根次序遍历
template<class Type> void Tree<Type>::PostOrder()
{
	if (!IsEmpty()) {  // 非空		
		TreeNode<Type> *p = current; // 保存当前指针
		bool i = FirstChild();  // 找根的第一棵子树
		while (i) {
			PostOrder();
			i = NextSibling(); // 先根次序遍历所有子树
		}

		current = p;  // 恢复当前指针
		cout << current->data << ' ';
	}
}

#endif // TREE_H