科学网 › 标签 › 二叉树

标签: 二叉树

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

[转载]二叉树的两种遍历输出结果还原二叉树: EnergeticYi 2013-8-1 22:04; 以前做这种题蛮熟练的，放了两个学期没管它，今天再来做就太.......伤脑子了不过还好，还是想起怎么做了这里把我的方法分享给大家，希望还不会的朋友能有所收获，也希望能得到更好的解决办法【题目】假设一棵二叉树的后序遍历序列为 DGJHEBIFCA ，中序遍历序列为 DBGEHJACIF ，则其前序遍历序列为 ( ) 。 A. ABCDEFGHIJ B. ABDEGHJCFI C. ABDEGHJFIC D. ABDEGJHCFI 由题，后序遍历的最后一个值为A，说明本二叉树以节点A为根节点（当然，答案中第一个节点都是A，也证明了这一点）下面给出整个分析过程【第一步】由后序遍历的最后一个节点可知本树根节点为【A】加上中序遍历的结果，得知以【A】为根节点时，中序遍历结果被【A】分为两部分【DBGEHJ】【A】【CIF】于是作出第一幅图如下【第二步】将已经确定了的节点从后序遍历结果中分割出去即【DGJHEBIFC】---【A】此时，位于后序遍历结果中的最后一个值为【C】说明节点【C】是某棵子树的根节点又由于【第一步】中【C】处于右子树，因此得到，【C】是右子树的根节点于是回到中序遍历结果【DBGEHJ】【A】【CIF】中来，在【CIF】中，由于【C】是根节点，所以【IF】都是这棵子树的右子树，【CIF】子树没有左子树，于是得到下图【第三步】将已经确定了的节点从后序遍历中分割出去即【DGJHEBIF】---【CA】此时，位于后序遍历结果中的最后一个值为【F】说明节点【F】是某棵子树的根节点又由于【第二步】中【F】处于右子树，因此得到，【F】是该右子树的根节点于是回到中序遍历结果【DBGEHJ】【A】【C】【IF】中来，在【IF】中，由于【F】是根节点，所以【I】是【 IF】这棵子树的左子树，于是得到下图【第四步】将已经确定了的节点从后序遍历中分割出去即【DGJHEB】---【IFCA】此时，位于后序遍历结果中的最后一个值为【B】说明节点【B】是某棵子树的根节点又由于【第一步】中【B】处于【A】的左子树，因此得到，【B】是该左子树的根节点于是回到中序遍历结果【DBGEHJ】【A】【C】【F】【I】中来，根据【B】为根节点，可以将中序遍历再次划分为【D】【B】【GEHJ】【A】【C】【F】【I】，于是得到下图【第五步】将已经确定了的节点从后序遍历中分割出去即【DGJHE】---【BIFCA】此时，位于后序遍历结果中的最后一个值为【E】说明节点【E】是某棵子树的根节点又由于【第四步】中【E】处于【B】的右子树，因此得到，【E】是该右子树的根节点于是回到中序遍历结果【D】【B】【GEHJ】【A】【C】【F】【I】中来，根据【B】为根节点，可以将中序遍历再次划分为【D】【B】【G】【E】【HJ】【A】【C】【F】【I】，于是得到下图【第六步】将已经确定了的节点从后序遍历中分割出去即【DGJH】---【EBIFCA】此时，位于后序遍历结果中的最后一个值为【H】说明节点【H】是某棵子树的根节点又由于【第五步】中【H】处于【E】的右子树，因此得到，【H】是该右子树的根节点于是回到中序遍历结果【D】【B】【G】【E】【HJ】【A】【C】【F】【I】中来，根据【H】为根节点，可以将中序遍历再次划分为【D】【B】【G】【E】【H】【J】【A】【C】【F】【I】，于是得到下图至此，整棵二叉树已经还原现在对该二叉树进行前序遍历便能得到我们想要的答案【B】; 1 次阅读|0 个评论

