数据结构学习三树

发表于 更新于

学习数据结构笔记

树

什么是树

树常用来表示客观世界中许多失误存在的层次关系

分层次组织在管理上具有更高的效率

数据管理的基本操作之一：查找

查找

那么如何实现高效率的查找。

查找：根据某个给定关键字K，从集合R中找出关键字与K相同的记录

查找又分为静态查找，和动态查找。

静态查找： 集合中记录是固定的，没有插入和删除操作，只有查找比如字典。

动态查找： 集合中记录是动态变化的，除了查找，还可能发生插入和删除比如数据库。

静态查找

静态查找最普通方式之一：

静态查找，静态查找顾名思义，就是头到尾，遍历循环查找所有值，当数据量一大那么这个查找是相当费时的。

二分查找，二分查找有个前提，前提是元素在数组内必须是有序的，而且是连续的，可以从大到小也可以从小到大，连续排列，那么可以使用二分查找法，进行查找，核心思路是先找到数组中间的值，对比是大于还是小于，那么就可以看忽略一边，重复上面的步骤，就可以快速的查找到了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int BinarySearch(List Tbl, ElementType K) {
    // 在表Tbl中查找关键字为K的元素
    int left, rigth,mid,NoFound=-1;

    left = 1; // 初始左边界
    rigth = Tbl->Length; // 初始右边界
    while(left <= right){
        mid=(left+right)/2; // 计算元素中间值
        if(K < Tbl->Element[mid]){
            right = mid -1; // 调整左边界
        }else if(K > Tbl->Element[mid]){
            left = mid + 1; // 调整右边界
        }else{
            return mid; // 查找成功返回下标
        }
    }
    return NotFound; // 查找失败返回 -1;
}

二分查找大大的降低了算法复杂度

那么为什么这么高效呢。

首先我们对数组进行了有序化，让他按照规律进行排列，使得查找过程中就知道怎么做。

树的定义

树：N （N > 0）个节点构成的有限集合，当 N = 0 时， 称为空树，对于任何一棵非空树，他具备一下性质：

树中有一个称为根的特殊节点，用 R 表示。
其余节点可以分为 m(m > 0)个互不相交的有限集，其中每个集合本身又是一棵树，称为原 C 树的子树

关于树的基本术语：

  1. 节点的度：节点的子树个数

  2. 树的度：树的所有节点中最大的度数

  3. 叶节点：度为 0 的节点

  4. 父节点：有子树的节点是其子树的根节点的父节点

  5. 子节点：若 a 节点是 b 节点的父节点，则称 b 节点是 a 节点的子节点，子节点也称作孩子节点

  6. 兄弟节点：具有同一个父节点的各节点彼此是兄弟节点

  7. 路径和路径长度：从节点 n1 到 nk 的路径为一个节点序列 n1，n2…nk 是 n1 的父节点，路径所包含边的个数为路径的长度。

  8. 祖先节点：沿树根到某一节点路径上多有节点都是这个节点的祖先节点

  9. 子孙节点：某一节点的子树中所有节点是这个节点的子孙

  10. 节点的层次：规定根节点在 1 层，其他任意节点的层数是其父节点的层数+1

  11. 树的深度：树中所有节点中最大层次是这棵树的深度

树的表示

二叉树，每个节点只有两个分支。

1
2
3
4
5
6
7
typedef struct TNode *Position;
typedef Position BinTree; // 二叉树类型
struct TNode{ // 树结点定义
    ElementType Data; // 结点数据
    BinTree Left;     // 指向左子树
    BinTree Right;    // 指向右子树
};

二叉树的定义

二叉树：一个又穷的节点集合，这个集合可以为空，若不为空，则他是由根节点和称为左子树和右子树的两个不相交的二叉树组成

斜二叉树。完美二叉树，满二叉树。都学过书上看过

二叉树的几个重要性质

  1. 一个二叉树第 I 层的最大节点数为：2 的 i 次方-1， i >= 1

  2. 深度为 k 的二叉树有最大节点总数为：2 的 k 次方-1， k >= 1

  3. 对于任何非空二叉树，若 n0 表示叶节点的个数、n2 是度为 2 的非叶节点个数，那么两者满足关系$$n_0 = n_2 +1$$

二叉树的遍历

  1. 先序遍历

遍历过程为：访问根节点，先序遍历其左子树，先序遍历其右子树。

  1. 中序遍历

遍历过程为：中序遍历其左子树，访问跟节点，中序遍历其右子树。

  1. 后序遍历
    遍历过程为：后序遍历其左子树，后序遍历其右子树，访问根节点。