基本数据结构

一.图
二.树

一.图

1.图的遍历：

通过深度优先遍历DFS和广度优先遍历BFS两种方式。
深度优先遍历
0 1 2 3 4 5 6 7 8

1.png

/*图深度遍历*/
-(void)graph_DFS
{
    int point[9]={0,1,2,3,4,5,6,7,8};
    int path[9][9]={
        {0,1,MaxPath,MaxPath,MaxPath,1,MaxPath,MaxPath,MaxPath},
        {1,0,1,MaxPath,MaxPath,MaxPath,1,MaxPath,1},
        {MaxPath,1,0,1,MaxPath,MaxPath,MaxPath,MaxPath,1},
        {MaxPath,MaxPath,1,0,1,MaxPath,1,1,1},
        {MaxPath,MaxPath,MaxPath,1,0,1,MaxPath,1,MaxPath},
        {1,MaxPath,MaxPath,MaxPath,1,0,1,MaxPath,MaxPath},
        {MaxPath,1,MaxPath,1,MaxPath,1,0,1,MaxPath},
        {MaxPath,MaxPath,MaxPath,1,1,MaxPath,1,0,MaxPath},
        {MaxPath,1,1,1,MaxPath,MaxPath,MaxPath,MaxPath,0},
    };
    
    BOOL visited[9]={FALSE};
    visited[0]=TRUE;
    printf("%d ",point[0]);
    [self dfs:point andPath:path andvisited:visited andIndex:0];
    
}
/*
 用visited[]记录找过的点；从开始节点，不断向一边找，直到访问到记录过的点，那么回退到上个节点继续。
 类似树的中序遍历
 */
-(void)dfs:(int[])point andPath:(int[9][9])path andvisited:(BOOL[])visited andIndex:(int)index
{
    for(int i=0;i<9;i++)
    {
        if(path[index][i]==1&&!visited[i])
        {
            visited[i]=TRUE;
            printf("%d ",point[i]);
            [self dfs:point andPath:path andvisited:visited andIndex:i];
        }
    }
}

广度优先遍历
0 1 5 2 6 8 4 3 7

2.png

/*
 图广度遍历
 借助一个队列保存访问过的节点，类似树的层序遍历
 */
-(void)graph_BFS
{
    int point[9]={0,1,2,3,4,5,6,7,8};
    int path[9][9]={
        {0,1,MaxPath,MaxPath,MaxPath,1,MaxPath,MaxPath,MaxPath},
        {1,0,1,MaxPath,MaxPath,MaxPath,1,MaxPath,1},
        {MaxPath,1,0,1,MaxPath,MaxPath,MaxPath,MaxPath,1},
        {MaxPath,MaxPath,1,0,1,MaxPath,1,1,1},
        {MaxPath,MaxPath,MaxPath,1,0,1,MaxPath,1,MaxPath},
        {1,MaxPath,MaxPath,MaxPath,1,0,1,MaxPath,MaxPath},
        {MaxPath,1,MaxPath,1,MaxPath,1,0,1,MaxPath},
        {MaxPath,MaxPath,MaxPath,1,1,MaxPath,1,0,MaxPath},
        {MaxPath,1,1,1,MaxPath,MaxPath,MaxPath,MaxPath,0},
    };
    BOOL visited[9]={FALSE};
    NSMutableArray * queue=[NSMutableArray array];
    for (int i=0;i<9;i++) {
        if(!visited[i])
        {
            visited[i]=TRUE;
            [queue addObject:[NSNumber numberWithInt:i]];
            while(queue.count>0)
            {
                int index=[queue.firstObject intValue];
                printf("%d ",point[index]);
                for (int j=0;j<9;j++) {
                    if(path[index][j]==1&&!visited[j])
                    {
                        visited[j]=TRUE;
                        [queue addObject:[NSNumber numberWithInt:j]];
                    }
                }
                [queue removeObjectAtIndex:0];
            }
        }
    }
}

二.树

1.特殊的二叉树结构

• 斜树
  所有节点都只有左子树或者右子树叫做斜树。对于二叉查找树的优化二叉平衡树，就是为了防止斜树的出现而影响查找效率。

  
  1.png

• 满二叉树
  所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上。

  
  2.png

• 完全二叉树
  对一颗具有n个节点的二叉树按层序编号，如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同。

  
  3.png

2.二叉树的性质

• 二叉树的第i层上至多有2^(i-1)个节点
  1层 1个
  2层 2个
  3层 4个
  4层 8个...
• 深度为k的二叉树至多有2^k-1个节点
  1层 1个
  2层 1+2=3个
  3层 1+2+4=7个
  4层 1+2+4+8=15个...
• 对任意一颗二叉树，n0=n2+1(其中n0表示度为0的叶子节点，n2表示度为2的叶子节点)
  如上这颗完全二叉树，m表示右侧缺省的叶子，k表示深度。
  n2=2^k-1-2(k-1)-m n0=2^(k-1)-m n0-n2=1->n0=n2+1
• n个节点的完全二叉树深度log2n+1
• 二叉树序列按照层序排列，第i个节点的左孩子是2i,右孩子是2i+1;双亲是i/2。
  该性质在堆排序中有应用，如果是一颗完全二叉树，使用顺序表存储节点元素也不会造成空间浪费。

3.二叉树的遍历