[转载]用二叉树表示表达式: EnergeticYi 2013-7-30 09:57; 　　先看中缀表达式的二叉树表示：　　　　 /* * 中缀表达式构建二叉树 * * 方法：每次找到“最后计算”的运算符，作为当前树的根，然后递归处理 * 详见刘汝佳《算法竞赛入门经典》 P198 * */ #include iostream using namespace std; const int maxn = 1000 ; // 每个节点的左右儿子编号 int lch , rch ; // 节点的字符 char op ; // 节点数 int cnt = 0 ; // s的 = rch = - 1 ; op = s ; return u; } // p==0表示在括号外 for ( int i=x; iy; i++){ switch (s ){ case ' ( ' : p++; break ; case ' ) ' : p--; break ; case ' + ' : case ' - ' : if (p == 0 ) c1 = i; // p==0说明s 不在括号内 break ; case ' * ' : case ' / ' : if (p == 0 ) c2 = i; break ; } } if (c1 0 ) c1 = c2; // 括号外没有 + 或 - ，则选括号外的 * 或 / if (c1 0 ) return buildTree(s, x+ 1 , y- 1 ); // 括号外也没有* 或 /，说明表达式被一个括号括住，去括号 u = cnt++; lch = buildTree(s, x, c1); rch = buildTree(s, c1+ 1 , y); op = s ; return u; } int main(){ return 0 ; } 下面是转的：包括中缀、后缀、前缀用二叉树表示：　　　　 2. 需求分析：（1）功能：表达式可以用二叉树表示，对于简单的四则运算，请实现以下功能【1】对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且图示出来（图形的形式）。【2】对于构造好的内部表达式二叉树，按照用户的要求输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括）或后缀表达式（不带括号）。提示：所谓中缀表达式中的冗余括号，就是去掉括号后不影响表达式的计算顺序。例如：“（c+b）+a”中的括号是冗余的，可以表示成不冗余的“c+b+a”。（2）输入输出要求：请输入字符串表达式：树形二叉树（图形显示）中缀表达式为：前缀表达式为：后缀表达式为： 3. 概要设计：（算法）分成两部分完成：【1】前缀、中缀、后缀表达式-二叉树表达式前缀表达式-二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈；（b）碰到操作符则把其值赋给相应的新申请的二叉树，并从栈中弹出两个地址，分别作为其右指针和左指针，然后再把其地址压栈，最后一个地址即为二叉树的根结点地址。中缀表达式-二叉树表达式：把中缀表达式转换成后缀表达式，然后再建立二叉树。后缀表达式-二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，压栈；（b）碰到操作符则把其值赋给相应的新申请的二叉树结点，取栈顶元素，取栈顶元素分别作为右、左节点。开始时用变量root保存。【1】二叉树表达式-前缀、中缀、后缀表达式二叉树表达式-前缀表达式：对二叉树表达式进行前序遍历。二叉树表达式-中缀表达式：对二叉树表达式进行中序遍历，若结点操作符的优先级高于其左或右子树，在打印相应的子树之前先打印开括号，在打印相应的子树最后在打印一个闭括号。二叉树表达式-后缀表达式：对二叉树表达式进行后序遍历。建立表达式树就是建立树中的每一个结点，将每一个结点链接起来就是整棵树。而在建立深度低的结点时要将其左右指针指向之前建立的深度比它高一级的结点(如’*’要指向’2’和’3’，而’+’又要指向’*’)。这样我们可以用栈来存放每次建立的结点，按照优先级(表达式为中缀型)或顺序扫描表达式(表达式为波兰式与逆波兰式)建立每一个结点。建立结点的顺序即为表达式求值的顺序。如果扫描到操作数则直接新建一个左右指针为空的结点，并压入结点栈中(存放结点指针)。遇到运算符时首先新建一个结点，然后从栈中依次弹出两个结点，并让新建立的结点的左右指针域指向它们。当所有结点建立完毕时，如果表达式没有错误(这里假设输入表达式正确)，这时栈中应该只剩下一个结点，它就是所建立的表达式的根结点。 4. 详细设计：（具体方法）首先创建一个节点类TNode：包含操作符oper、左孩子left、右孩子right，isOper（）判断是否为操作符，getOperOrder（）返回运算符op所对应的优先级，freeTree（）程序结束销毁二叉树，postOrder（）先序遍历，preOrder（）后序遍历，inOrder（）中序遍历，ExpTree1（）后缀表达式生成二叉树，ExpTree3（）前缀表达式生成二叉树，ExpTree2（）中后缀表达式生成二叉树，count（）求值函数，paint（）输出函数附代码： #include iostream #include stack #include queue #include string #includemath.h using namespace std; class TNode // 节点类 { public : char oper; TNode *left; TNode *right; int s； int t； TNode() { left=right=NULL; oper= 0 ; } TNode( char op) { left=right=NULL; oper=op;}}; bool isOper( char op) // 判断是否为运算符 { char oper ) { return true ; } } return false ;} int getOperOrder( char op) // 返回运算符op所对应的优先级 { switch (op) { case ' ( ' : return 1 ; case ' + ' : case ' - ' : return 2 ; case ' * ' : case ' / ' : return 3 ; case ' ^ ' : return 4 ; default : // 定义在栈中的右括号和栈底字符的优先级最低 return 0 ; } } void freeTree(TNode *p) // 释放树 { if (p-left!=NULL) freeTree(p-left); if (p-right!=NULL) freeTree(p-right); delete(p); cout " Memory free " ; } void postOrder(TNode *p) // 先序遍历 { if (p) { postOrder(p-left); postOrder(p-right); coutp-oper; } } void preOrder(TNode *p) // 后序遍历 { if (p) { coutp-oper; preOrder(p-left); preOrder(p-right); } } void inOrder(TNode *p) // 中序遍历 { if (p) { if (p-left) { if (isOper(p-left-oper) getOperOrder(p-left-oper) getOperOrder(p-oper)) { cout " ( " ; inOrder(p-left); cout " ) " ; } else { inOrder(p-left); } } coutp-oper; if (p-right) { if (isOper(p-right-oper) getOperOrder(p-right-oper) =getOperOrder(p-oper)) { cout " ( " ; inOrder(p-right); cout " ) " ; } else { inOrder(p-right); } } } } void ExpTree1(TNode *p, string str) // 后缀表达式生成二叉树 {stack TNode* nodeStack; char temp; int i= 0 ; temp=str ; while (temp!= ' \0 ' ) { if (temp!= ' \0 ' !isOper(temp)) // 不是运算符，则进栈 { p= new TNode(temp); // 以temp为结点值构造二叉树结点 nodeStack.push(p); temp=str ;} else { p= new TNode(temp); if (nodeStack.size()) { p-right=nodeStack.top(); // 若非空则弹栈并设为结点的右孩子 nodeStack.pop(); } if (nodeStack.size()) { p-left=nodeStack.top(); // 若非空则弹栈并设为结点的左孩子 nodeStack.pop(); } nodeStack.push(p); temp=str ; } } } void ExpTree3(TNode *p, string str) // 前缀表达式生成二叉树 { stack TNode* nodeStack; char temp; int i=str.size()- 1 ; temp=str ; while (temp!= ' \0 ' ) { if (temp!= ' \0 ' !isOper(temp)) { p= new TNode(temp); // 以temp为内容来建立新的结点 nodeStack.push(p); temp=str ;} else { p= new TNode(temp); if (nodeStack.size()) // 若栈顶指针所指结点左孩子为空 { p-left=nodeStack.top(); // 则当前结点设置成其左孩子 nodeStack.pop(); } if (nodeStack.size()) // 若栈顶指针所指结点右孩子为空 { p-right=nodeStack.top(); // 则当前结点设置成其右孩子 nodeStack.pop(); // 栈顶元素左右孩子指针设置完毕弹出 } nodeStack.push(p); temp=str ; } } } void ExpTree2(TNode *p, string str) // 中缀表达式转换成后缀表达式生成二叉树 { stack char a; char temp; string Postfixexp= "" ; int i= 0 ; temp=str ; while (temp!= ' \0 ' ) { if (!isOper(temp)) { Postfixexp+=temp; temp=str ;} else if (temp== ' ( ' ) // 进栈 { a.push(temp); temp=str ;} else if (temp== ' ) ' ){ while (a.top()!= ' ( ' ) // 脱括号 { Postfixexp+=a.top(); a.pop(); // 在碰到开括号和栈为空前反复弹出栈中元素 } a.pop(); temp=str ; } else if (temp== ' + ' ||temp== ' - ' ||temp== ' * ' ||temp== ' / ' ) // 出栈{ while (!a.empty()a.top()!= ' ( ' getOperOrder(a.top())=getOperOrder(temp)) // 若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时， // 将栈顶元素弹出到后缀表达式中，并且str下标加1 { Postfixexp+=a.top(); a.pop(); } a.push(temp); temp=str ; } } while (!a.empty()) { Postfixexp+=a.top(); a.pop(); } ExpTree1(p,Postfixexp); } void count(TNode *p, int height, int n) // 求值函数 { if (p-left==NULLp-right==NULL) { if (nheight) height=n;} if (p-left!=NULL) count(p-left,height,n+ 1 ); if (p-right!=NULL) count(p-right,height,n+ 1 ); } void paint(TNode *p) // 输出函数 { int height= 0 ; int h= 0 ; int i; using std::queue; queueTNode* aQueue; count(p,height, 1 ); TNode *pointer=p; TNode *lastpointer; if (pointer) { pointer-s= 1 ; pointer-t= 1 ; aQueue.push(pointer); } while (!aQueue.empty()) { lastpointer=pointer; pointer=aQueue.front(); aQueue.pop(); if (pointer-sh) {coutendl; h=pointer-s;} if (pointer-t== 1 ) { for (i= 0 ;ipow( 2 ,height-pointer-s)- 1 ;i++) cout " " ;} else if (lastpointer-s!=pointer-s){ for (i= 0 ;i(pointer-t- 1 )*(pow( 2 ,height-pointer-s+ 1 )- 1 )+(pointer-t- 1 )- 1 +pow( 2 ,height-pointer-s);i++) cout " " ; } else { for (i= 0 ;i(pointer-t-lastpointer-t)*(pow( 2 ,height-pointer-s+ 1 )- 1 )+(pointer-t-lastpointer-t)- 1 ;i++) cout " " ; } coutpointer-oper; if (pointer-left!=NULL){ pointer-left-s=pointer-s+ 1 ; pointer-left-t=pointer-t* 2 - 1 ; aQueue.push(pointer-left);} if (pointer-right!=NULL){ pointer-right-s=pointer-s+ 1 ; pointer-right-t=pointer-t* 2 ; aQueue.push(pointer-right); } } } int main() { string expression; TNode *tree; coutendl " 请输入字符串表达式: " ; cinexpression; if (isOper(expression )) ExpTree3(tree,expression); else if (isOper(expression )) ExpTree2(tree,expression); else ExpTree1(tree,expression); paint(tree); coutendl; cout " 中缀表达式为: " ; inOrder(tree); coutendl; cout " 前缀表达式为: " ; preOrder(tree); coutendl; cout " 后缀表达式为: " ; postOrder(tree); coutendl; freeTree(tree); coutendl; system( " pause " ); return 0 ; }; 0 个评论

