二叉树的存储表示

在数据处理过程中二叉树的大小、形态不发生剧烈的动态变化的场合，适宜采用数组方式来表示二叉树的抽象数据类型
1、完全二叉树的数组存储表示
设有一棵完全二叉树，将其所有结点按照层次自顶向下、同一层自左向右进行按序编号1 - n，得到一个结点的顺序（线性）序列。在数组下标为 i 的位置，存放编号为 i 的完全二叉树的结点。这种存储表示是存储完全二叉树最简单、最省存储的方式，因为可以从一个结点的编号推算出它的父结点、子女、兄弟等结点的编号

数组存储的缺陷：对待一般二叉树来说，有可能导致浪费大量存储空间。

使用链式存储，可以在形态剧烈变化的二叉树中，克服数组存储的缺点

1、根据二叉树的定义，每一个结点都有两个分支，指向左、右子树。所以二叉树的结点至少包括三个域：数组data、左子女指针left、右子女指针right。其称为二叉链表，可以很方便地找到左右子结点，但是找到其父结点很困难。

2、在含有n个结点的二叉链表中有n+1个空链指针域，因为在所有结点的2n个链指针域只有n-1个存有边信息的缘故。

在二叉链表的基础上，增加指向parent的指针，便于查找任意结点的父结点。三链表则有n+2个空链指针域。

template
struct BinTreeNode{
	T data;
	BinTreeNode *leftChild, *rightChild;
	BinTreeNode(): leftChild(nullptr), rightChild(nullptr){}
	BinTreeNode(T x, BinTreeNode *l = nullptr, BinTreeNode *r = nullptr)
		:data(x), leftChild(l), rightChild(r){}
};

template
class BinaryTree{
public:
	BinaryTree(): root(nullptr){}               //构造函数
	BinaryTree(T value): RefValue(value), root(nullptr){}         //构造函数
	BinaryTree(BinaryTree& s);          //复制构造函数
	~Binary(){ destroy(root); } 				//析构函数
	bool IsEmpty(){ return (root == nullptr) ? true : false; }             //判断二叉树空否
	BinTreeNode* Parent(BinTreeNode *current)                       //返回父结点
		{return (root == NULL || root == current)?NULL:Parent(root, current); }
	BinTreeNode* LeftChild(BinTreeNode *current)                    //返回左子女
		{return (current != NULL)?current->leftChild:NULL; }
	BinTreeNode* RightChild(BinTreeNode *current)					  //返回右子女
		{return (current != NULL)?current->rightChild:NULL; }
	int Height() { return Height(root); }                                 //返回树高度
	int Size() {return Size(root); }                                      //返回结点数
	BinTreeNode* getRoot() const {return root; }                       //取根
	void preOrder(void (*visit)(BinTreeNode* p))                       //前序遍历
		{preOrder(root, visit); }
	void inOrder(void (*visit)(BinTreeNode* p))                        //中序遍历
		{inOrder(root, visit); }
	void postOrder(void (*visit)(BinTreeNode* p))                      //后序遍历
		{postOrder(root, visit); }
	int Insert(const T& item);                                            //插入新元素
	BinTreeNode* Find(T& item)const;                                   //搜索
protected:
	BinTreeNode* root;                                                 //二叉树的根指针
	T RefValue;                  										  //数据输入停止标志
	void CreateBinTree(istream& in, BinTreeNode* &subTree);            //从文件读入建树
	bool Insert(BinTreeNode* &subTree, const T& x);                    //插入
	void destroy(BinTreeNode* &subTree);								  //删除                      
	bool Find(BinTreeNode* subTree, const T& x)const;                  //查找
	BinTreeNode* Copy(BinTreeNode* orignode);                       //复制
	int Height(BinTreeNode* subTree);								  //返回树高度
	int Size(BinTreeNode *sunTree);                                    //返回结点数
	BinTreeNode* Parent(BinTreeNode* subTree, BinTreeNode* current);      //返回父结点
	BinTreeNode* Find(BinTreeNode* subTree, const T& x)const;         //搜寻x
	void Traverse(BinTreeNode* subTree, ostream& out);                 //前序遍历输出
	void preOrder(BinTreeNode* subTree, void (*visit)(BinTreeNode* p))               //前序遍历
	void inOrder(BinTreeNode* subTree, void (*visit)(BinTreeNode* p))                //中序遍历
	void postOrder(BinTreeNode* subTree, void (*visit)(BinTreeNode* p))              //后序遍历
	friend istream& operator>>(istream& in, BinaryTree& Tree);			//重载输入操作符
	friend ostream& operator<<(ostream& out, BinaryTree& Tree);			//重载输出操作符
};

//删除根为subTree的子树
template
void BinaryTree::destroy(BinTreeNode* &subTree){
	if(subTree != nullptr){
		destroy(subTree->leftChild);
		destroy(subTree->rightChild);
		delete subTree;
	}
};

//搜索current结点的父结点
template
BinTreeNode* BinaryTree::Parent(BinTreeNode* subTree, BinTreeNode* current){
	if(subTree == nullptr){
		return nullptr;
	}
	if(subTree -> leftChild == current || subTree -> rightChild == current){
		return subTree;
	}
	BinTreeNode *p;
	if((p = Parent(subTree->leftChild, current)) != nullptr) return p;
	else return Parent(subTree->rightChild, current);
};

//搜索并输入根为subTree的二叉树
template
void BinaryTree::Traverse(BinTreeNode *subTree, ostream& out){
	if(subTree != nullptr){
		out << subTree -> data << ' ';            //输出当前结点的数据
		Traverse(subTree->leftChild, out);	      //输出
		Traverse(subTree->rightChild, out);
	}
};

//重载输入操作符
template
istream& operator>>(istream& in, BinaryTree& Tree){
	CreateBinTree(in, Tree.root);                     //采用广义表表示的建立二叉树的算法
	return in;
}

//重载输出操作符
template
ostream& operator<<(ostream& out, BinaryTree& Tree){
	out << "输出二叉树的前序遍历n";
	Tree.Traverse(Tree.root, out);
	out << endl;
	return out;
}

假定有一广义表 A（B（D，E（G，）），C（，F））#
算法基本思路：依次从保存广义表的字符串中输入字符。
1、以字母作为结点的值，k=1时为左子女，k=2时为右子女。
2、遇到左括号，表示子表开始；遇到右括号，表示子表结束。
3、遇到逗号，则表示左子女处理完毕，接着处理右子女，k置为2，直到#。在进入子表之前将根结点入栈，子表处理结束之后退栈。

template
void BinaryTree::CreateBinTree(istream& in, BinTreeNode* &subTree){
	stack*> s;               //存放根结点的栈
	subTree = nullptr;						//置空二叉树
	BinTreeNode *p, *t;
	int k;									//作为处理左、右子树标记
	T ch;
	in >> ch;        						//从in顺序读入一个字符
	while (ch != RefValue) {
		switch (ch) {
		case '(': s.push(p); k = 1; break;			//进入子树
		case ')': s.pop(); break;					//退出子树
		case ',': k = 2; break;						//处理右子树
		default: p = new BinTreeNode(ch);	
			if (subTree == nullptr) subTree = p;
			else if (k == 1) {
				t = s.top();
				t->leftChild = p;					//链接左子女
			}
			else {
				t = s.top();
				t->rightChild = p;					//链接右子女
			}
		}
		in >> ch;
	}
}