-(TreeNode*)buildTree
{
    TreeNode * node1=[[TreeNode alloc]initWithData:37 andLeft:nil andRight:nil];
    TreeNode * node2=[[TreeNode alloc]initWithData:35 andLeft:nil andRight:node1];
    TreeNode * node3=[[TreeNode alloc]initWithData:51 andLeft:nil andRight:nil];
    TreeNode * node4=[[TreeNode alloc]initWithData:47 andLeft:node2 andRight:node3];
    TreeNode * node5=[[TreeNode alloc]initWithData:58 andLeft:node4 andRight:nil];
    TreeNode * node6=[[TreeNode alloc]initWithData:93 andLeft:nil andRight:nil];
    TreeNode * node7=[[TreeNode alloc]initWithData:99 andLeft:node6 andRight:nil];
    TreeNode * node8=[[TreeNode alloc]initWithData:73 andLeft:nil andRight:nil];
    TreeNode * node9=[[TreeNode alloc]initWithData:88 andLeft:node8 andRight:node7];
    TreeNode * tree=[[TreeNode alloc]initWithData:62 andLeft:node5 andRight:node9];
    return tree;
}

• 前序遍历
  如果二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。

/*二叉查找树前序遍历*/
-(void)traverseTree:(TreeNode*)tree
{
    if(tree==nil)
        return;
    printf("%d ",tree.data);
    [self traverseTree:tree.leftNode];
    [self traverseTree:tree.rightNode];
}

• 中序遍历
  如果二叉树为空，则空操作返回，否则从根节点开始(注意并不是先访问根节点)，中序遍历左子树，然后访问根节点，最后中序遍历右子树。

/*二叉查找树中序遍历*/
-(void)traverseTree:(TreeNode*)tree
{
    if(tree==nil)
        return;
    [self traverseTree:tree.leftNode];
    printf("%d ",tree.data);
    [self traverseTree:tree.rightNode];
}

二叉查找树的中序遍历就是让数据顺序排列的过程。

• 后序遍历
  如果二叉树为空，则空操作返回，否则左到右先叶子后节点的方式遍历左右子树，最后访问根节点。

/*二叉查找树后序遍历*/
-(void)traverseTree:(TreeNode*)tree
{
    if(tree==nil)
        return;
    [self traverseTree:tree.leftNode];
    [self traverseTree:tree.rightNode];
    printf("%d ",tree.data);
}

• 层序遍历
  从根节点开始，从上到下，从左到右访问每一个节点。

4.线索二叉树

• 变形过程：
  树的每个节点的数据结构都包含一个数据域和一个左孩子和右孩子指针域，那些不包含左右孩子的节点和叶子节点，指针域就是空值，为了有效利用这些空值域，把它按照某种遍历顺序赋值为它的前驱或者后继节点。
• 概念：
  这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树。
• 节点结构：
  lchild：左孩子节点
  ltag：为0时指向该节点的左孩子，为1时指向该节点前驱
  data：数据
  rtag：为0时指向该节点的右孩子，为1时指向该节点后继
  rchild：右孩子节点

5.树转换成二叉树

树：

1.png

步骤1.给兄弟加线：

2.png
步骤2.给除长子外的孩子去线：
3.png

步骤3.层次调整

4.png

6.霍夫曼树和霍夫曼编码

• 预备知识
  树的路径长度就是从树根到每个节点的路径长度之和。

  
  1.png

• 霍夫曼树
  一颗有n个叶子节点的二叉树，每个叶子节点带权wk，每个叶子的路径长度为lk。
  带全路径长度就是每个叶子节点wk*lk之和，带权路径长度最小的二叉树称为霍夫曼树。
  eg:如下一颗树的带权路径，但是该树是不是霍夫曼树呢，我们该如何构建霍夫曼树呢？

  
  2.png

• 霍夫曼树构建过程
  1.根据给定的n个权值{w1,w2...wn}构成n颗二叉树的集合F{T1,T2,..Tn}，其中每颗二叉树Ti中只有一个带权为wi根节点，其左右子树均为空。
  2.在F中选取两颗根节点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根节点的权值为左右子树根节点权值之和。
  3.在F中删除这两棵树，加入新得到的二叉树进入F。
  4.重复2，3步骤，直到F只包含一棵树为止。这棵树就是霍夫曼树。
  第一步：

  
  1.png
  

  第二步：

  
  2.png
  第三步：
  3.png
  第四步：
  4.png

所以这颗树霍夫曼树，最短带权路径是205。

• 霍夫曼编码
  霍夫曼树的一个用途就是霍夫曼编码，作为一种基础的文件压缩方式和数据传输优化方式。
  eg:
  传输"BADCADFEED"给别人，显然可以用二进制字符表示。
  A-000 B-001 C-010 D-011 E-100 F-101
  BADCADFEED-001000011010000011101100100011(30个字符)
  假设6个字母的频率是A:27% B:8% C:15% D:15% E:30% F:5%
  如果使用霍夫曼编码构建规划这些字母，

  
  1.png
  

  A-01 B-1001 C-101 D-00 E-11 F-1000
  BADCADFEED-1001010010101001000111100(25个字符)
  接收方也需要直到这颗霍夫曼树，然后解析出编码所代表的字符。

一般地，设需要编码的字符集为{d1,d2,...dn}，各个字符在电文中出现的次数或频率集合为{w1,w2,...wn}，以d1,d2...dn作为叶子节点，以w1,w2,...wn作为相应叶子节点的权值来构造一颗霍夫曼树。规定霍夫曼树的左分支代表0，右分支代表1，则从根节点到叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，这就是霍夫曼编码。