1 树概述

• 树：在层次化的数据元素之间有祖先-后代、上级-下属、整体-部分以及其他类似的关系。
• 根和子树：树t为非空有限集合，其中一个元素为根，其余组成t的子树。
• 级：树根为1级，其孩子是2级，孩子的孩子为3级，以此类推。
• 高度（深度）：树中级的个数。
• 元素的度：其孩子的个数。
• 树的度：其元素的度的最大值。

2 二叉树特性及常用操作

2.1 二叉树特性
与普通树根本区别：
（1）每个元素恰好有两棵子树
（2）每个元素的子树是有序的，左子树和右子树
（3）二叉树可以为空
例：表达式树

特性：
（1）有n各元素，必有n-1条边
（2）有n个元素，高度最小$log_2(n+1)$log2​(n+1)，最大n
（3）高度为h，最少h个元素，最多$2^h-1$2h−1个元素
（4）完全二叉树某元素编号为i，$1\le i \le n$1≤i≤n，有以下关系成立：

• $i=1$i=1，该元素为根，其父节点编号为$i/2$i/2
• $2i>n$2i>n，该元素无左孩子，否则左孩子为$2i$2i
• $2i+1>n$2i+1>n，该元素无右孩子，否则右孩子为$2i+1$2i+1
  2.2 二叉树描述
  数组描述
  看做缺少部分元素的完全二叉树，适用于缺少的元素数目较少的情况。
  
  从0开始，最坏的空间需求是$2^n-1$2n−1（右斜树）
  链表描述
  用一个结构表示：两个指针域+一个element域
  
  具有n个元素的二叉树仅有n-1个边，所以有n+1个指针没有值，被设置成NULL。

#ifndef binaryTreeNode_
#define binaryTreeNode_

using namespace std;

template <class T>
struct binaryTreeNode
{
	T element;
	binaryTreeNode<T>* leftChild,   // left subtree
		* rightChild;  // right subtree

	binaryTreeNode() { leftChild = rightChild = NULL; }
	binaryTreeNode(const T& theElement) :element(theElement)
	{
		leftChild = rightChild = NULL;
	}
	binaryTreeNode(const T& theElement,
		binaryTreeNode* theLeftChild,
		binaryTreeNode* theRightChild)
		:element(theElement)
	{
		leftChild = theLeftChild;
		rightChild = theRightChild;
	}
};
#endif

2.3 二叉树常用操作

以上操作可通过对二叉树的遍历实现。
2.4 二叉树遍历
常用的4中遍历方法：

• 前序遍历

template <class T>
void preOrder(binaryTreeNode<T> *t){
	//前序遍历二叉树*t
	if (t != NULL){
		visit(t);//访问树根
		preOrder(t -> leftChild);//前序遍历左子树
		preOrder(t -> rightChild);//前序遍历右子树
	}
}

• 中序遍历

template <class T>
void inOrder(binaryTreeNode<T> *t){
	//中序遍历二叉树*t
	if (t != NULL){
		inOrder(t -> leftChild);//中序遍历左子树
		visit(t);//访问树根
		inOrder(t -> rightChild);//中序遍历右子树
	}
}

• 后序遍历

template <class T>
void postOrder(binaryTreeNode<T> *t){
	//后序遍历二叉树*t
	if (t != NULL){
		postOrder(t -> leftChild);//中序遍历左子树
		postOrder(t -> rightChild);//中序遍历右子树
		visit(t);//访问树根
	}
}

前三种方法相同之处：左子树先于右子树遍历
区别在于：对每个节点访问时间不同
***例：***对下图三个数分别用上述三种遍历方法进行遍历

结果如下：

其中，遍历方法visit(t)程序如下：

template <class T>
void visit(binaryTreeNode<T> *x){
	cout << x -> element << ' ';
}

• 层次遍历
  从顶层到底层，在同一层中，从左到右，依次访问树的元素
  需要队列的支持，故很难编写递归程序。

template <class T>
void levelOrder(binaryTreeNode<T> *t)
{
	arrayQueue<binaryTreeNode<T>*> q;
	while (t != NULL)
	{
		theVisit(t);  // visit t

		// put t's children on queue
		if (t->leftChild != NULL)
			q.push(t->leftChild);
		if (t->rightChild != NULL)
			q.push(t->rightChild);

		// get next node to visit
		try { t = q.front(); }
		catch (queueEmpty) { return; }
		q.pop();
	}
}

3 二叉树实现

3.1 抽象数据类型

3.2 类linkedBinaryTree
声明如下：

template<class E>
class linkedBinaryTree : public binaryTree<binaryTreeNode<E> >
{
public:
	linkedBinaryTree() { root = NULL; treeSize = 0; }
	~linkedBinaryTree() { erase(); };
	bool empty() const { return treeSize == 0; }
	int size() const { return treeSize; }
	E* rootElement() const;
	void makeTree(const E& element,
		linkedBinaryTree<E>&, linkedBinaryTree<E>&);
	linkedBinaryTree<E>& removeLeftSubtree();
	linkedBinaryTree<E>& removeRightSubtree();
	void preOrder(void(*theVisit)(binaryTreeNode<E>*))
	{
		visit = theVisit; preOrder(root);
	}
	void inOrder(void(*theVisit)(binaryTreeNode<E>*))
	{
		visit = theVisit; inOrder(root);
	}
	void postOrder(void(*theVisit)(binaryTreeNode<E>*))
	{
		visit = theVisit; postOrder(root);
	}
	void levelOrder(void(*)(binaryTreeNode<E>*));
	void preOrderOutput() { preOrder(output); cout << endl; }
	void inOrderOutput() { inOrder(output); cout << endl; }
	void postOrderOutput() { postOrder(output); cout << endl; }
	void levelOrderOutput() { levelOrder(output); cout << endl; }
	void erase()
	{
		postOrder(dispose);
		root = NULL;
		treeSize = 0;
	}
	int height() const { return height(root); }
protected:
	binaryTreeNode<E>* root;                // pointer to root
	int treeSize;                           // number of nodes in tree
	static void (*visit)(binaryTreeNode<E>*);      // visit function
	static int count;         // used to count nodes in a subtree
	static void preOrder(binaryTreeNode<E>* t);
	static void inOrder(binaryTreeNode<E>* t);
	static void postOrder(binaryTreeNode<E>* t);
	static void countNodes(binaryTreeNode<E>* t)
	{
		visit = addToCount;
		count = 0;
		preOrder(t);
	}
	static void dispose(binaryTreeNode<E>* t) { delete t; }
	static void output(binaryTreeNode<E>* t)
	{
		cout << t->element << ' ';
	}
	static void addToCount(binaryTreeNode<E>* t)
	{
		count++;
	}
	static int height(binaryTreeNode<E>* t);
};

方法定义略。

4 应用

设置信号放大器
并查集