虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等. 在二叉查找树b中查找x的过程为： 1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的数据域之值，则查找成功；否则： 3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：
4. 查找右子树。
/* 以下代码为C++写成, 下同 */
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){ //在根指针T所指二元排序樹中递归地查找其關键字等於key的數據元素，若查找成功，
//則指针p指向該數據元素節點，并返回TRUE，否則指针指向查找路徑上訪問的最後
//一個節點并返回FALSE，指针f指向T的雙親，其初始调用值為NULL if(!T) { //查找不成功 p=f;
return false; }
else if (key == T->data.key) { //查找成功 p=T;
return true; }
else if (key < T->data.key) //在左子樹中繼續查找 return SearchBST(T->lchild, key, T, p); else //在右子樹中繼續查找
return SearchBST(T->rchild, key, T, p); }
向一个二叉查找树b中插入一个节点s的算法，过程为：
1. 若b是空树，则将s所指结点作为根节点插入，否则： 2. 若s->data等于b的根节点的数据域之值，则返回，否则：
3. 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，
否则：
4. 把s所指节点插入到右子树中。
/*当二元搜尋樹T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，否则返回FALSE*/
Status InsertBST(BiTree &T, ElemType e){ if(!SearchBST(T, e.key, NULL,p){ s = new BiTNode;
s->data = e; s->lchild = s->rchild = NULL;
if(!p)
T=s; //被插節点*s为新的根结点 else if (e.key < p->data.key)
p->lchild = s; //被插節点*s为左孩子 else
p->rchild = s; //被插節点*s为右孩子 return true; }
else
return false; //树中已有关键字相同的節点，不再插入 }
在二叉排序树删除结点的算法[编辑]
在二叉排序树删去一个结点，分三种情况讨论：
1. 若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶
子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。 2. 若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双
亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉排序树的特性。
3. 若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的
相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令*p的左子树为*f的左/右(依*p是*f的左子树还是右子树而定)子树，*s为*p左子树的最右下的结点，而*p的右子树为*s的右子树；其二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或
直接后继）。在二叉排序树上删除一个结点的算法如下： Status DeleteBST(BiTree &T, KeyType key){ //若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素，并返回
//TRUE；否则返回FALSE if(!T)
return false; //不存在关键字等于key的数据元素 else{
if(key == T->data.key) { // 找到关键字等于key的数据元素 return Delete(T); }
else if(key < T->data.key)
return DeleteBST(T->lchild, key); else
return DeleteBST(T->rchild, key); } }
Status Delete(BiTree &p){ //该节点为叶子节点，直接删除
if (!p->rchild && !p->lchild) {
delete p; }
else if(!p->rchild){ //右子树空则只需重接它的左子树 q=p->lchild;
p->data = p->lchild->data; p->lchild=p->lchild->lchild; p->rchild=p->lchild->rchild;'
delete q; }
else if(!p->lchild){ //左子树空只需重接它的右子树 q=p->lchild;
p->data = p->rchild->data; p->lchild=p->rchild->lchild; p->rchild=p->rchild->rchild;'
delete q; }
else{ //左右子树均不空 q=p;
s=p->lchild;
while(s->rchild){ q=s;
s=s->rchild;
} //转左，然后向右到尽头
p->data = s->data; //s指向被删结点的“前驱” if(q!=p)
q->rchild = s->lchild; //重接*q的右子树 else
q->lchild = s->lchild; //重接*q的左子树 delete s; }
return true; }
8. 二叉平衡树的插入结点的原理，有哪几种旋转方式？分别适用于哪种情况。分析二叉平衡树的时间复杂度。
平衡二叉树关于树的深度是平衡的，具有较高的检索效率。平衡二叉树或是一棵空树，或是
具有下列性质的二叉排序树：其左子树和右子树都是平衡二叉树，而且左右子树深度之差绝对值不超过1. 由此引出了平衡因子（balance factor）的概念，bf定义为该结点的左子树的深度减去右子树的深度（有些书是右子树深度减去左子树深度，我是按照左子树减去右子树来计算的，下面的代码也是这样定义的），所以平衡二叉树的结点的平衡因子只可能是 -1，0，1 ，某个结点的平衡因子绝对值大于1，该二叉树就不平衡。
平衡二叉树在出现不平衡状态的时候，要进行平衡旋转处理，有四种平衡旋转处理（单向右旋处理，单向左旋处理，双向旋转（先左后右）处理，双向旋转（先右后左）处理），归根到底是两种（单向左旋处理和单向右旋处理）。
AVL树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的\旋转\。
平衡二叉搜索树(Balanced Binary Tree)是一种结构平衡的二叉搜索树，即叶节点深度差不超过1，它能在O(log n)内完成插入、查找和删除操作。
9. 红黑树的定义，红黑树的性能分析和与二叉平衡树的比较。 红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为\对称二叉B树\，它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。 红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求: 性质1. 节点是红色或黑色。 性质2. 根是黑色。
性质3. 所有叶子都是黑色（叶子是NIL节点）。
性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
10. 图有哪些储存表示。
图的存储表示[编辑]
? ? ? ? ? 数组（邻接矩阵）存储表示（有向或无向） 邻接表存储表示 前向星存储表示 有向图的十字链表存储表示 无向图的邻接多重表存储表示
11. 链表插入排序、链表归并排序。
12. 常见的有哪几种排序算法，试比较其时间复杂度，以及是否稳定，及各自使用的情形。 常用的排序算法的时间复杂度和空间复杂度 排序法 冒泡排序 快速排序 选择排序 最差时间分析 O(n2) O(n2) O(n2) 平均时间复杂度 O(n2) O(n*log2n) O(n2) O(n*log2n) O(n2) O(n*log2n) 稳定度 稳定 不稳定 稳定 不一顶 稳定 不稳定 空间复杂度 O(1) O(log2n)~O(n) O(1) O(n) O(1) O(1) 二叉树排序 O(n2) 插入排序 O(n2) 堆排序 O(n*log2n)