构造算法

㈠ 数据结构C语言版 二叉树构造算法实验 在键盘上怎么输入

同学你好：我帮你看了你的程序：这是修改了的程序：希望你能采纳：

这是实验结果：是正确的

#include"stdio.h"

#include"stdlib.h"

#defineOK1

#defineERROR0

typedefcharTElemType;

typedefintStatus;

typedefstructBiTNode{//结点结构

TElemType data;

structBiTNode *lchild,*rchild;

//左右孩子指针

//以下是建立二叉树存储结构

StatusCreateBiTree(BiTree&T){

//请将该算法补充完整，参见第6章课件算法或课本

charch;

scanf("%c",&ch);

if(ch=='#')T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);

T->data=ch;

CreateBiTree(T->lchild);

CreateBiTree(T->rchild);

}

}//CreateBiTree

voidPreorder(BiTreeT)

{

if(NULL==T)

{

return;

}

else

{

printf("%c",T->data);

Preorder(T->lchild);

Preorder(T->rchild);

}

voidInorder(BiTreeT)

{//中序遍历二叉树

//请将该算法补充完整，参见第6章课件算法

if(T)

{

Inorder(T->lchild);

printf("%c",T->data);

Inorder(T->rchild);

}

}

voidPostorder(BiTreeT)

{//后序遍历二叉树

//请将该算法补充完整，参见第6章课件算法

if(T)

{

Postorder(T->lchild);

Postorder(T->rchild);

printf("%c",T->data);

}

//以下是求叶子结点数

voidCountLeaf(BiTreeT,int&count){

//请将该算法补充完整，参见第6章课件算法

if(T){

if((!T->lchild)&&(!T->rchild))

count++;

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);

}

//以下是求二叉树的深度

intDepth(BiTreeT){

//请将该算法补充完整，参见第6章课件算法

intdepthval,depthLeft,depthRight;

if(!T) depthval=0;

else{

depthLeft=Depth(T->lchild);

depthRight=Depth(T->rchild);

if(depthLeft>depthRight)depthval=1+depthLeft;

elsedepthval=1+depthRight;

}

returndepthval;

voidmain(){

BiTreeT;

ints=0,d;

printf(" creatofthebitree: ");

CreateBiTree(T);

printf(" outputresultofPreorder: ");

Preorder(T);

printf(" outputresultofInorder: ");

Inorder(T);

printf(" outputresultofPostorder: ");

Postorder(T);

CountLeaf(T,s);

d=Depth(T);

printf(" leaves=%d ",s);

printf(" depth=%d ",d);

}

㈡ 哈夫曼树构造算法中j<n+i是什么意思

先看一下哈夫曼树的构造规则是：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

用数据表示哈夫曼树的话，首先有n个权值点，其初始化就是从 0 到 n -1，先从这里面查找两个权值最小的结点，就是遍历一遍，把最小的值取出来。X1 和X2 要记录着两个权值在哪个位置。
然后把这两个权值加起来的和放回到数组n的位置，然后继续遍历这个数据，现在是从0 到n了，当然原来X1 和X2位置的两个点不用管，已经有父节点了。继续上述过程直到只有一个节点位置。

如 1 2 3 4 5 6构造哈夫曼树，先初始化parent 为 -1
1 2 3 4 5 6
parent -1 -1 -1 -1 -1 -1
先从上述中选取两个权值最小的节点 1 和 2，构造树变为3，放到数组6的位置，原权值序列变为：
1 2 3 4 5 6 3
parent 6 6 -1 -1 -1 -1 -1
继续选取 两个最小权值且parent为-1的点。找到3 和 3，放到数组7的位置，权值序列变为：
1 2 3 4 5 6 3 6
parent 6 6 7 -1 -1 -1 7 -1
继续选取 两个最小权值且parent为-1的点。找到4 和5，到数组8的位置，权值序列变为：
1 2 3 4 5 6 3 6 9
parent 6 6 7 8 8 -1 7 -1 -1
继续选取 两个最小权值且parent为-1的点。找到6 和6，到数组9的位置，权值序列变为：
1 2 3 4 5 6 3 6 9 12
parent 6 6 7 8 8 9 7 9 -1 -1
继续选取 两个最小权值且parent为-1的点。找到9 和12，到数组10的位置，权值序列变为：
1 2 3 4 5 6 3 6 9 12 21
parent 6 6 7 8 8 9 7 9 10 10 -1
结束
所以你说的j < n + i，由于每次选取两个权值的点权值和做为新的节点放在数组后面，当然下一次循环的时候要多一次循环。
X1 和X2要记录下选择两个权值，将其父节点的位置设置为新的权值点位置。

㈢ 什么是算法构造算法的基本思想是什么

1顺序结构
按从上到下的顺序进行
2选择结构
根据条件作判断,再决定执行哪一种操作的算法结构
必须包含判断框
3循环结构

㈣ FP-tree的FP-tree构造算法

输入：事务数据库D和最小支持度阈值minσ。
输出：D所对应的FP-tree。
方法：FP-tree是按以下步骤构造的：
(1)扫描事务库D，获得D中所包含的全部频繁项集1F，及它们各自的支持度。对1F中的频繁项按其支持度降序排序得到L。
(2)创建FP-tree的根结点T，以“null”标记。再次扫描事务库。对于D中每个事务，将其中的频繁项选出并按L中的次序排序。设排序后的频繁项表为[p|P]，其中p是第一个频繁项，而P是剩余的频繁项。调用insert_tree([p|P],T)。insert_tree([p|P],T)过程执行情况如下：如果T有子女N使N .item_name=p.item_name，则N的计数增加1；否则创建一个新结点N，将其计数设置为1，链接到它的父结点T，并且通过node_link将其链接到具有相同item_name的结点。如果P非空，递归地调用insert_tree(P，N)。FP-tree是一个高度压缩的结构，它存储了用于挖掘频繁项集的全部信息。FP-tree所占用的内存空间与树的深度和宽度成比例，树的深度一般是单个事务中所含项目数量的最大值；树的宽度是平均每层所含项目的数量。由于在事务处理中通常会存在着大量的共享频繁项，所以树的大小通常比原数据库小很多。频繁项集中的项以支持度降序排列，支持度越高的项与FP-tree的根距离越近，因此有更多的机会共享结点，这进一步保证了FP-tree的高度压缩。

㈤ 小世界网络模型的NW小世界模型构造算法

1、一个环状的规则网络开始：网络含有N个结点，每个结点向与它最临近K个结点连出K条边，并满足N>>K>>ln(N)>>1。
2、随机化加边：以概率p在随机选取的一对节点之间加上一条边。其中，任意两个不同节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。改变p值可以实现从最临近耦合网络(p=0)向全局耦合网络(p=1)转变。当p足够小和N足够大时，NW小世界模型本质上等同于WS小世界模型。

㈥ 小世界网络模型的WS小世界模型构造算法

1、一个环状的规则网络开始：网络含有N个结点，每个节点向与它最临近的K个节点连出K条边，并满足N>>K>>ln(N)>>1。
2、随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。这样就会产生pNK/2条长程的边把一个节点和远处的结点联系起来。改变p值可以实现从规则网络(p=0)向随机网络(p=1)转变。

㈦ 二叉树 构造算法

http://www.programfan.com/club/showbbs.asp?id=13378
自己去看看哈

㈧ 最优二叉树算法的构造算法

从上述算法中可以看出，F实际上是森林，该算法的思想是不断地进行森林F中的二叉树的“合并”，最终得到哈夫曼树。
在构造哈夫曼树时，可以设置一个结构数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n－1个结点，所以数组HuffNode的大小设置为2n－1，数组元素的结构形式如下： weight lchild rchild parent 其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为－1，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是－1了。
构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HuffNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。
下面给出哈夫曼树的构造算法。
const maxvalue= 10000; {定义最大权值}
maxleat=30; {定义哈夫曼树中叶子结点个数}
maxnode=maxleaf*2-1;
type HnodeType=record
weight: integer;
parent: integer;
lchild: integer;
rchild: integer;
end;
HuffArr:array[0..maxnode] of HnodeType;
var ……
procere CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼树的构造算法}
var i,j,m1,m2,x1,x2,n: integer;
begin
readln(n); {输入叶子结点个数}
for i:=0 to 2*n-1 do {数组HuffNode[ ]初始化}
begin
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
end;
for i:=0 to n-1 do read(HuffNode[i].weight); {输入n个叶子结点的权值}
for i:=0 to n-1 do {构造哈夫曼树}
begin
m1:=MAXVALUE; m2:=MAXVALUE;
x1:=0; x2:=0;
for j:=0 to n i-1 do
if (HuffNode[j].weight
begin m2:=m1; x2:=x1;
m1:=HuffNode[j].weight; x1:=j;
end
else if (HuffNode[j].weight
begin m2:=HuffNode[j].weight; x2:=j; end;
{将找出的两棵子树合并为一棵子树}
HuffNode[x1].parent:=n i; HuffNode[x2].parent:=n i;
HuffNode[n i].weight:= HuffNode[x1].weight HuffNode[x2].weight;
HuffNode[n i].lchild:=x1; HuffNode[n i].rchild:=x2;
end;
end;

㈨ 3DGIS中几种多分辨率模型构造算法的性能比较研究

摘要：本文对开源3DGIS软件VTP中的三种视点相关多分辨率地形模型生成算法-McNally算法、Rottger算法和TopoVista算法进行了比较实验研究。结果表明，在三角形数取1000时，如果使用三角彤带绘制，则McNally算法的运行速度最快，如果没有使用，则TopoVista算法最快；Rottger算法在CLOD算法中速度最慢，但是弹跳现象不如其他算法明显，效果要好；当三角形数量大于5000时，Rottger算法的表现始终优于McNally算法。