DDK提供了两种链表的数据结构,双向链表和单向链表,其定义如下: typedef struct _LIST_ENTRY { struct _LIST_ENTRY *Flink; struct _LIST_ENTRY *Blink; } LIST_ENTRY,*PLIST_ENTRY; typedef struct _SINGLE_LIST_ENTRY { struct _SINGLE_LIST_ENTRY *Next;} SINGLE_LIST_ENTRY, *PSINGLE_LIST_ENTR

原题链接:http://ac.jobdu.com/problem.php?pid=1113 题目描述: 如上所示,由正整数1,2,3……组成了一颗特殊二叉树.我们已知这个二叉树的最后一个结点是n.现在的问题是,结点m所在的子树中一共包括多少个结点. 比如,n = 12,m = 3那么上图中的结点13,14,15以及后面的结点都是不存在的,结点m所在子树中包括的结点有3,6,7,12,因此结点m的所在子树中共有4个结点. 输入: 输入数据包括多行,每行给出一组测试数据,包括两个整数m,n (1 <

给定一棵完全二叉树的头节点head,返回这棵树的节点个数.如果完全二叉树的节点数为N,请实现时间复杂度低于O(N)的解法. 分析:遍历的话不管是前序.中序.后序还是层次都是O(N),低于O(N)只能是O(lgN),向二分方向努力. 完全二叉树:除最后一层外,每一层上的节点数均达到最大值:在最后一层上只缺少右边的若干结点. 只有最后一层不满,我们可以根据左子树的最右节点或者右字数的最左节点来判断左子树是不是满二叉树, 若左字树满,可用公式计算左字树的节点数2^(l-1), 总节点数n= 2^(l-

输入 二叉树的先序遍历序列,用#代表空树或空子树. 输出 共五行 前三行依次输出先序.中序和后序遍历序列, 第四行输出二叉树的高度, 第五行依次输出二叉树总结点数目.叶子结点数目.度为1的结点数目. 样例输入 A B # D # # C E # # F # # 样例输出 PreOrder: A B D C E FInOrder: B D A E C FPostOrder: D B E F C A36 3 1 题目很简单,基本的二叉树操作.需要注意的是输入结点之间有空格,而且输出结点时也有空格,行

int GetNodeNumKthLevel(BiTNode * pRoot, int k) { if(pRoot == NULL || k < 1) return 0; if(k == 1) return 1; int numLeft = GetNodeNumKthLevel(pRoot->lchild, k-1); // 左子树中k-1层的节点个数 int numRight = GetNodeNumKthLevel(pRoot->rchild, k-1); // 右子树中k-1层的节

Description It’s an interesting experience to move from ICPC to work, end my college life and start a brand new journey in company. As is known to all, every stuff in a company has a title, everyone except the boss has a direct leader, and all the re

1. 什么是红黑树 (1) 简介     上一篇我们介绍了基本动态集合操作时间复杂度均为O(h)的二叉搜索树.但遗憾的是,只有当二叉搜索树高度较低时,这些集合操作才会较快:即当树的高度较高(甚至一种极端情况是树变成了1条链)时,这些集合操作并不比在链表上执行的快.     于是我们需要构建出一种"平衡"的二叉搜索树.     红黑树(red-black tree)正是其中的一种.它可以保证在最坏的情况下,基本集合操作的时间复杂度是O(lgn). (2) 性质     与普通二叉搜索树不

哈夫曼树 哈夫曼树也叫最优二叉树(哈夫曼树) 问题:什么是哈夫曼树? 例:将学生的百分制成绩转换为五分制成绩:≥90 分: A,80-89分: B,70-79分: C,60-69分: D,<60分: E. if (a < 60){ b = 'E'; } else if (a < 70) { b = ‘D’; } else if (a<80) { b = ‘C’; } else if (a<90){ b = ‘B’; } else { b = ‘A’; } 判别树:用于描述分类

Description 给定一棵结点数为n的树,初始点权均为0,有依次q个操作,每次操作有三个参数a,b,c,当a=1时,表示给b号结点到c号结点路径上的所有点(包括b,c,下同)权值都增加1,当a=2时,表示询问b号结点到c号结点路径上的所有点权值之和. Input 第一行,一个正整数n. 接下来n-1行,每行一对正整数x,y,表示x号结点和y号结点之间有一条边. 第n+1行,一个正整数q. 最后q行,每行一组正整数a,b,c,表示操作的三个参数.b和c可能相等. 保证数据都是合法的. Out

codevs 2879 堆的判断 http://codevs.cn/problem/2879/ 题目描述 Description 堆是一种常用的数据结构.二叉堆是一个特殊的二叉树,他的父亲节点比两个儿子节点要大,且他的左右子树也是二叉堆.现在输入一颗树(用二叉树的数组表示,即a[i]的左儿子与右儿子分别为a[2i],a[2i+1]),要求判断他是否是一个堆. 输入描述 Input Description 一个整数N,表示结点数. 第二行N个整数,表示每个结点代表的数字 输出描述 Output D

1.基本概念 a.路径和路径长度 若在一棵树中存在着一个结点序列 k1,k2,……,kj, 使得 ki是ki+1 的双亲(1<=i<j),则称此结点序列是从 k1 到 kj 的路径. 从 k1 到 kj 所经过的分支数称为这两点之间的路径长度,它等于路径上的结点数减1. b.结点的权和带权路径长度 在许多应用中,常常将树中的结点赋予一个有着某种意义的实数,我们称此实数为该结点的权,(如下面一个树中的蓝色数字表示结点的权) 结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘

2879 堆的判断  时间限制: 1 s  空间限制: 32000 KB  题目等级 : 黄金 Gold   题目描述 Description 堆是一种常用的数据结构.二叉堆是一个特殊的二叉树,他的父亲节点比两个儿子节点要大,且他的左右子树也是二叉堆.现在输入一颗树(用二叉树的数组表示,即a[i]的左儿子与右儿子分别为a[2i],a[2i+1]),要求判断他是否是一个堆. 输入描述 Input Description 一个整数N,表示结点数. 第二行N个整数,表示每个结点代表的数字 输出描述 O

题意 求节点数为\(n\)的有根树期望的叶子结点数.(\(n \le 10^9\)) 分析 神题就打表找规律.. 题解 方案数就是卡特兰数,$h_0=1, h_n = \sum_{i=0}^{n-1} h_i h_{n-1-i} \(. 设叶子数量和为\)f_n\(,则得到\)f_n = 2 \sum_{i=0}^{n-1} f_i h_{n-1-i}$ 设\(H(x)\)表示\(h_n\)的母函数,\(F(x)\)表示\(f_n\)的母函数 容易得到:\[H(x) = x H^2(x) + 1

哈希表(Hash Table)是一种特殊的数据结构,它最大的特点就是可以快速实现查找.插入和删除.因为它独有的特点,Hash表经常被用来解决大数据问题,也因此被广大的程序员所青睐.为了能够更加灵活地使用Hash来提高我们的代码效率,今天,我们就谈一谈Hash的那点事. 1. 哈希表的基本思想 我们知道,数组的最大特点就是:寻址容易,插入和删除困难:而链表正好相反,寻址困难,而插入和删除操作容易.那么如果能够结合两者的优点,做出一种寻址.插入和删除操作同样快速容易的数据结构,那该有多好.这就是哈希

数据结构中有很多树的结构,其中包括二叉树.二叉搜索树.2-3树.红黑树等等.本文中对数据结构中常见的几种树的概念和用途进行了汇总,不求严格精准,但求简单易懂. 1. 二叉树 二叉树是数据结构中一种重要的数据结构,也是树表家族最为基础的结构. 二叉树的定义:二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒.二叉树的第i层至多有2i-1个结点:深度为k的二叉树至多有2k-1个结点:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=

[BZOJ2391]Cirno的忧郁 试题描述 Cirno闲着无事的时候喜欢冰冻青蛙. Cirno每次从雾之湖中固定的n个结点中选出一些点构成一个简单多边形,Cirno运用自己的能力能将此多边形内所有青蛙冰冻. 雾之湖生活着m只青蛙,青蛙有大有小,所以每只青蛙的价值为一个不大于10000的正整数. Cirno很想知道每次冻住的青蛙的价值总和.因为智商有限,Cirno将这个问题交给完美算术教室里的你. 因为爱护动物,所以每次冻结的青蛙会被放生.也就是说一只青蛙可以被多次统计. 输入 第一行2个正整

//最优二叉树 #include <iostream> #include <iomanip> using namespace std; //定义结点类型 //[weight | lchid | rchild | parent] //为了判定一个结点是否已加入到要建立的哈夫曼树中 //可通过parent域的值来确定. //初始时parent = -1,当结点加入到树中时,该结点parent的值 //为其父亲结点在数组Huffman中的序号. template<typename

B-树 1 .B-树定义 B-树是一种平衡的多路查找树,它在文件系统中很有用. 定义:一棵m 阶的B-树,或者为空树,或为满足下列特性的m 叉树: ⑴树中每个结点至多有m 棵子树: ⑵若根结点不是叶子结点,则至少有两棵子树: ⑶除根结点之外的所有非终端结点至少有[m/2] 棵子树: ⑷所有的非终端结点中包含以下信息数据: (n,A0,K1,A1,K2,…,Kn,An) 其中:Ki(i=1,2,…,n)为关键码,且Ki<Ki+1,  Ai 为指向子树根结点的指针(i=0,1,…,n),且指针Ai-

1001. A+B Format (20) 注意负数,没别的了. 用scanf来补 前导0 和 前导的空格 很方便. #include <iostream> #include <cstdio> using namespace std; ]; int main() { int A,B; cin>>A>>B; A+=B; ) { A=-A; cout<<"-"; } ; while(A) { a[n++]=A%; A/=; } ;

B-树 1 .B-树定义 B-树是一种平衡的多路查找树,它在文件系统中很有用. 定义:一棵m 阶的B-树,或者为空树,或为满足下列特性的m 叉树:⑴树中每个结点至多有m 棵子树:⑵若根结点不是叶子结点,则至少有两棵子树: ⑶除根结点之外的所有非终端结点至少有[m/2] 棵子树:⑷所有的非终端结点中包含以下信息数据: (n,A0,K1,A1,K2,…,Kn,An)其中:Ki(i=1,2,…,n)为关键码,且Ki<Ki+1,  Ai 为指向子树根结点的指针(i=0,1,…,n),且指针Ai-1 所指

原文链接:https://www.dreamwings.cn/ytu3027/2899.html 3027: 哈夫曼编码 时间限制: 1 Sec  内存限制: 128 MB 提交: 2  解决: 2 题目描述 设计一个程序,构造一颗哈夫曼树,输出对应的哈夫曼编码. 输入 输入数据有两行,第一行为一个整数n,代表接下来要输入n个整数,然后我们用这n个整数构造一个哈夫曼树. 输出 输出对应的哈夫曼编码,每一个哈夫曼编码占一行. 样例输入 8 7 19 2 6 32 3 21 10 样例输出 1010