第7章 第1节 树

推荐给朋友

● 二叉树层序遍历

参考回答:

思路:先建立一棵二叉树。再进行队列遍历
function tree(obj) {
var obj = obj.split(')');
obj.pop();
var newobj = [];
for (var i = 0; i < obj.length; i++) {
newobj.push(obj[i].replace('(',''));
}
var root = {
value: null, left: null, right: null,have:0
}
var u;
for(var i = 0; i < newobj.length; i++) {
var a1 = newobj[i].split(',')[0];
var a2 = newobj[i].split(',')[1];
u = root;
if(a2!==''){
for (var j = 0;j<a2.length;j++) {
if(a2[j]==='L'){
if(u.left === null){
u.left = newnode();
u = u.left;
}else {
u = u.left;
}
} else if(a2[j]==='R') {
if(u.right === null){
u.right = newnode();
u = u.right;
}else{
u = u.right;
}
}
}
if(u.have === 1)  {
} else{
u.value = a1;
u.have = 1;
}
}else {
root.value = a1;
u.have = 1;
}
}
return root;
}

//建立新结点

function newnode() {
return {value: null, left: null, right: null,have:0};
}

//队列遍历

function bfs() {
var root = tree('(11,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)');
var front = 0,rear = 1,n=0;
var q = [],ans=[];
q[0] = root;
while(front < rear) {
var u = q[front++];
if(u.have!==1) {
return;
}
ans[n++] = u.value;
if(u.left!==null) {
q[rear++] = u.left;
}
if(u.right!==null) {
q[rear++] = u.right;
}
}
console.log(ans.join(' '));
}
bfs();

● B树的特性,B树和B+树的区别

参考回答:

一个m 阶的B树满足以下条件:

每个结点至多拥有m棵子树;

根结点至少拥有两颗子树(存在子树的情况下);

除了根结点以外,其余每个分支结点至少拥有m/2 棵子树;

所有的叶结点都在同一层上;

有k 棵子树的分支结点则存在 k-1 个关键码,关键码按照递增次序进行排列;

关键字数量需要满足ceil(m/2)-1 <= n <= m-1;

B树和B+树的区别:

以一个m阶树为例。

关键字的数量不同;B+树中分支结点有m个关键字,其叶子结点也有m个,其关键字只是起到了一个索引的作用,但是B树虽然也有m个子结点,但是其只拥有m-1个关键字。

存储的位置不同;B+树中的数据都存储在叶子结点上,也就是其所有叶子结点的数据组合起来就是完整的数据,但是B树的数据存储在每一个结点中,并不仅仅存储在叶子结点上。

分支结点的构造不同;B+树的分支结点仅仅存储着关键字信息和儿子的指针(这里的指针指的是磁盘块的偏移量),也就是说内部结点仅仅包含着索引信息。

查询不同;B树在找到具体的数值以后,则结束,而B+树则需要通过索引找到叶子结点中的数据才结束,也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。