数据结构树和二叉树的实际应用

数据结构树和二叉树有哪些实际应用？~

一个单位有10个部门，每个部门都有一部电话，但是整个单位只有一根外线，当有电话打过来的时候，由转接员转到内线电话，已知各部门使用外线电话的频率为（次/天）
5 20 10 12 8 4 3 5 6 9
问应该如何设计个内线电话号码，使得接线员拨号次数尽可能少？
这是哈夫曼树的应用。
一种数据结构，用于保存和处理树状的数据，如家谱。
应用极为广泛，因为根据数据结构的理论，任何复杂的树够可以转换为二叉中并进行处理。
二叉树再排序、查找、大规模数据索引方面有很多很多应用。
二叉树排序是简单算法排序中速度最快的。
树的一个大类是自平衡二叉搜索树 (self-balanced BST), 变种特别多:RB 树是每个节点是红色或者黑色, 颜色隔代遗传AVL 树是每个节点包含平衡因子, 等于左高-右高Splay 树是每个节点带个父节点的指针Treap 是每个节点都带个随机的 priority number, parent priority >= child priority。
自平衡二叉搜索树在面试中经常出现, 但做网页的互联网码农却很少用得上，如果是当 Map 用, 往往还不如直接上哈希表. 如果是当排序用, 不如直接用排序算法... 不过也有有用的时候, 例如查找一个数字的上下界。
树的另一个大类是 Trie, 特点是能保证字典序, 存储词典的空间压缩率高, 能做前缀搜索. 在正则匹配, 数据压缩, 构建索引都可能用到. Trie 也有不少变种:Double Array - trie 的一个经典实现。
每个节点可以存一段字符串而不限于一个字符Judy Array - 基于 256-ary radix tree, 用了 20 种压缩方式, 极其复杂...Burst Trie - 如果一个子树足够小, 就用 binary 堆的方式存储,。
不过压缩效果一般HAT Trie - 压缩率高而且不容易出现 CPU cache miss, 查速接近哈希表而耗内存少得多. 节点可以是以下三种之一: Array Hash, 序列化的 Bucket, 传统 Trie nodeMARISA Trie - 压缩率最高, 支持 mmap 载入, 也是用了很多压缩技巧的复杂实现, 就是构建比较花时间, 也不能动态更新。

二叉树二叉树能够说是人们假想的一个模型，因此，允许有空的二叉树是无争议的。二叉树是有序的，左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定，是因为人们赋予了左孩子和右孩子不同的意义，在二叉树的各种应用中，您将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书，您会发现一个有趣的现象：在二叉树这里，基本操作有计算树高、各种遍历，就是没有插入、删除——那树是怎么建立起来的？其实这很好理解，对于非线性的树结构，插入删除操作不在一定的法则规定下，是毫无意义的。因此，只有在具体的应用中，才会有插入删除操作。节点结构 数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲，或是资源紧张，建议附加一个双亲指针，这将会给很多算法带来方便，尤其是在这个“空间换时间”的时代。

数据结构树和二叉树的实际应用：哈夫曼编码。

利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。

从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。

要求：输出存放哈夫曼树的数组HT的初态和终态；输出每个字符的哈夫曼编码；输入由上述若干字符组成的字符串，对电文进行编码并输出；输入电文的哈夫曼编码，进行译码并输出。

在计算机科学中，树是用来模拟具有树状结构性质的数据集合。它是由n（n>=0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。(n = 0 时称为空树)

特点有：每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。

二叉树的性质：

二叉树的第ii层至多拥有2i−12i−1个节点数, ii>=1)；

深度为 kk的二叉树至多总共有 2k−12k−1 个节点数,(kk>=1)；

对任何一棵非空的二叉树TT，如果其叶片(终端节点)数为 n0n0，分支度为22的节点数为 n2n2，则 n0=n2+1。

扩展资料：

树状图由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；

单个结点是一棵树，树根就是该结点本身。

设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称T1,T2,..,Tk为结点n的子树。

空集合也是树，称为空树。空树中没有结点。

参考资料：百度百科-树 （数据结构名词）

一个单位有10个部门，每个部门都有一部电话，但是整个单位只有一根外线，当有电话打过来的时候，由转接员转到内线电话，已知各部门使用外线电话的频率为（次/天）
5 20 10 12 8 4 3 5 6 9
问应该如何设计个内线电话号码，使得接线员拨号次数尽可能少？

这是哈夫曼树的应用

---

海林市19321359460： 数据结构中,怎么样才能学好二叉树,? 与实际编程中有什么用? - ？
偶典沙棘： 一种数据结构,用于保存和处理树状的数据,如家谱百 应用极为广泛,因为根据数据结构的理论,任何复杂的树够可以转换为二叉中并进行处理 二叉树再排序、查找、大规模数据索度引方面有很多很多应用 二叉树排序是简单算法排序中速度最快的 比如显示一个树结构.在一个树里找指定的结点.写游戏的时候,我把场景放到节点上,这样出了内一个场景,就切到父节点的场景.这个叫做'入口'技术,通过变换容节点在树中的位置,打开同一个门,就可以到不同的地方.

海林市19321359460： 数据结构与算法中,树一般会应用在哪些方面?为什么 - ？
偶典沙棘： 首先,有一些实际场景中的数据,天然地就是树结构.凡是符合每个对象有一个上级,多个下级的性质,就可以用树建模.比如管理树(老板和员工),家族树(父亲和孩子),文件系统树(文件夹和文件).另外,二叉搜索树(BST)可以比较高效地对数据进行排序.如果需要维护动态增减且要保持顺序的一组数据,就可以用BST.

海林市19321359460： 数据结构树和二叉树的实际应用 - ？
偶典沙棘： 一个单位有10个部门,每个部门都有一部电话,但是整个单位只有一根外线,当有电话打过来的时候,由转接员转到内线电话,已知各部门使用外线电话的频率为(次/天)5 20 10 12 8 4 3 5 6 9 问应该如何设计个内线电话号码,使得接线员拨号次数尽可能少?这是哈夫曼树的应用

海林市19321359460： 二叉树在计算机科学与技术中的应用有哪些 - ？
偶典沙棘： 霍夫曼编码:这是一种数据压缩方法,利用一棵霍夫曼树(本质为二叉树)来压缩一组数据.优先级队列:它使用一棵二叉树来记录集合中元素的优先级,并将其排序,为解决问题提供更好的方案.事件调度:主要使用二叉搜索树,这能够使得查找信息更加高效.数据库系统:主要使用B树,这能够使插入和删除操作更加高效.用户界面:在图形用户界面中,窗口按树形结构组织,如windows系统.文件系统:文件按树形结构组织,如windows系统.人工智能:比如棋类这种逻辑类的游戏,可以把步骤生成决策树.以上如果需要详细了解,可直接百度相关名词.

海林市19321359460： 树和二叉树的建立及应用 - ？
偶典沙棘： 以下是我的数据结构实验的作业:肯定好用,里面还包括了统计树的深度和叶子数!记住每次做完一个遍历还要重新输入你的树哦! #include ＂stdio.h＂ #include ＂string.h＂ #define NULL 0 typedef struct BiTNode{ char data; struct BiTNode *...

海林市19321359460： 二叉树有什么用 - ？
偶典沙棘： 任何树和森林都可以转化成为二叉树,一旦转化成为二叉树就可以利用很多二叉树的性质.树形结构在我们计算机中应用非常广,例如文件系统等等,而单纯的树形结构在计算机中很难实现,所以一般都会用二叉树的形式来实现一般的树.这样一举两得,既容易实现,又可以用二叉树的性质来处理数据.所以阁下看一下你的《数据结构》课本,讲树的内容比较少,主要讲的是二叉树.

海林市19321359460： 什么是二叉树,举一个二叉树的例子 - ？
偶典沙棘： 二叉树 树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样.树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示.树在计算机...

海林市19321359460： 数据结构中树与二叉树的区别在于? - ？
偶典沙棘： 二叉树是树的一种,开可以有三叉树、四叉树、……,以及混合叉树.不过一般只讨论二叉树,这是最典型、最有用的数据结构.

海林市19321359460： 数据结构 二叉树 - ？
偶典沙棘： 先介绍一下树:1.树的定义 树是一种常见的非线性的数据结构.树的递归定义如下: 树是n(n>0)个结点的有限集,这个集合满足以下条件: ⑴有且仅有一个结点没有前件(父亲结点),该结点称为树的根; ⑵除根外,其余的每个结点都有且仅...

海林市19321359460： c++数据结构树的应用 - ？
偶典沙棘： #include<cstdio> #include<stack> using namespace std; template <typename T> class tnode { public: //注意都是公有成员 T nodeValue; tnode<T> *left, *right; tnode() { } tnode(const T& item, tnode<T> *lptr = NULL, tnode<T> *rptr = NULL) :...