二叉树模型的改进版: 热度 1 itellin 2013-2-14 19:01; 这次改进是把标的的价格也在图形中显示出来，这样就可以知道什么价格有什么权利金。 # ce 欧式看涨，pe 欧式看跌，ca 美式看涨，pa 美式看跌 # S 标的价格，X 敲定价格，Time 到期日 # u 上涨幅度，d 下跌幅度，r 年利率，n 期数 # 计算权利金 BiTreeOption = function (TypeFlag = c("ce", "pe", "ca", "pa"), S, X, Time, u, d, r, n) { TypeFlag = TypeFlag if (TypeFlag == "ce" || TypeFlag == "ca") z = +1 if (TypeFlag == "pe" || TypeFlag == "pa") z = -1 dt = Time/n p = (exp(r * dt) - d)/(u - d) Df = exp(-r * dt) OptionValue = z * (S * u^(0:n) * d^(n:0) - X) offset = 1 Tree = OptionValue = (abs(OptionValue) + OptionValue)/2 if (TypeFlag == "ce" || TypeFlag == "pe") { for (j in (n - 1):0) { Tree - c(Tree, rep(0, times = n - j)) for (i in 0:j) { OptionValue = (p * OptionValue + (1 - p) * OptionValue ) * Df Tree = c(Tree, OptionValue ) } } } if (TypeFlag == "ca" || TypeFlag == "pa") { for (j in (n - 1):0) { Tree - c(Tree, rep(0, times = n - j)) for (i in 0:j) { OptionValue = max((z * (S * u^i * d^(abs(i - j)) - X)), (p * OptionValue + (1 - p) * OptionValue ) * Df) Tree = c(Tree, OptionValue ) } } } Tree = matrix(rev(Tree), byrow = FALSE, ncol = n + 1) # 计算标的价格 genprice - function(S, u, d, n) { X - c() X - S count - 2 for (i in 1:n) { for (j in i:0) { X - S * u^j * d^(i-j) count - count + 1 } } return(X) } # 转换为上三角矩阵 x - genprice(S=S, u=u, d=d, n=n) len - 2*length(x) m - (-1+sqrt(1+4*len))/2 BiPrice - matrix(0,m,m) BiPrice - x MA - list(Tree,BiPrice) invisible(MA) } #画图 BiTreePlot - function (BTree, dx = -0.025, dy = 0.4, cex = 1, digits = 2, ...) { Tree = round(BTree ], digits = digits) FP = round(BTree ], digits = digits) depth = ncol(Tree) plot(x = c(1, depth), y = c(-depth + 1, depth - 1), type = "n", col = 0, ...) points(x = 1, y = 0, pch=19) text(1 + dx, 0 + dy, paste(deparse(FP ),deparse(Tree ),sep="/"), cex = cex) for (i in 1:(depth - 1)) { y = seq(from = -i, by = 2, length = i + 1) x = rep(i, times = length(y)) + 1 points(x, y, col = 1,pch = 20) for (j in 1:length(x)) text(x + dx, y + dy, paste(deparse(FP ), deparse (Tree ), sep = "/"), cex = cex) y = (-i):i x = rep(c(i + 1, i), times = 2 * i) lines(x, y, col = 2) } invisible() } BTree = BiTreeOption(TypeFlag = "pa",S = 50,X = 50,Time = 5/12,u = 1.1224,d = 0.8909,r = 0.1,n = 5) BiTreePlot(BTree, dy = 1, cex = 0.8, ylim = c(-6, 7),xlab = "期数", ylab = "标的价价/权利金") title(main = "二叉树模型"); 2358 次阅读|2 个评论

