BST算法题
1. 红黑树——插入、双红修正
模拟插入关键码e //设T中本不含e
按BST的常规算法插入 // x = insert(e)必为末端节点
设x的父亲p = x->parent存在 //否则，即平凡的渗源局首次插入
将x染红（除非它是根） //x->color = isRoot(x) ? B : R
双红缺陷(double-red) //p->color == x->color == R
考查：x的祖父 g = p->parent //g != null && g->color == B
p的兄弟 u = p== g->lc ? g->rc : g->lc
实现：
template <typename T> BinNodePosi(T) RedBlack<T>::insert(const T & e){
//确认目标节点不存在（留意对_hot的设置）
BinNodePosi(T) & x =search(e); if(x) return x;
//创建红节点x，以_hot为父，黑高度-1
x = new BinNode<T>(e,_hot,NULL,NULL,-1);
_size++;
//如有必要，做双红修正
solveDoubleRed(x);
//返回插入节点
return x ? x : _hot->parent;
} //无论原树中是否有e，返回时总有x->data == e
RR-1:u->color == B
此时：x、p、g的四个孩子（可能是外部节点）全为黑，且黑高度相同
1.参照AVL树算法，做局部3+4重构
将节点x、p、g及其四棵子树，按中序组合为：T0<a<T1<b<T2<c<T3
2.染色：b转黑，a或c转红
RR-2:u->color == R
在B-树中，等效于超级节裂侍点发丛让生上溢
p与u转黑，g转红
在B-树中，等效于节点分裂，关键码g上升一层
双红修正：复杂度
重构、染色均属常数时间的局部操作，统计其总次数
红黑树的每一次插入操作都可在O(logn)时间内完成
其中至多做：
1.O(logn)次节点染色
2.一次"3+4"重构
2. 写算法 求二叉排序树 从小到大结点的序列
表示很简单。。。。。。
#include <stdio.h>大态毁
#include <stdlib.h>
#include <time.h>
#define MAX 30
typedef int DataType;
typedef struct node
{
DataType Data;
struct node * lchild, * rchild;
}BSTNode,*BTree;
BSTNode * BST;DataType A[MAX], flag=0;
int InsertBST(BSTNode * &p, DataType d) //插入结点
{
if (p==NULL)
{
p=(BSTNode *)malloc(sizeof(BSTNode));
p->Data=d;
p->lchild=p->rchild=NULL;
return 1;
}
else if (d==p->Data)
return 0;
else if (d<p->Data)
return InsertBST(p->lchild, d);
else
return InsertBST(p->rchild, d);
}
BSTNode * CreatBST(DataType A[], int n) //创建二叉排序树
{
BSTNode * bt = NULL;
for (int i=0; i<n; i++)
InsertBST(bt, A[i]);
return bt;
}
void PrintBST(BSTNode * p) // 括号表示法输出二叉排序树
{
if (p!=NULL)
{
printf("%d", p->Data);
if (p->lchild!=NULL||p->rchild!=NULL)
{
printf("(");
PrintBST(p->lchild);
if (p->rchild!=NULL) printf(",");
PrintBST(p->rchild);
printf(")");
}
}
}
void SearchBST(BSTNode * bt, DataType d) //查找结点
{
if (bt==NULL)
printf("查找失败，无此关键字!");
else if (d==bt->Data)
{
A[flag++]=bt->Data;
printf("查找成功，查找路径为:");
for (int i=0; i<flag; i++)
printf("->%d", A[i]);
flag=0;
}
else
{
A[flag++]=bt->Data;
if (d<闭伍bt->Data)
SearchBST(bt->lchild, d);
else if (d>bt->Data)
SearchBST(bt->rchild, d);
}
}
void Delete(BSTNode * &p);void Delete1(BSTNode * p, BSTNode * &r);
int DeleteBST(BSTNode * &bt, DataType d) // 删除结滚备点
{
if (bt==NULL)
return 0;
else
{
if (d<bt->Data)
return DeleteBST(bt->lchild, d);
else if (d>bt->Data)
return DeleteBST(bt->rchild, d);
else
{
Delete(bt);
return 1;
}
}
}
void Delete(BSTNode * &p)
{
BSTNode * q;
if (p->rchild==NULL)
{
q=p; p=p->lchild; free(q);
}
else if (p->lchild==NULL)
{
q=p; p=p->rchild; free(q);
}
else Delete1(p, p->lchild);
}
void Delete1(BSTNode * p, BSTNode * &r)
{
BSTNode * q;
if (r->rchild!=NULL)
Delete1(p, r->rchild);
else
{
p->Data=r->Data; q=r; r=r->lchild; free(q);
}
}
void Choose(int t) // 菜单选项
{
switch(t)
{
case 1: // 创建
{
int a[MAX], n,i;
printf("请输入关键字个数:");
scanf("%d", &n);
srand(time( NULL ) );
for( i = 0; i < n;i++ )
{a[i]=rand()%100+1;
printf( "%d\n", a[i]);
}
BST = CreatBST(a, n);
printf("该二叉排序树表示为:");
PrintBST(BST);
printf("\n");
}break;
case 2: // 插入
{
int d;
printf("请输入要插入的关键字:");
scanf("%d", &d);
if (InsertBST(BST, d))
{
printf("该二叉排序树表示为:");
PrintBST(BST);
}
else
printf("插入失败，已存在此关键字!");
printf("\n");
}break;
case 3:
{
int d;
printf("请输入要查找的关键字:");
scanf("%d", &d);
SearchBST(BST, d);
printf("\n");
}break;
case 4: // 删除
{
int d;
printf("请输入要删除的关键字:");
scanf("%d", &d);
if (DeleteBST(BST, d))
{
printf("该二叉排序树表示为:");
PrintBST(BST);
}
else
printf("删除失败，无此关键字!");
printf("\n");
}break;
case 5: // 重置
{
BST = NULL;
printf("已重置，请继续选择操作!\n");
}break;
default:
printf("无效输入，请重新选择!\n"); break;
}
}
void main()
{
int x;
printf("---------------------\n");
printf("二叉排序树\n");
printf("---------------------\n");
printf("1.创建\n");
printf("2.插入\n");
printf("3.查找\n");
printf("4.删除\n");
printf("5.重置\n");
printf("6.退出\n");
printf("---------------------\n");
printf("请选择你要的操作:");
scanf("%d",&x);
while (x!=6)
{
Choose(x);
printf("\n请选择你要的操作:");
scanf("%d",&x);
}
}
3. 红黑树——删除、双黑缺陷
首先按照BST常规算法，执行：r = removeat(x,_hot)
x由孩子r接替 //另一孩子记作w（即黑的NULL）
条件1和2依然满基喊足，但3和4不一定 //在原树中，考查x与r
若二者之一为红，则3和4不难满足
双黑缺陷
若x与r均黑double-black
摘除x并代之以r后，全树黑深度郑坦不再统一，原B-树中x所属节点下溢
在新树中，考查r的父亲p = r->parent， r的兄弟s = r==p->lc ? p->rc : p->lc
以下分四种情况处理
BB-1：s为黑，且至少有一个红孩子t
3+4重构：t、s、p重命名为a、b、c
r保持黑；a和c染黑；b继承p的原色
如此，红黑树性质在全局得以恢复——删除完成 //zig-zag等类似
BB-2R：s为黑，且两个孩子均为黑；p为红
r保持黑；s转红；p转黑
在对应的B-树中，等效于下溢节点与兄弟合并
红黑树性质在全局得以恢复
失去关键码p之前，上层节点不会继续下溢，合并之前，在p之左或右侧还必有（问号）关键码。必为黑色，有且仅有一个
BB-2B：s为黑，且两个孩子均为黑；p为黑
s转红；r与p保持黑
BB-3：s为红（其孩子均为黑）
zag(p)或zig(p)；红s转黑，黑p转红
既搏丛野然p已转红，接下来绝不会是情况BB-2B，而只能是BB-1或BB-2R
复杂度
红黑树的每一删除操作都可在O(logn)时间内完成
其中，至多做
1.O(logn)次重染色
2.一次“3+4”重构
3.一次单旋
4. 程序设计问题，查找算法性能研究，帮下忙谢啦
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
static const int ARRAY_MAX = 10000;
typedef int DataType;
class SequentialStorage
{
public:
DataType data[ARRAY_MAX];
int top;
SequentialStorage()
{
top = -1;
}
void insertData(DataType data)
{
if(top == ARRAY_MAX-1)
return;
this->data[++top] = data;
}
int find(DataType data)
{
for(int i = 0;i <= top;i++)
{
if(this->data[i] == data)
return i;
}
return -1;
}
};
class OrderlySequenceStorage
{
public:
DataType data[ARRAY_MAX];
int top;
OrderlySequenceStorage()
{
top = -1;
}
void insertData(DataType data)//插入排序
{
if(top == ARRAY_MAX-1)
return;
int i = top;
while(this->data[i] > data&&i != -1)
{
this->data[i+1] = this->data[i];
i--;
}
this->data[i+1] = data;
top++;
}
int find(DataType data)//普通查找
{
for(int i = 0;i <= top;i++)
{
if(this->data[i] == data)
return i;
}
return -1;
}
int find2(DataType data)//二分法
{
if(this->data[0] > data||this->data[top] < data)
return -1;
if(this->data[0] == data)
return 0;
if(this->data[top] == data)
return top;
int a = 0;
int b = top;
while(true)
{
if(a == b-1)
return -1;
if(this->data[(a+b)/2] == data)
return (a+b)/2;
else if(this->data[(a+b)/2] < data)
a = (a+b)/2;
else
b = (a+b)/2;
}
}
};
typedef struct node
{
DataType data;
struct node *pNext;
}LLSNode;
class LinkedListStorage
{
public:
LLSNode *pHead;
LinkedListStorage()
{
pHead = NULL;
}
void insertData(DataType data)
{
LLSNode *p = (LLSNode *)malloc(sizeof(LLSNode));
p->data = data;
p->pNext = pHead;
pHead = p;
}
LLSNode *find(DataType data)
{
LLSNode *p = pHead;
while(p)
{
if(p->data == data)
return p;
p = p->pNext;
}
return NULL;
}
};
typedef struct node2
{
DataType data;
struct node2 *lchild,*rchild;
}BSTNode;
class BinarySortTree
{
public:
BSTNode *pRoot;
BinarySortTree()
{
pRoot = NULL;
}
void insertData(DataType data)
{
BSTNode *f,*p = pRoot;
while(p)
{
f = p;
if(data < p->data)
p = p->lchild;
else
p = p->rchild;
}
p = (BSTNode *)malloc(sizeof(BSTNode));
p->data = data;
p->lchild = NULL;
p->rchild = NULL;
if(pRoot == NULL)
pRoot = p;
else
if(data < f->data)
f->lchild = p;
else
f->rchild = p;
}
BSTNode *find(DataType data)
{
if(pRoot == NULL)
return NULL;
else
return recursion(data,pRoot);
}
BSTNode *recursion(DataType data,BSTNode *p)
{
if(data == p->data||p == NULL)
return p;
else if(data < p->data)
return recursion(data,p->lchild);
else
return recursion(data,p->rchild);
}
void print()
{
if(pRoot != NULL)
printR(pRoot);
}
void printR(BSTNode *p)
{
if(p->lchild != NULL)
printR(p->lchild);
printf("%d\t",p->data);
if(p->rchild != NULL)
printR(p->rchild);
}
};
class CPUTime
{
public:
_int64 getCPUCycleCount(void)
{
_asm _emit 0x0F
_asm _emit 0x31
}
long long arr[1000];
int count;
long long lastCPUCycleCount;
int randCount;
CPUTime()
{
for(int i = 0;i < 1000;i++)
arr[i] = 0;
count = -1;
lastCPUCycleCount = getCPUCycleCount();
randCount = 0;
}
void setTimePoint()
{
arr[++count] = getCPUCycleCount()-lastCPUCycleCount;
lastCPUCycleCount = getCPUCycleCount();
}
int rand()
{
randCount++;
int temp = getCPUCycleCount()%20000;
return (temp*(randCount+temp))%10007;
}
};
int main()
{
SequentialStorage ss;
OrderlySequenceStorage oss;
LinkedListStorage lls;
BinarySortTree bst;
DataType temp1;
CPUTime cpuTime;
for(int i = 0;i < 2000;i++)
{
temp1 = cpuTime.rand();
ss.insertData(temp1);
oss.insertData(temp1);
lls.insertData(temp1);
bst.insertData(temp1);
}
DataType temp[7];
for(int i = 0;i < 7;i++)
temp[i] = ss.data[cpuTime.rand()%2000];
cpuTime.setTimePoint();
for(int i = 0;i < 7;i++)
{
ss.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
oss.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
oss.find2(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
lls.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
bst.find(temp[i]);
cpuTime.setTimePoint();
}
int count = 1;
printf("各项存储结构查找已存在数据的时间（cpu周期）：\n");
printf("储存方式\t\t数据1\t数据2\t数据3\t数据4\t数据5\t数据6\t平均\n");
int a[9];
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("顺序存储\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("有序顺序存储(普通)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("有序顺序存储(二分法)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("链表存储\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("二叉排序树存储\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
system("pause");
}
//我按照课题的要求写的c++具体实现的代码，楼主可以编译运行着试试，你可以参考一下
//我这搜索的是储存结构里已存在的数据，你也可以按题目的要求用随机生成的数据
//楼主留下qq吧，我等会把流程图发给你
//至于其他的，楼主还是自己试着写写看吧
5. 二叉排序树的应用
树的应用：二叉排序树
排序是一种十分重要的运算。所谓排序就是把一堆杂乱无章的元素按照某种次序排列起来，形成一个线性有序的序列。二叉排序树是利用二叉树的结构特点来实现对元素排序空绝的。
一、二叉排序树的定义
二叉排序树或者是空树，或者是具有如下性质的二叉树：
1、左子树上所有结点的数据值均小于根结点的数据值；
2、右子树上所有结点的数据值均大于或等于根结点的数据值；
3、左子树、右子树本身又各是一棵二叉排序树。
由此可见，二叉排序树是一种特殊结构的二叉树。（18（10（3，15（12，15）），21（20，21（，37））））就是一棵二叉排序树。
思考题1：试将上述括号表示法表示的二叉排序树用图形表示法表示出来。图
思考题2：试用中序遍历二叉树的方法写出遍历二叉排序树的结果，并思考二叉排序树究竟有什么作用？。
二、二叉排序树的构造
二叉排序树的构造过程实质上就是排序的过程，它是二叉排序树作媒介，将一个任意的数据序列变成一个有序序列。二叉排序树的构造一般是采用陆续插入结点的办法逐步构成的。具体构造的思路是：
1、以待排序的数据的第一个数据构成根结点；
2、对以后的各个数据，逐个插入结点，而且规定：在插入过程的仿亏缓每一步，原有树结点位置不再变动，只是将新数据的结点作为一个叶子结点插入到合适的位置，使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求。
思考题3：试根据上述构造二叉排序树的思路，画出待排序数据（50，54，71，23，48，55，79，32，21）的二叉排序树图。
总结：构造二叉排序树的算法思想如下：设A={a1,a2,...,an}为一组元素的集合，
1、令a1为二叉排序树的根；
2、在保持二叉排序树性质的前提下，依次把a2,a3,...,an插入到该树中。
二叉排序树的生成算法：
Procere createbst(Var t:pointer);
{构造一棵以t指向根结点的二叉排序树，插入数据以‘#’结束}
Begin
t:=nil; {初始化}
read(x); {输入元素值x}
while (x<>'#') do
begin
new(s);s^.Lc:=nil;s^.Rc:=nil;
s^.data:=x;
insertnode(s,t);
read(x)
end;
end.
其中，插入一个结点的算法insertnode(s，t)如下：
Procere insertnode(s:pointer;Var t:pointer);
{s指向待插入结点，t是bst的根}
Begin
if t=nil then t:=s
else if s^.data < t^.data then insertnode(s,t^.Lc)
else insertnode(s,t^.Rc)
end.
注备模意该算法为尾递归算法。不用栈即可转为非递归。
思考题4：试用Pascal语言编写一个程序，实现对未排序数据的输入、排序和输出排序结果。（要求应用二叉排序树）标准程序 参考程序（黄硕）
思考题5：假设已经生成了一棵二叉树，试按照二叉排序树的思想设计一个算法，判断这棵二叉树是否为二叉排序树。
6. 设计算法，查找二叉树中数据元素x，Search（bt，x）在bt为二叉树的根结点指针的二叉树中查找
#include <stdio.h>
#include <stdlib.h>
#define STACK_MAX_SIZE 30
#define QUEUE_MAX_SIZE 30
#ifndef elemType
typedef int elemType;
#endif struct BTreeNode{
elemType data;
struct BTreeNode *left;
struct BTreeNode *right;
}; /*1.查找*/
/*递归算法*/
elemType* findBSTree1(struct BTreeNode* bst,elemType x)
{
/绝誉*树为空告凯则返回NULL*/
if(bst==NULL){
return NULL;
}else{
if(x==bst->data){
return &(bst->data);
}else{
if(x<bst->data){/*向左子树查找并直接返回*/
return findBSTree1(bst->left,x);
}else{/*向右子树查找并直接返回*/
return findBSTree1(bst->right,x);
}
}
}
}
/*非递归算法*/
elemType* findBSTree2(struct BTreeNode*bst,elemType x)
{
while(bst!=NULL){
if(x==bst->data){
return&(bst->data);
}else if(x<bst->data){
bst=bst->left;
}else{
bst=bst->right;
}
}
return NULL;
}
/*2.插入*/
/*递归算法*/
void insertBSTree1(struct BTreeNode**bst,elemType x)
{
/*新建一个根结点*/
if(*bst==NULL){
struct BTreeNode*p=(struct BTreeNode*)malloc(sizeof(struct BTreeNode));
p->data=x;
p->left=p->right=NULL;
*bst=p;
return;
}else if(x<(*bst)->data){/*向左子树完成插入运算*/
insertBSTree1(&((*bst)->left),x);
}else{/*向右子树完成插入运算*/
insertBSTree1(&((*bst)->right),x);
}
}
/*非递归算法*/
void insertBSTree2(struct BTreeNode**bst,elemType x)
{
struct BTreeNode*p;
struct BTreeNode*t=*bst,*parent=NULL;
/*为待插入的元素查找插入位袜宏唤置*/
while(t!=NULL){
parent=t;
if(x<t->data){
t=t->left;
}else{
t=t->right;
}
}
/*建立值为x，左右指针域为空的新结点*/
p=(struct BTreeNode*)malloc(sizeof(struct BTreeNode));
p->data=x;
p->left=p->right=NULL;
/*将新结点链接到指针为空的位置*/
if(parent==NULL){
*bst=p;/*作为根结点插入*/
}else if(x<parent->data){/*链接到左指针域*/
parent->left=p;
}else{
parent->right=p;
}
return;
}
/*3.建立*/
void createBSTree(struct BTreeNode**bst,elemType a[],int n)
{
int i;
*bst=NULL;
for(i=0;i<n;i++){
insertBSTree1(bst,a[i]);
}
return;
}
/*******************************/
/* 6.输出二叉树(前序遍历) */
void printBTree(struct BTreeNode *bt)
{
/* 树为空时结束递归，否则执行如下操作 */
if(bt != NULL){
printf("%d", bt->data);/* 输出根结点的值 */
if(bt->left != NULL || bt->right != NULL){
printf("(");
printBTree(bt->left);
if(bt->right != NULL){
printf(",");
}
printBTree(bt->right);
printf(")");
}
}
return;
}
/* 7.清除二叉树，使之变为一棵空树 */
void clearBTree(struct BTreeNode* *bt)
{
if(*bt != NULL){
clearBTree(&((*bt)->left));
clearBTree(&((*bt)->right));
free(*bt);
*bt = NULL;
}
return;
}
/* 8.前序遍历 */
void preOrder(struct BTreeNode *bt)
{
if(bt != NULL){
printf("%d ", bt->data);/* 访问根结点 */
preOrder(bt->left);/* 前序遍历左子树 */
preOrder(bt->right);/* 前序遍历右子树 */
}
return;
}
/* 9.前序遍历 */
void inOrder(struct BTreeNode *bt)
{
if(bt != NULL){
inOrder(bt->left);/* 中序遍历左子树 */
printf("%d ", bt->data);/* 访问根结点 */
inOrder(bt->right);/* 中序遍历右子树 */
}
return;
}
/* 10.后序遍历 */
void postOrder(struct BTreeNode *bt)
{
if(bt != NULL){
postOrder(bt->left);/* 后序遍历左子树 */
postOrder(bt->right);/* 后序遍历右子树 */
printf("%d ", bt->data);/* 访问根结点 */
}
return;
}
int main(int argc,char*argv[])
{
int x,*px,i=0;
elemType a[10];//={30,50,20,40,25,70,54,23,80,92};
printf("请输入一组整数（空格隔开,-1结束）：");
scanf("%d",&x);
while(x!=-1){
a[i++]=x;
scanf("%d",&x);
}
struct BTreeNode* bst=NULL;
createBSTree(&bst,a,i);
printf("建立的二叉搜索树的广义表形式为： ");
printBTree(bst);
printf(" ");
printf("\n前序遍历： ");
preOrder(bst);
printf(" ");
printf("\n中序遍历： ");
inOrder(bst);
printf(" ");
printf("\n后序遍历： ");
postOrder(bst);
printf(" ");
printf("\n输入待查找元素的值：");
scanf("%d",&x);
if(px=findBSTree1(bst,x)){
printf("\n查找成功！得到的x为：%d ",*px);
}else{
printf("\n查找失败！ ");
}
clearBTree(&bst);
system("pause");
return 0;
}
7. 数据结构与算法 - 树,BST 树
树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（核宏棚Root）的结点；（2）当n>1时，其余结点可以分为互不相交的有限集T1、T2、……Tm，其中每一绝饥个集合本身又是一棵树，并且称为根的子树（SubTree）
基本术语
树中的每一个节点最多有两个子节点的树，或者说是树中的每一个节点的度最大为2 。 二叉树的子节点分别称为左节点和右改则节点
二叉树具有以下几个性质：
所有的非叶子节点都存在左右子节点， 并且所有的叶子节点都在最后一层
满二叉树除了满足普通二叉树的性质，还具有以下性质：
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。 满二叉树一定是完全二叉树
完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊log2 n⌋+1。
对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：
也叫二叉排序树，指除了叶子节点外，左子节点的值要小于当前节点，右子节点的值要大于当前节点
8. 数据结构与算法试题，高分，求答案啊
给你第一题解法吧：后面的实在是不想做。
先根：ABCDEFGHI
中根：CBEDAGFHI
遍历的基本方法：先左子树后右子树。
1,先根遍历可以确定根节点为A,
2,依据1步，可以在中根遍历中确定左子树为：CBED,右为：GFHI
3,在可以重复1,2步。就可以得到结果。
A
BF
CDGH
I
4,O(n^3)+O(1)
9. 下面是向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。请将缺失语句填上
1.
p->lchild竖仿衫=NULL;
p->rchild=NULL;
//这里应该给出BTreeNode的数据大闭结构。是不是有data,lchild,rchild?
2.
Insert(BST->lchild,item);
//item值比该节点值小，应该余腔递归该节点的左子树
3.
Insert(BST->rchild,item);
大概应该是这样，不知道对不对，但是递归的原理应该是没错
10. 编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找成功能则由item带回整个
typedef int ElemType;
typedef struct bn{
ElemType item;
struct bn *left,*right;
} BTreeNode;
bool Find(BTreeNode *BST,ElemType &item)
{
BTreeNode *now=BST;
while (now)
{
if (item>now->item) now=now->right;
else if (item<now->item) now=now->left;
else return true;
}
return false;
}