一、二叉树
定义：每个节点都不能有多于两个的儿子的树。
二叉树节点声明：
struct treeNode
{
elementType element;
treeNode * left;
treeNode * right;
}
应用：
中缀表达式——>后缀表达式（栈的应用）——>表达式树（栈的应用2）
栈的应用2：读取后缀表达式，操作数入栈，遇操作符后，指向栈里前两位元素t1和t2的指针出栈（t1先弹出，作为该操作符的右儿子），并将指向该操作符的指针入栈。
二、二叉查找树
定义：
结构性：二叉树；
排序性：右子树中最小值 > X关键字 > 左子树中最大值（对任意节点关键字X均成立）
1、清空树（递归）makeEmpty
searchTree * makeEmpty( searchTree * T)
{
if( T != NULL)
{
makeEmpty( T -> left);
makeEmpty( T -> right);
delete (T); // 基准情况
}
return T;
}
2、Find
searchTree * find( elementType X , searchTree * T)
{
if( T = NULL)
return NULL; //非空判断 if(X < T->element)
return find (X , T->left);
else
if(X > T->element)
return find(X , T->right);
else
return T; //找到元素X
}
3、findMin && findMax（举一例，（非）递归法，利用其排序性找到相应节点）
递归法：
searchTree * findMax( searchTree * T)
{
if( T = NULL)
return NULL; //非空判断
else
if(T->right == NULL)
return T; //基准情况
else
return findMax(T->right);
}
非递归法：
searchTree * findMax( searchTree * T)
{
if( T = NULL)
return NULL; //非空判断
else
while(T->right != NULL)
T = T->right;
return T;
}
4、insert
searchTree * insert( elementType X , searchTree * T)
{
if( T == NULL)
{
T = searchTree New(searchTree);
if(T == NULL)
cout << "out of space." << endl;
else
{
T->element = X;
T->left = T->right = NULL;
}
}
else
if(X < T->element)
T->left = insert(X , T->left);
else
if(X > T->element)
T->right = insert(X , T->right); return T;
}
5、delete
searchTree * delete( elementType X , searchTree * T)
{
searchTree * tem;
tem = (searchTree *) New searchTree;
if( T == NULL)
return NULL;
else
if(X < T->element)
T->left = delete(X , T->left);
else
if(X > T->element)
T->right = delete(X , T->right);
else
if(T->left && T->right)
{
tem = findMin(T->right);
T->element = tem->element;
// tem = delete(tem->element , tem);
T->right = delete(T->element , T->right);
}
else
{
tem = T;
if(T->left == NULL)
T = T->right;
if(T->right == NULL)
T = T->left;
delete(tem);
}
return T;
}
三、AVL树
定义：每个节点的左子树和右子树的高度最多差1的二叉查找树。（空树的高度定义为-1）
插入后，只有那些从 插入点 到 根节点 的路径上的节点的平衡可能被改变，所以沿着 插入点 回溯到 根节点的这条路径并更新平衡信息，就可以找到破坏AVL平衡条件的节点。
（第一个这样的节点 即破坏性节点中最深的节点）。
破坏平衡性的节点设为a，则a的左右子树高度差为2，新节点插入点：
1、a的左儿子的左子树（单旋转）
2、a的左儿子的右子树（双旋转）
3、a的右儿子的左子树（单旋转）
4、a的右儿子的右子树（双旋转）
1、节点声明
struct avlNode
{
elementType element;
avlNode left;
avlNode right;
int height;
}
2、高度信息
static int height( avlNode *P)
{
if( P == NULL)
return -; //基准情况
else
return max( height(P->left) , height(P->right) ) + ;
}
3、节点插入
avlTree *insert(elementType X , avlTree *T)
{
if(T == NULL)
{
T = (avlTree*) New avlTree;
if(T == NULL)
cout << "out of space" << endl;
else
{
T->element = X;
T->left = T->right = NULL;
}
}
else
if(X < T->element)
{
T->left = insert (X , T->left);
if(height(T->left) - height(T->right) == )
{
if(X < T->left->element)
T = singleRotateWithLeft(T);
else
T = doubleRotateWithLeft(T);
}
}
else
if(X > T->element)
{
T->right = insert (X , T->right);
if(height(T->right) - height(T->left) == )
{
if(X > T->right->element)
T = singleRotateWithRight(T);
else
T = doubleRotateWithRight(T);
}
}
T->height = height(T); //更新高度信息
return T;
}
4、旋转（给出一组单双旋转）
static avlTree *singleRotateWithLeft(avlTree *T1)
{
avlTree *T2;
T2 = T1->left; T1->left = T2->right;
T2->right = T1;
T1->height = height(T1); //更新高度信息
T2->height = height(T2); return T2;
}
static avlTree *doubleRotateWithLeft(avlTree *T1)
{
T1->left = singleRotateWithRight(T1->left);
// 在旋转中已经有返回值，此时不写return亦可
rerurn singleRotateWithLeft(T1);
}
四、树的遍历（递归）
中序遍历：左-中-右
后序遍历：左-右-中（先遍历儿子）
前序遍历：中-左-右（先遍历祖先）
中序遍历：
void printTree(searchTree *T)
{
if(T != NULL)
{
printTree(T->left);
cout<< T->element << endl;
printTree(T->right);
}
}