二叉树模型的计算: itellin 2013-2-13 14:07; 网上看到很多二叉树模型都是用上涨幅度和下跌幅度来代替软件中的波动率，其实这两者是可以相互转换的，但是为了和国内接轨，于是把用波动率做参数改成用上涨幅度做参数，这样便于计算。 # ce 欧式看涨，pe 欧式看跌，ca 美式看涨，pa 美式看跌 # S 标的价格，X 敲定价格，Time 标的期限 # u 上涨幅度，d 下跌幅度，r 年利率，n 期数 #用二叉树模型计算权利金 BiTreeOption = function (TypeFlag = c("ce", "pe", "ca", "pa"), S, X, Time, u, d, r, n) { TypeFlag = TypeFlag if (TypeFlag == "ce" || TypeFlag == "ca") z = +1 if (TypeFlag == "pe" || TypeFlag == "pa") z = -1 dt = Time/n p = (exp(r * dt) - d)/(u - d) Df = exp(-r * dt) OptionValue = z * (S * u^(0:n) * d^(n:0) - X) offset = 1 Tree = OptionValue = (abs(OptionValue) + OptionValue)/2 if (TypeFlag == "ce" || TypeFlag == "pe") { for (j in (n - 1):0) { Tree - c(Tree, rep(0, times = n - j)) for (i in 0:j) { OptionValue = (p * OptionValue + (1 - p) * OptionValue ) * Df Tree = c(Tree, OptionValue ) } } } if (TypeFlag == "ca" || TypeFlag == "pa") { for (j in (n - 1):0) { Tree - c(Tree, rep(0, times = n - j)) for (i in 0:j) { OptionValue = max((z * (S * u^i * d^(abs(i - j)) - X)), (p * OptionValue + (1 - p) * OptionValue ) * Df) Tree = c(Tree, OptionValue ) } } } Tree = matrix(rev(Tree), byrow = FALSE, ncol = n + 1) invisible(Tree) } #画图 BiTreePlot - function (BTree, dx = -0.025, dy = 0.4, cex = 1, digits = 2, ...) { Tree = round(BTree, digits = digits) depth = ncol(Tree) plot(x = c(1, depth), y = c(-depth + 1, depth - 1), type = "n", col = 0, ...) points(x = 1, y = 0) text(1 + dx, 0 + dy, deparse(Tree ), cex = cex) for (i in 1:(depth - 1)) { y = seq(from = -i, by = 2, length = i + 1) x = rep(i, times = length(y)) + 1 points(x, y, col = 1) for (j in 1:length(x)) text(x + dx, y + dy, deparse(Tree ), cex = cex) y = (-i):i x = rep(c(i + 1, i), times = 2 * i) lines(x, y, col = 2) } invisible() } 用一个例子说明，假设有标的资产为不付红利的股票，市价是50元，上涨幅度是1.2224，下跌幅度是0.8909，无风险连续复利率为10%，该股票5月期的美式看跌期权敲定价格为50元，求该期权的价值。 BTree = BiTreeOption(TypeFlag = "pa",S = 50,X = 50,Time = 5/12,u = 1.1224,d = 0.8909,r = 0.1,n = 5) BiTreePlot(BTree, dy = 1, cex = 0.8, ylim = c(-6, 7),xlab = "n", ylab = "权利金") title(main = "二叉树模型") 从图中可以看出，该股票的期权价值是4.49元。; 3029 次阅读|0 个评论

