① 求《數據結構》（c語言，第二版） 嚴蔚敏、吳偉民主編，清華大學出版社 課後習題答案
http://wenku..com/link?url=-wmTox3c-s9Pk6r0MyGk1N6YqJu-Fya9-LrzhksZfVTfM0R09K9kzLVq9d4_AtX-ZXlPWuZC
② 數據結構B樹或者B+樹怎麼構造 求告知
一、B樹的起源
B樹，最早是由德國計算機科學家Rudolf Bayer等人於1972年在論文 《Organization and Maintenance of Large Ordered Indexes》提出的，不過我去看了看原文，發現作者也沒有解釋為什麼就叫B-trees了，所以把B樹的B，簡單地解釋為Balanced或者Binary都不是特別嚴謹，也許作者就是取其名字Bayer的首字母命名的也說不定啊……
二、B樹長啥樣
還是直接看圖比較清楚，圖中所示，B樹事實上是一種平衡的多叉查找樹，也就是說最多可以開m個叉（m>=2），我們稱之為m階b樹，為了體現本博客的良心之處，不同於其他地方都能看到2階B樹，這里特意畫了一棵5階B樹 。
B+樹的查找過程，與B樹類似，只不過查找時，如果在非葉子節點上的關鍵字等於給定值，並不終止，而是繼續沿著指針直到葉子節點位置。因此在B+樹，不管查找成功與否，每次查找都是走了一條從根到葉子節點的路徑
③ 求數據結構 B-樹與B+樹及其操作的代碼（C語言版）
那個叫二叉樹啊
樹是一種重要的非線性數據結構，直觀地看，它是數據元素（在樹中稱為結點）按分支關系組織起來的結構，很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用，如在編譯源程序如下時，可用樹表示源源程序如下的語法結構。又如在資料庫系統中，樹型結構也是信息的重要組織形式之一。一切具有層次關系的問題都可用樹來描述。
一、樹的概述
樹結構的特點是：它的每一個結點都可以有不止一個直接後繼，除根結點外的所有結點都有且只有一個直接前趨。以下具體地給出樹的定義及樹的數據結構表示。
（一）樹的定義
樹是由一個或多個結點組成的有限集合，其中：
⒈必有一個特定的稱為根(ROOT)的結點；
⒉剩下的結點被分成n>=0個互不相交的集合T1、T2、......Tn，而且，
這些集合的每一個又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。
樹的遞歸定義如下：（1）至少有一個結點（稱為根）（2）其它是互不相交的子樹
1.樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如上圖的樹，其度為3;樹中度為零的結點稱為葉結點或終端結點。樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。
2.樹的深度——組成該樹各結點的最大層次，如上圖，其深度為4；
3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結點A，其原來的二棵子樹T1、T2、T3的集合就為森林；
4.有序樹——指樹中同層結點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。
5.樹的表示
樹的表示方法有許多，常用的方法是用括弧：先將根結點放入一對圓括弧中，然後把它的子樹由左至右的順序放入括弧中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括弧括起來，同層子樹之間用逗號隔開，最後用閉括弧括起來。如上圖可寫成如下形式：
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
5.
2
二叉樹
1.二叉樹的基本形態：
二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：
(1)空二叉樹——(a)；
(2)只有一個根結點的二叉樹——(b)；
(3)右子樹為空的二叉樹——(c)；
(4)左子樹為空的二叉樹——(d)；
(5)完全二叉樹——(e)
注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。
④ 數據結構（C語言版） 建立二叉樹數據怎麼輸入
typedef struct BiTNode{ ............} BiTNode,*BiTree;BiTree CreateBiTree(){ BiTree T;char ch;scanf("%c",&ch);if(ch==' ')return (NULL); else{ if(!(T=( BiTNode*)malloc(sizeof(BiTNode))))return 0; T->data=ch; //生成根結點 T->lchild= CreateBiTree(); //構造左子樹 T->rchild=CreateBiTree(); //構造右子樹。因為前面定義具有BiTNode相同類型的二叉樹，所以把遞歸的值付給右孩子 return (T); }}
⑤ 數據結構B樹
比如說一顆 B 樹的階為 1001（即 1 個節點包含 1000 個關鍵字），高度為 2，它可以儲存超過 10 億個關鍵字，我們只要讓根節點持久地保留在內存中，那麼在這棵樹上，尋找某一個關鍵字至多需要兩次硬碟的讀取即可。
⑥ c語言數據結構 什麼叫 最下層的非葉結點 b樹里的
在b樹種，當在葉子結點處於第L+1層的B樹中插入關鍵字時，被插入的關鍵字總是進入第L層的結點。
b樹中所有葉子結點都在同一層,並且不帶任何信息。
所以你所說的最下層的非葉子節點是不是代表倒數第二層的能插入關鍵字的那一層，你是想要進行刪除操作嗎？
⑦ 數據結構B樹的設計與實現
B樹的插入演算法在編寫過程中還是覺得比較難寫的，主要的問題是，結點的分裂，
對葉子結點的分裂和對非葉節點的分裂不一樣，還有就是當ptr->parent==NULL,
需要新建父結點，而新建的結點始終是樹的根結點，還有結點分裂過程中子樹指
針的變化還是很復雜的，不過終於實現了，分享一下我的代碼，可以直接運行，
本程序沒有包含我編寫的其他頭文件，代碼如下，大家多多討論：
另外，由於B樹不同於其他的樹，所有我考慮了一下，還是採用縮進格式來顯示
B樹了，因為每個結點有多個關鍵碼，所以用廣義表形式不顯示不好。
#ifndef BTREE_H
#define BTREE_H
#include<iostream.h>
#include<stdlib.h>
const int maxValue=10000;
/////////////////////////////////////////////////
//BTreeNode<T>B樹的結點的定義
/////////////////////////////////////////////////
template<class T>
struct BTreeNode
{
int n; //結點中關鍵碼的個數
BTreeNode<T>* parent; //當前結點的父結點的指針
T* key; //m+1個元素存放關鍵碼,其中key[0]和key[m]沒有用
BTreeNode<T>** //子樹指針的結點數組(一共有m棵子樹),m+1個元素
subTree; //最後一個元素subTree[m]在插入溢出的時候使用
int** recptr; //每個索引項中指向數據區相應記錄起始地址的指針數組
BTreeNode(int m) //構造函數
{
n=0; //關鍵碼個數初始化為0
parent=NULL; //父結點指針初始化為空
key=new T[m+1]; //開辟關鍵碼數組的空間
subTree=new //開辟子樹的指針數組的內存空間
BTreeNode<T>*[m+1]; //從p0,p1,p2,...p(m-1)共m棵子樹
for(int i=0;i<=m;i++)
subTree[i]=NULL; //子樹數組先全部初始化為空
};
bool Insert(const T& x //把一個關鍵碼插入到當前的B樹結點中
,BTreeNode<T>* p) //也把附帶的新建的右子樹的指針插入subTree[]中
{
for(int i=1;i<=n;i++) //尋找插入關鍵碼的位置
{
if(x<key[i])
break;
};
for(int j=n;j>=i;j--) //挪處新的插入位置來
key[j+1]=key[j];
key[i]=x; //插入結點
n++;
for(j=n;j>=i;j--) //把新分裂開來的右子樹結點插入subTree[]中
subTree[j+1]=subTree[j];
subTree[i]=p;
return true;
};
void Display() //顯示當前結點所有關鍵碼
{
for(int i=1;i<=n;i++)
cout<<key[i]<<" ";
};
};
/////////////////////////////////BTree<T>定義結束
/////////////////////////////////////////////////
//Triple<T>結構 返回搜索結果用的三元組
/////////////////////////////////////////////////
template<class T>
struct Triple
{
BTreeNode<T>* r; //結點指針
int i; //關鍵碼在當前結點中的序號
int tag; //tag=0:搜索成功,tag=1:搜索失敗
};
////////////////////////////////Triple<T>結構結束
/////////////////////////////////////////////////
//BTree<T> B樹的定義;
//m階B樹的根至少有兩個子樹，
//其他的結點至少應該有int(m/2)+1個子樹
//所有的失敗結點都在一個層次上
/////////////////////////////////////////////////
template<class T>
class BTree
{
private:
BTreeNode<T>* root; //樹根結點指針
int m; //即B樹的階數
public:
BTree(int x) //空構造函數,構造一棵空x路的搜索樹
{root=NULL;m=x;};
BTree(int x,BTreeNode<T>* r)
{root=r;m=x;}; //用指定的樹根來初始化當前的m路搜索樹
void Insert( //在樹指定父結點的情況下插入一個結點
BTreeNode<T>* pa, //指定要出入的位置的父結點
BTreeNode<T>* subTree, //要插入的結點的指針
int i); //表示插入到pa的第i個子樹的位置
Triple<T> //搜索指定關鍵碼x對應的結點
Search(const T& x);
void RootFirst( //遞歸:以先根的方式遍歷當前的搜索樹
BTreeNode<T>* subTree);
void RootFirst() //調用上面的遞歸函數
{RootFirst(root);};
bool Insert(const T& x); //B樹的插入操作
void Display(
BTreeNode<T>* p,int i); //遞歸:以縮進的格式顯示當前的B樹
void Display() //調用上面的遞歸函數
{cout<<"*****當前B樹的縮進結構顯示*****:"<<endl;
Display(root,1);};
};
//////////////////////////////////////B樹聲明結束
/////////////////////////////////////////////////
//RootFirst()公有成員函數
//以先根的方式遞歸遍歷當前B樹
/////////////////////////////////////////////////
template<class T>
void BTree<T>::RootFirst(BTreeNode<T>* st)
{
if(st!=NULL)
{
int n=st->n;
cout<<"當前結點有"<<n
<<"個關鍵碼:"<<endl;
for(int k=1;k<=n;k++) //輸出當前結點的所有的關鍵碼
cout<<st->key[k]<<" ";
cout<<endl<<endl;
for(int i=0;i<=n;i++) //遞歸輸出所有的子樹
RootFirst(st->subTree[i]);
};
};
//////////////////////////////RootFirst()函數結束
/////////////////////////////////////////////////
//Search()公有成員函數 搜索具有指定關鍵碼的
//的結點並且以三元組的形式進行返回,如果沒有搜索
//成功就把該關鍵碼插入到當前駐留的結點中去
/////////////////////////////////////////////////
template<class T>
Triple<T> BTree<T>::Search(const T& x)
{
Triple<T> result; //結果三元組
BTreeNode<T>* ptr=root; //從根結點開始搜索
BTreeNode<T>* pre;
/*從根結點開始往下查找*/
int i;
while(ptr!=NULL)
{
for(i=1;i<=ptr->n;i++) //在結點內部進行順序搜索
{
if(ptr->key[i]==x) //如果找到
{
result.r=ptr; //當前查找駐留的結點指針
result.i=i; //查找成功的關鍵碼
result.tag=1; //是否查找成功
return result;
};
if(ptr->key[i]>x) //查找失敗
break;
};
pre=ptr;
ptr=ptr->subTree[i-1]; //從失配的關鍵碼左邊的子樹繼續查找
};
/*如果查找失敗*/
result.r=pre;
result.i=i; //可以在i-1和i之間進行插入
result.tag=0; //查找失敗
return result;
};
/////////////////////////////////Search()函數結束
/////////////////////////////////////////////////
//Insert()公有成員函數 B樹的插入操作
//把指定的關鍵碼插入到B樹中,使得仍然滿足B樹的要求
//首先對B樹進行搜索,如果關鍵碼已經存在則插入失敗,
//否則執行插入，並按B樹要求進行調整
//一般來說,執行插入的肯定是在葉子結點上進行
//但是如果查找成功的話,可能在非葉子結點上就結束了
/////////////////////////////////////////////////
template<class T>
bool BTree<T>::Insert(const T& x)
{
/*如果當前的B樹是空的,就新建之*/
if(root==NULL) //如果當前的B樹是空的
{
root=new BTreeNode<T>(m); //新建一個結點
root->Insert(x,NULL); //把關鍵碼插入到key[]數組第一個位置
return true;
};
/*如果當前的B樹不空,就搜索該樹*/
Triple<T> Tp; //查找結果三元組
Tp=Search(x);
int IsIn=Tp.tag;
if(IsIn==1) //關鍵碼已經存在
{
cout<<"關鍵碼已存在!"<<endl;
return false; //插入失敗
};
/*插入關鍵碼直到結點關鍵碼不溢出為止*/
BTreeNode<T>* ptr=Tp.r; //查找失敗而駐留的結點
int loc=Tp.i-1; //在k[loc]後進行插入
int pkey=x;
BTreeNode<T>* p=NULL; //隨關鍵一起要插入的右子樹的根結點
do
{
ptr->Insert(pkey,p); //把關鍵碼和相關的新分裂的右結點插入當前結點
if(ptr->n>m-1) //如果關鍵碼溢出,則需要進行調整
{
/*以下處理結點的分裂*/
int k=ptr->key[m/2+1]; //提取出要上提的關鍵碼
BTreeNode<T>* right //建立分裂後右邊的結點
=new BTreeNode<T>(m);
right->n=ptr->n-m/2-1; //右結點的關鍵碼個數
for(int i=m/2+2;i<=ptr->n;i++)
right->key[i-m/2-1] //把右半邊的關鍵碼復制進入右結點
=ptr->key[i];
for(i=m/2+1;i<=ptr->n;i++)
{
right->subTree[i-m/2-1]
=ptr->subTree[i]; //把相應的分裂後的右結點子樹指針復制入新結點
}
ptr->n=m/2; //修改原結點使之成為左結點
right->parent
=ptr->parent; //新分裂的結點
p=right; //p是隨k一起上提的新建分裂右結點指針
pkey=k;
/*如果當前的結點沒有父結點*/
if(ptr->parent==NULL) //如果當前結點沒有父結點,就新建父結點
{
BTreeNode<T>* newp //新建一個父結點
=new BTreeNode<T>(m);
newp->key[1]=k; //插入新關鍵碼
newp->subTree[0] //新關鍵碼左邊的子樹
=ptr;
newp->subTree[1] //新關鍵碼右邊的子樹
=right;
newp->n=1; //新關鍵碼個數為1
ptr->parent=newp; //設置父結點指針
right->parent=newp;
root=newp;
return true; //插入成功並結束
}
else //如果有父結點存在
ptr=ptr->parent; //把上提的關鍵碼繼續插入父結點
}
else //不溢出則插入成功
return true;
}while(ptr!=NULL);
return true;
};
/////////////////////////Insert()公有成員函數結束
/////////////////////////////////////////////////
//Display()公有成員函數
//遞歸:顯示當前B樹的縮進格式
/////////////////////////////////////////////////
template<class T>
void BTree<T>::Display(BTreeNode<T>* p,int i)
{
if(p!=NULL)
{
for(int j=0;j<i;j++)
cout<<" "; //控制縮進的格數
cout<<"當前結點是:關鍵碼個數"<<p->n<<" "
<<"關鍵碼的內容是";
for(int k=1;k<=p->n;k++)//顯示當前結點所有關鍵碼
cout<<p->key[k]<<" ";
cout<<endl;
for(k=0;k<=p->n;k++) //遞歸顯示子樹,遞歸向後縮進
Display(p->subTree[k],i+5);
};
};
////////////////////////////////Display()函數結束
#endif
#include"BTree.h"
/////////////////////////////////////////////////
//main()函數 測試B樹的程序
/////////////////////////////////////////////////
int main()
{
BTree<int> BT(3);
BT.Insert(53); //依此在B樹中插入關鍵碼
BT.Insert(75);
BT.Insert(139);
BT.Insert(49);
BT.Insert(145);
BT.Insert(36);
BT.Insert(101);
BT.Insert(150);
BT.Insert(170);
BT.Insert(25);
BT.Insert(13);
BT.Display(); //顯示當前B樹的內容
return 0;
};
///////////////////////////////////main()函數結束
⑧ 求數據結構（C語言版）建立二叉樹的代碼~~急~~謝謝了
BT.H文件
#include
<stdio.h>
#include
<malloc.h>
#include
<conio.h>
#define
TRUE
1
#define
FALSE
0
#define
ERROR
0
#define
OK
1
#define
Stack_Size
50
#define
NUM
50
#define
MAXSIZE
50
//隊列的最大長度
//定義二叉樹
typedef
char
DataType;
typedef
struct
Node
{
DataType
data;
struct
Node
*LChild;
struct
Node
*RChild;
}BiTNode,
*BiTree;
//定義stack
typedef
BiTree
StackElementType;
typedef
struct
{
StackElementType
elem[Stack_Size];
int
top;
}SeqStack;
//定義隊列
typedef
BiTree
QueueElementType;
typedef
struct
{
QueueElementType
element[MAXSIZE];
int
front;
int
rear;
}SeqQueue;
//隊列的抽象
void
InitQueue(SeqQueue
*Q)
{
Q->front=Q->rear=0;
}
int
EnterQueue(SeqQueue
*Q,
QueueElementType
x)
{
if((Q->rear+1)%MAXSIZE==Q->front)
return(FALSE);
Q->element[Q->rear]=x;
Q->rear=(Q->rear+1)%MAXSIZE;
return(TRUE);
}
⑨ 數據結構中什麼是B樹
B 樹是為了磁碟或其它存儲設備而設計的一種多叉（下面你會看到，相對於二叉，B樹每個內結點有多個分支，即多叉）平衡查找樹。
B 樹又叫平衡多路查找樹。一棵m階的B 樹 (m叉樹)的特性如下：樹中每個結點最多含有m個孩子（m>=2）；除根結點和葉子結點外，其它每個結點至少有[ceil(m / 2)]個孩子（其中ceil(x)是一個取上限的函數）；若根結點不是葉子結點，則至少有2個孩子（特殊情況：沒有孩子的根結點，即根結點為葉子結點，整棵樹只有一個根節點）；所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字信息(可以看做是外部接點或查詢失敗的接點，實際上這些結點不存在，指向這些結點的指針都為null)；每個非終端結點中包含有n個關鍵字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
a) Ki (i=1...n)為關鍵字，且關鍵字按順序升序排序K(i-1)< Ki。
b) Pi為指向子樹根的接點，且指針P(i-1)指向子樹種所有結點的關鍵字均小於Ki，但都大於K(i-1)。
c) 關鍵字的個數n必須滿足： [ceil(m / 2)-1]<= n <= m-1。
⑩ 數據結構(C語言版）中2叉樹的問題
#include <stdio.h> #include <malloc.h> #define MaxSize 100 #define MaxWidth 40 typedef char ElemType; typedef struct tnode { ElemType data; struct tnode *lchild,*rchild; } BTNode; void CreateBTree(BTNode * &bt,char *str) /*由str創建二叉鏈bt*/ {BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch;bt=NULL; ch=str[j]; bt=NULL; ch=str[j]; while(ch!='\0') { switch(ch) { case'(':top++;St[top]=p;k=1;break; case')':top--;break; case',':k=2;break; default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(bt==NULL) bt=p; else { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; }/*請在此處填寫代碼*/ } int BTHeight(BTNode *bt) /*求二叉樹高度*/ {int lchilddep,rchilddep; if(bt==NULL) return(0); else {lchilddep=BTHeight(bt->lchild); rchilddep=BTHeight(bt->rchild); return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1); }/*請在此處填寫代碼*/ } int NodeCount(BTNode *bt) /*求二叉樹bt的結點個數*/ {int num1,num2; if(bt==NULL) return 0; else { num1=NodeCount(bt->lchild); num2=NodeCount(bt->rchild); return (num1+num2+1); }/*請在此處填寫代碼*/ } int LeafCount(BTNode *bt) /*求二叉樹bt的葉子結點個數*/ {int num1,num2; if(bt==NULL) return 0; else if(bt->lchild==NULL&&bt->rchild==NULL) return 1; else {num1=LeafCount(bt->lchild); num2=LeafCount(bt->rchild); return(num1+num2); }/*請在此處填寫代碼*/ } void DispBTree(BTNode *bt) /*以括弧表示法輸出二叉樹*/ {if (bt!=NULL) {printf("&c",bt->data); if(bt->lchild!=NULL||bt->rchild!=NULL) {printf("("); DispBTree(bt->lchild); if(bt->rchild!=NULL) printf(","); DispBTree(bt->rchild); printf(")"); } }/*請在此處填寫代碼*/ } void main() { BTNode *bt; CreateBTree(bt,"A(B(C,D(E(G),F)))"); printf("二叉樹bt:");DispBTree(bt);printf("\n"); printf("bt的高度:%d\n",BTHeight(bt)); printf("bt的結點數:%d\n",NodeCount(bt)); printf("bt的葉子結點數:%d\n",LeafCount(bt)); }
滿意請採納