二叉树与哈希表以及基本算法_二叉树和hash表

树和二叉树

1．树的定义

   树(Tree)是n (n≥0)个结点的有限集(记为T)，T为空时称为空树，否则它满足以下两个条件：

  (1) 有且仅有一个结点没有前驱，称该结点为根结点(Root)；

  (2) 除根结点以外，其余结点可分为m(m≥0)个互不相交的有限集合T0，Tl，…，Tm-1。其中每个集合又构成一棵树，树T0，Tl ，…，Tm-1被称为根结点的子树(Subree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。

树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关系，是一种十分重要的非线性的数据结构。

2．树的基本术语

 树的结点包含一个数据元素及若干指向其子树的分支。

1. 树的结点:包含一个DE和指向其子树的所有分支;

2. 结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点;

3. 树的度:树中所有结点的度的最大值 Max(D(I))

    含义:树中最大分支数为树的度;

4. 结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层.

   树中结点的最大层次称为树的深度或高度

5 .有序树、无序树  如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。

6.森林: 是m（m≥0）棵互不相交的树的集合。

7.在树结构中，结点之间的关系又可以用家族关系描述，定义如下：

8.孩子、双亲: 结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。

9.子孙: 以某结点为根的子树中的所有结点都被称为是该结点的子孙。

10.祖先: 从根结点到该结点路径上的所有结点。

11.兄弟: 同一个双亲的孩子之间互为兄弟。

12.堂兄弟: 双亲在同一层的结点互为堂兄弟。

 

1、双亲存储表示法

   一般采用顺序存储结构实现。用一组地址连续的存储单元来存放树的结点，每个结点有两个域：

　　data域-----存放结点的信息；　　

　　parent域-----存放该结点双亲结点的位置

特点：求结点的双亲很容易，但求结点的孩子需要遍历整个向量。

树的遍历

  所谓树的遍历，就是按照某种顺序依次访问树中各个结点，并使得每个结点只被访问一次。也就是把非线性结构的树结点变成线性序列的一种方式 。

    树的遍历可以按深度优先遍历，也可以按照广度优先（按层次）遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。

二叉树的定义与性质

   二叉树(Binary Tree)是另一种重要的树型结构。是度为2的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。

1．二叉树的递归定义

  二叉树(BinaryTree)是n(n≥0)个结点的有限集。它或者是空集(n=0)，或者同时满足以下两个条件：

(1) 有且仅有一个根结点；

(2) 其余的结点分成两棵互不相交的左子树和右子树。

满二叉树(FullBinaryTree) 

深度为k，且有2k-1个结点的二叉树。

   特点：（1）每一层上结点数都达到最大

         （2）度为1的结点n1=0，树叶都在最下一层上。

   结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。

完全二叉树(Complete BinaryTree) 

深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。

特点：

（1）每个结点i的左子树的深度Lhi-其结点i的右子树的深度Rhi等于0或1，即叶结点只可能出现在层次最大或次最大的两层上。

（2）完全二叉树结点数n满足2k-1-1＜n≤2k-1

（3）满二叉树一定是完全二叉树，反之不成立。

遍历二叉树

先序

preorder(BTree *root)         //前序遍历
{ if(root!= NULL)             //如果不是空结点
　{ printf(“%c\n”,root->data); //输出当前结点值
　　preorder(root->lchild);    //递归前序遍历左子结点
　　preorder(root->rchild);    //递归前序遍历右子结点
　}
　return;                      //结束
}

中序

void inorder(BTree *root)       //中序遍历
 
{
    if(root!=NULL)               //如果不是空结点
    { 
        inorder(root->lchild);     //递归中序遍历左子结点
 
        printf(“%c\n”,root->data);  //输出当前结点值
 
        inorder(root->rchild);      //递归中序遍历右子结点
   }
}

后序

void postorder(BTree *root)   //后序遍历
{ 
    if(root!=NULL)                //如果不是空结点
    { 
        postorder(root->lchild);     //递归后序遍历左子结点    
        postorder(root->rchild);     //递归后序遍历右子结点 
        printf(“%c\n”,root->data);   //输出当前结点值
  }
}

算法排序排序

常用的排序算法

• 冒泡排序

• 快速排序

• 直接插入排序

• 希尔排序

• 选择排序

• 堆排序

• 归并排序

以及

桶排序

地精排序

栈

特点:  先进后出， 后进先出

专业术语： 
      栈底：  封闭的一端
      栈顶:   入栈出栈都是从栈顶操作的

PS: 可以通过顺序结构实现栈，也可以通过链式结构实现栈！

队列

特点:  先进先出， 后进后出

队列可以用数组和链表的结构实现，使用链表的结构实现更方便一些。

哈希表

     哈希表又称散列表。

     哈希表存储的基本思想是：以数据表中的每个记录的关键字 k为自变量，通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。在此称该函数H为哈希函数或散列函数。按这种方法建立的表称为哈希表或散列表。

构造好的哈希函数的方法，应能使冲突尽可能地少，因而应具有较好的随机性。这样可使一组关键字的散列地址均匀地分布在整个地址空间。根据关键字的结构和分布的不同，可构造出许多不同的哈希函数。

哈希函数的构造方法

1．直接定址法

    直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。该哈希函数H(k)为：

      H(k)=k+c   (c≥0)

   这种哈希函数计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可使用直接定址法的哈希函数。否则，若关键字分布不连续将造成内存单元的大量浪费。

2．除留余数法

    取关键字k除以哈希表长度m所得余数作为哈希函数地址的方法。即：

      H(k)=k％m   

这是一种较简单、也是较常见的构造方法。这种方法的关键是选择好哈希表的长度m。使得数据集合中的每一个关键字通过该函数转化后映射到哈希表的任意地址上的概率相等。理论研究表明，在m取值为素数（质数）时，冲突可能性相对较少。  

3．平方取中法

       取关键字平方后的中间几位作为哈希函数地址（若超出范围时，可再取模）。

   设有一组关键字ABC，BCD,CDE，DEF，……其对应的机内码如表所示。假定地址空间的大小为1000，编号为0-999。现按平方取中法构造哈希函数，则可取关键字机内码平方后的中间三位作为存储位置。计算过程如下表所示：

4．折叠法

    这种方法适合在关键字的位数较多，而地址区间较小的情况。

    将关键字分隔成位数相同的几部分。然后将这几部分的叠加和作为哈希地址（若超出范围，可再取模）。

5．数值分析法

    若事先知道所有可能的关键字的取值时，可通过对这些关键字进行分析，发现其变化规律，构造出相应的哈希函数。

冲突的解决方法

1.开放定址法

（1）线性探测法

线性探测法是从发生冲突的地址（设为d）开始，依次探查d+l，d+2，…m-1（当达到表尾m-1时，又从0开始探查）等地址，直到找到一个空闲位置来存放冲突处的关键字。

（2）平方探查法

   设发生冲突的地址为d，则平方探查法的探查序列为：d+12，d+22，…直到找到一个空闲位置为止。

2．链地址法

用链地址法解决冲突的方法是：把所有关键字为同义词的记录存储在一个线性链表中，这个链表称为同义词链表。并将这些链表的表头指针放在数组中（下标从0到m-1）。这类似于图中的邻接表和树中孩子链表的结构。