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;
}