数据结构_3

发表于
字数统计 1.1k | 阅读时长 4

学习过程主要依照中国MOOC课程，感谢MOOC，感谢浙大授课大佬。

树与树的表示

什么是树

分层次管理的结构，在管理上有更高的效率。
树：n(n>=0)个结点构成的有限子集。
当n=0时，称为空树；当n>0时，具备以下性质：

  • 树中有一个特殊结点，称为“根root”；
  • 其余结点可分为m个互不相交的有限集，其中每个集合本身又是一棵树，称为原来树的“子树”，子树是不相交的；

以查找为例，查找分为静态查找（集合中记录是固定的，例如查字典）和动态查找（集合中记录是动态变化的）。
静态查找：顺序查找（有哨兵和无哨兵）、二分查找
二分查找判定树：判定树上每个结点需要的查找次数刚好为该结点所在的层数===>n个结点的判定树的深度为[log n]+1

树的表示

儿子兄弟表示法:每一个结点有两个指针域，FirstChild和NextSibling，分别指向第一个儿子和下一个兄弟。

二叉树及存储结构#

二叉树的定义

二叉树T是一个有穷的结点集合，这个集合可以为空；若不为空，则它是由根结点和称为其左子树和右子树的两个不相交的二叉树组成。二叉树的子树有左右顺序之分。
完美二叉树==满二叉树=/=完全二叉树
将满二叉树的结点按照从上到下，从左到右的顺序进行编号，如果此二叉树中所有结点编号和对应的满二叉树相同，则为完全二叉树，也就是满二叉树去掉最后几个结点即完全二叉树。

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. 对任何非空二叉树T，若n0表示叶结点的个数，n2是度为2的非叶节点个数，那么有n0=n2+1。

二叉树的存储结构

顺序存储结构

适用于完全二叉树，用数组进行存储。非根结点（序号i>1）的父结点的序号是[i/2]；结点（序号为i）的左孩子结点的序号为2i，右孩子结点序号为2i+1。一般二叉树也可以采取这种方法，补充成完全二叉树，但是会造成空间浪费。

链表存储结构

适用于一般完全二叉树。三个域，left/data/right。

二叉树的遍历

先序

递归：根结点-先序遍历左子树-先序遍历右子树
堆栈：参照中序

中序

递归：中序遍历左子树-根结点-中序遍历右子树
堆栈：遇到一个结点，就把它压栈，并去遍历它的左子树，当左子树遍历结束后，从栈顶弹出这个结点并访问它，然后按其右指针再去中序遍历该结点的右子树。

后序

递归：后序遍历左子树-后序遍历右子树-根结点
堆栈：参照中序

层次遍历

从结点访问其左右儿子结点。访问左儿子后，右儿子结点需要用堆栈或队列暂时保存不访问的结点。
队列实现：遍历从根节点开始，首先将根节点入列，然后开始执行循环：结点出队、访问该结点、其左右儿子入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void InorderTraversal( BinTree BT )
{
    if( BT ) {
        InorderTraversal( BT->Left );
        /* 此处假设对BT结点的访问就是打印数据 */
        printf("%d ", BT->Data); /* 假设数据为整型 */
        InorderTraversal( BT->Right );
    }
}
 
void PreorderTraversal( BinTree BT )
{
    if( BT ) {
        printf("%d ", BT->Data );
        PreorderTraversal( BT->Left );
        PreorderTraversal( BT->Right );
    }
}
 
void PostorderTraversal( BinTree BT )
{
    if( BT ) {
        PostorderTraversal( BT->Left );
        PostorderTraversal( BT->Right );
        printf("%d ", BT->Data);
    }
}
 
void LevelorderTraversal ( BinTree BT )
{ 
    Queue Q; 
    BinTree T;
 
    if ( !BT ) return; /* 若是空树则直接返回 */
     
    Q = CreatQueue(); /* 创建空队列Q */
    AddQ( Q, BT );
    while ( !IsEmpty(Q) ) {
        T = DeleteQ( Q );
        printf("%d ", T->Data); /* 访问取出队列的结点 */
        if ( T->Left )   AddQ( Q, T->Left );
        if ( T->Right )  AddQ( Q, T->Right );
    }
}

以上。

注：转载文章请注明出处，谢谢~