[转载]数据结构——赫夫曼树(最优二叉树): yzcck 2012-6-26 12:40; 路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。树的路径长度：从树根到每一个结点的路径长度之和。结点的带全路径长度：从该结点到树根之间的路径长度与结点上权的乘积。树的带全路径长度：树中所有叶子结点的带全路径长度之和，WPL = Σ (wi x li)，其中wi是叶子结点的权重，li是从根到该叶子结点的路径长度，注意，带全路径长度只有叶子结点有权重！其他结点只计算长度无权重！。来看书上三个树的WPL： WPL(a) = 7*2 + 5* 2 + 2*2 +4*2 = 36 WPL(b)=4*2 + 7*3 + 5*3 + 2 = 46 WPL(c) = 7 + 5 * 2 + 3 * 2 + 4 * 3 = 35 其实c是最优二叉树。赫夫曼(Huffman)树，又称最优二叉树，是一类带全路径长度最短的树。赫夫曼编码的用途很广，例如优化if分支条件的组合、数据压缩等等。赫夫曼算法设有n个叶子结点，则有对应的n个权值w1…wn。 (1)首先构成n棵二叉树，每棵二叉树中以wi为根结点，左右孩子均为空，设n棵二叉树位于集合F中。 (2)在F中选取两棵根结点权值最小的树做为左右子树，构造一棵新的二叉树，并设置根结点的权值为左、右子树上的根结点的权值之和。 (3)在F中删除这两棵被选中的子树，并且在F中加入新树。 (4)重复(2)和(3)直到F中只包含一棵树为止。最后形成的这棵树便是赫夫曼树。其实，赫夫曼算法的思想很简单：让权值大的尽量少在路径短的上面。权值小的在路径长的上面。由于赫夫曼树中没有度为1的结点，所以一棵有n个叶子结点的赫夫曼树一定有2n-1个结点。赫夫曼编码在需要压缩编码的时候，可以另每种字符做为叶子结点，借助最优二叉树(赫夫曼树)设计长短不等的编码。这种编码叫做前缀编码：长短不等的编码，且必须是任意一个字符的编码都不是另一个字符编码的前缀。由于赫夫曼编码不仅需要左、右孩子，还需要双亲、还需要计算和合并。我们可以采用如下的结点数据结构： struct HFNode { int weight; int parent, lchild, rchild; }; typedef struct HFNode HFTree; 如上所述，weight是结点的权重。赫夫曼树用数组存放，lchild和rchild是左右孩子在数组中的下标。有了这个结构后，实现赫夫曼树的算法就比较简单了。算法共分为三部分： (1)构造赫夫曼树 (2)计算(打印)字符的赫夫曼编码 (3)利用赫夫曼编码译码首先是构造赫夫曼树的编码，假设n个叶子结点(要编码的字符) ，我们用2*n-1个结点的数组存储赫夫曼树： (a) 是n个叶子结点和weight，parent都是-1（未决定），lchild和rchild是0。 (b) .weight = tree .lchild = tree .rchild = 0; tree .parent = -1; } } int hftree_min(HFTree tree, int start, int end) { int min = 0; int minw = 0xffffff; int i; for(i=start; i=end;i++) { if(tree .parent==-1 tree .weightminw) { minw = tree .weight; min = i; } } return min; } void hftree_build(HFTree tree, int* w, int nw) { int i, m; int min1, min2; // First , fill HFTree with weight (leaf node) for(i=0;inw;i++) { tree .weight = w ; tree .lchild = tree .rchild = 0; // leaf has no left or right child tree .parent = -1; // parent undefined } // Second, build tree and set no-leaf node into HFTree min1 = hftree_min(tree, 0, i-1); tree .parent = i; min2 = hftree_min(tree, 0, i-1); tree .parent = i; // Make new node and store at i tree .lchild = min1; tree .rchild = min2; tree .weight = tree .weight + tree .weight; tree .parent = -1; } } int main() { int i; int w = {5, 29, 7, 8, 14, 23, 3, 11}; int n = sizeof(w) / sizeof(int); HFNode hftree ; // Init hftree_init(hftree); // Make tree hftree_build(hftree, w, n); // Print Test //for(i=0;i2*n-1;i++) //{ // printf(“%2d %2d %2d %2d\n”, hftree .weight, hftree .parent, hftree .lchild, hftree .rchild); //} hfcode_encode(hftree, w, n); return 0; } 然后是给每个字符(叶子结点) 赋予0/1编码，我们这里规定左子树0，右子树1： void hfcode_encode(HFTree tree, int* w, int nw) { char tmp ; int i, p, j; // Get Huffman code each leaf to root for(i=0;inw;i++) { j = 0; p = i; while(tree .parent!=-1) { if(tree .parent].lchild==p) { tmp = '0'; } else if(tree .parent].rchild==p) { tmp = '1'; } p = tree .parent; } tmp = ''; // Print huffman code printf("%2d: %s\n", w , tmp); } } 最后的编码结果： 5: 1000 29: 01 7: 0111 8: 1111 14: 011 23: 10 3: 0000 11: 100; 3336 次阅读|0 个评论

[转载]KD-tree: hailuo0112 2012-4-5 21:28; Kd-树其实是K-dimension tree的缩写，是对数据点在k维空间中划分的一种数据结构。其实，Kd-树是一种平衡二叉树。举一示例：假设有六个二维数据点 = {（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间中。为了能有效的找到最近邻，Kd-树采用分而治之的思想，即将整个空间划分为几个小部分。六个二维数据点生成的Kd-树的图为：对于拥有n个已知点的kD-Tree，其复杂度如下：构建：O(log 2 n) 插入：O(log n) 删除：O(log n) 查询：O(n 1-1/k +m) m---每次要搜索的最近点个数一 Kd-树的构建 Kd-树是一个二叉树，每个节点表示的是一个空间范围。下表表示的是Kd-树中每个节点中主要包含的数据结构。Range域表示的是节点包含的空间范围。Node-data域就是数据集中的某一个n维数据点。分割超面是通过数据点Node-Data并垂直于轴split的平面，分割超面将整个空间分割成两个子空间。令split域的值为i，如果空间Range中某个数据点的第i维数据小于Node-Data ，那么，它就属于该节点空间的左子空间，否则就属于右子空间。Left，Right域分别表示由左子空间和右子空间空的数据点构成的Kd-树。域名数据类型描述 Node-Data 数据矢量数据集中某个数据点，是n维矢量 Range 空间矢量该节点所代表的空间范围 Split 整数垂直于分割超面的方向轴序号 Left Kd-tree 由位于该节点分割超面左子空间内所有数据点构成的Kd-树 Right Kd-tree 由位于该节点分割超面左子空间内所有数据点构成的Kd-树 Parent Kd-tree 父节点构建Kd-树的伪码为：算法：构建Kd-tree 输入：数据点集Data_Set，和其所在的空间。输出：Kd，类型为Kd-tree 1 if data-set is null ,return 空的Kd-tree 2 调用节点生成程序（1）确定split域：对于所有描述子数据（特征矢量），统计他们在每个维度上的数据方差，挑选出方差中最大值，对应的维就是split域的值。数据方差大说明沿该坐标轴方向上数据点分散的比较开。这个方向上，进行数据分割可以获得最好的分辨率。（2）确定Node-Data域，数据点集Data-Set按照第split维的值排序，位于正中间的那个数据点被选为Node-Data，Data-Set` =Data-Set\Node-data 3 dataleft = {d 属于Data-Set` d =Node-data } Left-Range ={Range dataleft} dataright = {d 属于Data-Set` d Node-data } Right-Range ={Range dataright} 4 :left =由（dataleft,LeftRange）建立的Kd-tree 设置:left的parent域（父节点）为Kd ：right =由（dataright,RightRange）建立的Kd-tree 设置：right的parent域为kd。如上例中，（1）确定：split 域=x，6个数据点在x,y 维度上的数据方差为39,28.63.在x轴方向上的方差大，所以split域值为x。（2）确定：Node-Data=（7,2），根据x维上的值将数据排序，6个数据的中值为7，所以node-data域为数据点（7,2）。这样该节点的分割超面就是通过（7,2）并垂直于：split=x轴的直线x=7. (3)左子空间和右子空间，分割超面x=7将整个空间分为两部分。x=7 为左子空间，包含节点（2,3），（5,4），（4，7），另一部分为右子空间。包含节点（9,6），（8,1）这个构建过程是一个递归过程。重复上述过程，直至只包含一个节点。在k-d树中进行数据的查找也是特征匹配的重要环节，其目的是检索在k-d树中与查询点距离最近的数据点。这里先以一个简单的实例来描述最邻近查找的基本思路。星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行'回溯'操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从（7,2）点开始进行二叉查找，然后到达（5,4），最后到达（2,3），此时搜索路径中的节点为（7,2），（5,4），（2,3），首先以（2,3）作为当前最近邻点，计算其到查询点（2.1,3.1）的距离为0.1414，然后回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如图4所示。发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中去搜索。再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为0.1414。一个复杂点了例子如查找点为（2，4.5）。同样先进行二叉查找，先从（7,2）查找到（5,4）节点，在进行查找时是由y = 4为分割超平面的，由于查找点为y值为4.5，因此进入右子空间查找到（4,7），形成搜索路径（7,2），（5,4），（4,7），取（4,7）为当前最近邻点，计算其与目标查找点的距离为3.202。然后回溯到（5,4），计算其与查找点之间的距离为3.041。以（2，4.5）为圆心，以3.041为半径作圆，如图5所示。可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找。此时需将（2,3）节点加入搜索路径中得（7,2），（2,3）。回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5。回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如图6所示。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。k-d树查询算法的伪代码如下所示。从root节点开始，DFS搜索直到叶子节点，同时在stack中顺序存储已经访问的节点。如果搜索到叶子节点，当前的叶子节点被设为最近邻节点。然后通过stack回溯: 如果当前点的距离比最近邻点距离近，更新最近邻节点. 然后检查以最近距离为半径的圆是否和父节点的超平面相交. 如果相交，则必须到父节点的另外一侧，用同样的DFS搜索法，开始检查最近邻节点。如果不相交，则继续往上回溯，而父节点的另一侧子节点都被淘汰，不再考虑的范围中. 当搜索回到root节点时，搜索完成，得到最近邻节点。; 个人分类: 学术坊|4192 次阅读|0 个评论

关于<<Logic in Computer Science>>这本书: junqing 2011-6-27 10:41; 看过这本书,给出一些感想: 它的英文名为"Logic in Computer Science".作者是 Michael Huth, Mark Ryan. 这本书主要介绍了命题逻辑,谓词逻辑,模型检测中的时态逻辑(包括,线性时态逻辑LTL,计算树逻辑CTL,以及CTL*),模型检测算法和不动点的证明,程序验证,模态逻辑,二叉树判定图.本书还给出相关的模型检测工具NuSMV等,介绍了Alloy语言. 从本书的结构上分析,前两章是基础,后面四章相对独立,但还是有一定关联的.本书还是介绍一些比较基础的理论,为进一步学习形式化和模型检测提供必要的知识.卡内基 -梅隆大学的Edmund M. Clarke教授给本书作序,可见本书的价值. 学过离散数学的同学,应该对前两章的内容是不会陌生的.这方面知识在本科阶段学习过,可惜后面的章节在本科阶段都没学过,甚至没听说过(很汉颜啊!). 有人认为这是本科所要求的内容,我不知道在中国有哪几个大学要求在本科阶段掌握这本书的内容.总之,我读本科的时候,根本就没有以这本书为教材;离散数学这门课倒是学过.在国外,是不是在本科阶段必选这门课?也就是说,在本科阶段就要掌握这方面的内容?(差距?) 现在看这本书,还是有一些疑问不是弄得很清楚,如果有人也学这方面的内容,大家可以一起探讨!; 5285 次阅读|0 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 二叉树

相关帖子

相关日志

关闭安全验证