锐客网

  1. 首页 > it技术 > >

数据结构与算法—树论

一、什么是数据结构？什么是树？ 1、什么是数据结构：数据在计算中存储的方式。

  • 思考：1000w个单词，让你去找某一个词是否在这1000w中。
假设，机器：1台，2G配置
Hash表，时间复杂度：0(1)，机器的配置能存下？
分布式任务，但这里已经假定。
用什么方式？ => 字典树 （Tire树，中文的变种）

数据结构与算法—树论
文章图片

2、什么是树形结构？ 树形数据结构是一类高级非线性数据结构，其中最重要的就是树和二叉树。其特殊的层次结构扮演了非常重要的地址，其中一些重要的算法和高性能的系统几乎都采用了树形结构。
  • 有一个根节点、一般称为root节点
  • 每一个元素都被称为node
  • 除了root节点外，其余的节点都会被分为n个互不相交的集合
基本术语:
1、树结点：包含一个数据元素和若干个指向子树的分支。
2、孩子结点：节点的子树的根称为该结点的孩子。
3、双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲。
4、兄弟结点：同一双亲节点的孩子结点。
5、堂兄结点：同一层上结点。
6、结点层次：根结点的层次为1，根结点的孩子结点的层次为2，以此类推。
7、树的高（深）度：树中最大的结点层。
8、结点的度：结点子树的个数。
9、树的度：树中最大的结点度。
10、叶子结点：也是终端结点，是度为0的结点。
11、分支结点：度不为0的结点（非终端结点）。
12、森林：互不相交的树集合。
13、有序树：子树有序的树，如：家族树。
14、无序树：不考虑子树的顺序。
二、二叉树和平衡二叉树 什么是二叉树？什么是二叉搜索树？如何实现？
什么是平衡二叉树？什么是B树？
1、二叉树的定义 一种特殊的树形结构，每个节点至多只有两颗子树，通常子树被称为左子树和右子树。
2、二叉树满足的一些性质和概念
1、二叉树不存在度大于2的结点。
2、左右子树是有顺序的，即使某结点只有一颗子树，也要区分它是左子树还是右子树。
3、二叉树具有5种基本形态：空二叉树、只有一个根节点、只有左子树、只有右子树、左右子树都有。
4、二叉树的第n层上至多右2^(n-1)个结点。
5、深度为m的二叉树至多右2^m - 1个结点，此时为满二叉树。
6、这个推导：设结点数为n,可以知道为n-1。于是有两个公式：n-1 = n1 + 2 * n2 和 n = n0 + n1 +n2，联合解出：n0=n2+1.
7、具有n个结点的完全二叉树的深度为log2n 向下取整然后加1 => 通过满二叉树2^n -1 可以推出。
8、对于完全二叉树，在有左右子结点的情况下，设根节点的编号是n(这个编号从1开始），则左结点的编号为2n，右节点的编号是2n+1。
3、特殊的二叉树
  • 斜树：所有的结点都只有左子树或右子树，特点是结点的个数与二叉树的深度相同。
  • 满二叉树：所有的分支结点（非叶子）都存在左子树和右子树，并且所有的叶子都在同一层（完全对称，非叶子结点的度一定是2，结点数2^n -1 ）
  • 完全二叉树：允许在满二叉树中去掉若干个最后的结点，但是存在的结点序号一定与满二叉树的位置一致（比满二叉树要求低一点，所以满二叉树一定是完全二叉树，反之则不成立。如果某结点的度为1，则该结点只有左结点）。
4、二叉树的遍历 由于（链表结构的）二叉树没有明确的“次序”一说（不存在唯一的前驱和后继关系），所以只要是按照某种次序依次访问二叉树中所有结点，使得每个结点被访问且仅被访问一次就是二叉树遍历。

  • 前序遍历：先访问根结点，然后前序遍历左子树，再前序遍历右子树。=> 注意到这里是一个递归过程，后面的遍历方法采用的也是这个思想，另外，这个“序”针对的是对根结点的访问时机。
  • 中序遍历：先中序遍历根结点的左子树，然后访问根结点，再中序遍历右子树。
  • 后序遍历：先后序遍历根结点的左子树，然后后序遍历右子树，再访问根结点。
  • 层序遍历：从上到下从左到右对结点逐个访问。
    以上的遍历方法都是把树中的结点变成某种意义的线性序列，给程序的实现带来好处。以下例子：
    数据结构与算法—树论
    文章图片
    案例分析
  • 前序遍历（根结点、左结点、右节点）=>
  • 中序遍历（左结点、根结点、右节点）=>
  • 后序遍历（左结点、右节点、根结点）=>
  • 层次遍历（从上到下、从左到右）=>
中序遍历示例：
package com.nuih.algorithm; /** * @version: V1.0 * @author: hejianhui * @className: NodeTreeSearch * @packageName: com.nuih.algorithm * @description: 二叉树遍历 * @data: 2018-12-02 23:46 **/ public class NodeTreeSearch {private int data; private NodeTreeSearch leftNode; private NodeTreeSearch rightNode; public NodeTreeSearch() { }public NodeTreeSearch(int data) { this.data = https://www.it610.com/article/data; this.leftNode = null; this.rightNode = null; }/** * 插入数据 * @param root 结点 * @param data 数据 */ public void insert(NodeTreeSearch root ,int data){if(data < root.data){ // 插入左边 // 判断左结点是否存在，不存在new一个 if(root.leftNode == null){ root.leftNode = new NodeTreeSearch(data); }else{ // 存在则直接插入 insert(root.leftNode,data); }}else if(data> root.data){ // 插入右边 if(root.rightNode == null){ root.rightNode = new NodeTreeSearch(data); }else{ // 存在则直接插入 insert(root.rightNode,data); } }else { return; } }/** * 中序遍历：左结点、根结点、右结点 * @param root */ public static void inOrder(NodeTreeSearch root){ if( null != root){ inOrder(root.leftNode); System.out.println(root.data + " "); inOrder(root.rightNode); } }public static void main(String[] args){ int data[] = {3,14,7,1,8,27}; NodeTreeSearch nodeTreeSearch = new NodeTreeSearch(data[0]); for (int i = 0; i

结果如下：

数据结构与算法—树论
文章图片
输出 三、总结 【数据结构与算法—树论】数据结构对程序员的重要性

    推荐阅读


    上一篇：打造睡眠经济，蜗牛睡眠的三驾马车与三大困扰

    下一篇：人从众叕的华南宠物展圆满收官，Cheer|人从众叕的华南宠物展圆满收官，Cheer Share畅享优品又双叒叕引爆全场！