1.树由称作根的结点r以及零个或多个非空的（子树）T1，T2，...Tk组成，这些子树中每一棵的根都被来自根r的一条有向的边所连接。每一棵子树的根叫做根r的儿子，而r是每一课子树的根的父亲。一棵树是N个结点和N-1条边的集合。其中的一个结点叫做根。每条边都将某个结点连接到它的父亲，而除去根结点外每个结点都有一个父亲。没有儿子的结点称为叶结点。具有相同父亲的结点为兄弟。
2.从结点n1到nk的路径定义为结点n1,n2,...nk的一个序列。路径的长为路径上的边的条数，即k-1。从每一个结点到它自己有一条长为0的路径。对任意结点ni,ni的深度为从根到ni的唯一路径的长。根的深度为0。ni的高是从ni到一片树叶的最长路径的长。因此所有的树叶的高都是0。一棵树的高等于它的根的高。
3.树的实现：
将每个结点的所有儿子都放在树结点的链表中：
struct TreeNode
{
Object element;
TreeNode *firstChild; //指向第一个儿子
TreeNode *nextSibling; //指向下一个兄弟
};
4.树的遍历：
前序遍历：
//伪码，源码如何实现？？
void FileSystem::listAll( int depth=0 )const
{
printName(depth); //print the name of the object
if( isDirectory() )
for each file c in the directory (for each child)
c.listAll(depth+1);
}
后序遍历：
int FileSystem::size() const
{
int totalSize=sizeOfThisFile();
if(isDirectory())
for each file c in this directory( for each child )
totalSize+=c.size();
return totalSize;
}
5.二叉树：
（1）二叉树是一棵每个结点都不能有多于两个儿子的树。
二叉树的一个性质是平均二叉树的深度要比结点个数N小得多。这个平均深度为O(√N)。而对于特殊类型的二叉树，即二叉查找树，其深度的平均值是O(logN)。
（2）实现：
因为一个二叉树结点最多有两个儿子，因此可以直接链接他们：
struct BinaryNode
{
Object element; //the data in the node
BinaryNode *left; //left child
BinaryNode *right; //right child
};
（3）表达式树：
表达式树的树叶是操作数，其他结点是操作符。
6.二叉查找树：
性质：对于树的每个结点X,它的左子树中所有项的值小于X中的项。而它的右子树中所有项的值大于X中的项。
下面是一个BinarySearchTree类模板的接口，查找是基于<操作符的,而该操作符对特定的Compareble类型必须定义：
template <typename Comparable>class BinarySearchTree{public: BinarySearchTree(); BinarySearchTree( const BinarySearchTree &rhs); ~BinarySearchTree();
const Comparable &findMin() const ; const Comparable &findMax() const; bool contains( const Comparable &x) const; bool isEmpty() const; void printTree() const; void makeEmpty(); void insert( const Comparable &x); void remove( const Comparable &x); const BinarySearchTree & operator=(const BinarySearchTree &rhs);private: struct BinaryNode; { Comparable element; BinaryNode *left; BinaryNode *right; BinaryNode( const Comparable &theElement,BinaryNode *lt,BinaryNode *rt) :element(theElement),left(lt),right(rt) {} }; BinaryNode *root; void insert( const Comparable &x,BinaryNode *&t) const; void remove( const Comparable &x,BinaryNode *&t) const; BinaryNode * findMin(BinaryNode *t) const; BinaryNode *findMax(BinaryNode *t) const; bool contains( const Comparable &x,BinaryNode *t) const; void printTree( BinaryNode * &t); void printTree( BinaryNode *t) const; BinaryNode *clone(BinaryNode *t) const;};
contains:如果在树X中有项为X的结点，那么contains操作就返回true，否则，若没有这样的结点就返回false。树结构使得该操作很简单。如果T为空，那么就可以返回false，否则，如果存储在T中的项为X，就返回true。
bool contains ( const Comparable &x) const{ return contains(x,root);}
bool contains( const Comparable &x,BinaryNode *t) const
{
if(t==NULL)
return false;
else if(x<t->element)
return contains(x,t->left);
else if(t->element<x)
return contains(x,t->right);
else
return true; //Match
}
注意首先要对是否为空树进行验证，如果不这么做就会产生一个企图通过NULL指针访问数据成员的运行错误。
下面是使用函数对象而不是使用Comparable项所需要做的微小修改：
template <typename Object,typename Comparator=less<Object> >class BinarySearchTree{public: //same methods,with Object replacing Comparableprivate: BinaryNode *root; Comparator isLessThan; //same methods,with Object replacing Comparable bool contains( const Object &x,BinaryNode *t) const { if(t==NULL) return false; else if( isLessThan(x,t->element) ) return contains(x,t->left); else if( isLessThan(t->element,x) ) return contains(x,t->right); else return true; //Match }};
findMin和findMax:
这两个private例程分别指向树中包含最小元和最大元的结点的指针。为了执行findMin，从根开始并且只要有左儿子就向左进行。终止点就是最小元素。findMax例程除分支朝向右儿子外其余过程相同。
用递归编写findMin而非递归编写findMax：
BinaryNode *findMin(BinaryNode *t) const
{
if(t==NULL)
return NULL;
if(t->left==NULL)
return t;
return findMin(t->left);
}
BinaryNode *findMax( BinaryNode *t) const
{
if(t!=NULL)
while(t->right!=NULL)
t=t->right;
return t;
}
7.insert:
