树、二叉树、查找算法总结

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了树、二叉树、查找算法总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3156字，纯文字阅读大概需要5分钟。

内容图文

树、二叉树、查找算法总结

一.树

基本概念：

树是非线性结构，将数据元素组织成层次结构，元素间属于一对多的关系。
数据元素直接的关系：
每个元素都有唯一的前驱，有0个或多个后继，第一个元素没有前驱，称为根节点。
树的逻辑表示法：
树形表示法，括号表示法，文氏图表示法，凹入表示法
基本术语：
森林：是m（m>=0）棵互不相交的树的集合
有向树：有确定的根，树根和子树根之间为有向关系
有序树：子树直接存在确定的次序关系
无序树：子树之间不存在确定的次序关系
树的性质：
1.树中的结点数等于所有结点的度数加一
2.度为m的树中第i层上至少有m^i-1个结点，i>=1
3.高度为h的m次树至多有m^k -1/m-1 个结点

树的遍历：

概念：
树的遍历运算是值按某种方式访问树中每一个结点且每一个结点只被访问一次
遍历方法：
1.先根遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树
2.后根遍历：若树不空，则先依次后根遍历各棵子树，然后访问根节点
3.层次遍历：若树不空，则自上而下自左至右访问树中每个结点

树的存储结构：

1.双亲存储结构：是一种顺序存储结构，用连续空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置。
2.孩子链存储结构：该结构按树的度设计结点的孩子结点指针域个数
3.孩子兄弟链存储结构：每个结点有三个域--数据元素域、该结点第一个孩子结点指针域、该节点的下一个兄弟结点指针域。

二.二叉树

概念：
二叉树是有限的结点集合。（集合可能是空）
五种基本形态：
空，仅根，右子树空，左子树空，左右子树均不空。
四种逻辑图形表示法：
树形表示法、文氏图表示法、凹入表示法、括号表示法。
二叉树的性质：
1.在二叉树的第i层上至多有2^i-1个结点（i>=1）
2.深度为h的二叉树上至多含有2^h-1个结点
3.对任何一棵二叉树，若它含有n0个叶子结点，n2个度为2的结点，则必存在关系式：n0=n2+1.
三个特殊二叉树：
满二叉树：指的是深度为k且含有2^k-1个结点的二叉树
完全二叉树：树中共n个结点，则该n个节点的编号与满二叉树中编号为1-n的节点一一对应
偏二叉树

存储结构：

顺序存储结构：先用空节点补全成为完全二叉树，然后编号。无节点处存储‘#’
存在问题：
对完全二叉树合适，但对一般二叉树，比如单支树，空间浪费大
链式存储结构：定义左右指针域，用于存储左右孩子节点。

遍历：

递归遍历概念：按照一定次序访问树中所有节点，并且每一个节点仅被访问一次的过程。（它是最基本的运算，二叉树中所有其它运算的基础）
三种方式：
1.先序遍历：访问根，先序遍历左子树，先序遍历右子树。
2.中序遍历：中序遍历左子树，访问根，中序遍历右子树。
3.后序遍历：后序遍历左子树，后序遍历右子树，访问根。

线索化：

概念：
分类：中序线索二叉树，前序线索二叉树，后序线索二叉树
意义：
提高查找结点与遍历二叉树的性能
存储结构设计：
在结点的存储结构上增加两个标志位来区分

哈夫曼树：

定义：

三.查找算法总结

采用何种查找方法，取决于：
1.表中使用的数据结构。
2.表中关键字的次序。
3.在查找的同时是否做修改。
动态查找表
静态查找表
平均查找长度：用以衡量一个查找算法效率的优劣，分为成功情况下和不成功情况

线性表查找：

方法：
顺序查找：
从表的一端开始，顺序扫描线性表，依次比较
特点：算法简单、对结构无要求、但效率低
二分查找：
思路：对于一个有序的顺序表，将关键字k与中间结点位置关键字做比较，若成功则完成。
若不等：k小则在左半区查找。k大则在右半区查找
二分查找的最坏性能和平均性能接近。
分块查找：
概念：是以索引方式存储和查找线性表，是顺序查找的一种改进方法
性能：分块查找是介于顺序查找和二分查找之间的查找方法

二叉树查找：

中序遍历得到的序列是一个连续递增的序列

哈希表：

方法：
直接定址法、除留余数法、数字分析法
构造原则：
计算简单，提高速度，分布均匀，尽量减少冲突。
解决方法：

内容总结

以上是互联网集市为您收集整理的树、二叉树、查找算法总结全部内容，希望文章能够帮你解决树、二叉树、查找算法总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---