数据结构非线性结构

树的概念及常用术语

①树的概念

树是一种非线性结构,树是n个节点的有限集合,且满足:

(1)如果n=0,则称为空树,否则,有且仅有一个特定的节点被称为根。

(2)当n>1的时候,其余节点被分成m个互不相交的子集,每个子集又是一颗树,并且称为根的子树。

②树的常用术语

(1)节点:包含一个数据元素及若干指向其子树根的分支;

(2)节点的度:节点拥有的子树个数;

(3)叶子(终端节点):度为0的节点(其实就是最末尾的那一个)

(4)非终端节点:度不为0 的节点

(5)节点的层次:树中根节点的层次为1,根节点子树的层次为2 ,以此类推

(6)树的度:树中所有的节点的度的最大值

(7)树的深度:树中节点层次的最大值

(8)孩子:节点子树的根称为这个节点的孩子;

(9)双亲:节点的直接上层节点称为该节点的双亲;

(10)兄弟:同一双亲的孩子互称为兄弟

(11)堂兄弟:双亲在同一层次上的节点互称为堂兄弟

(12)路径:从某个节点到其子树中另一个节点之间的分支,构成两个节点之间的路径

(13)子孙:以某个节点为根的子树中的所有节点都被称为该节点的子孙;

(14)祖先:从根节点到该节点路径上的所有节点

(15)森林:m(m>=0)颗互不相交的树的集合

(16)有序树和无序树:如果树中每棵子树从左向右的排列拥有一定的顺序,不得互换,则称为有序树,否则称为无序树,在有序树中,最左边的子树的根称为第一个孩子,最右边的子树的根称为最后一个孩子。

二叉树

二叉树是树的另一种树形结构,他与树的区别是:每个节点最多有两棵子树;子树有左右之分。

二叉树的性质:

性质①:在二叉树的第i层上最多有2^(i-1)个节点(i>=1).

性质②:深度为k的二叉树最多有2^(k-1)个节点。

性质③:对任意一个二叉树,如果其终端节点个数为n,度为2 的节点个数为m,则n=m+1.

满二叉树和完全二叉树
满二叉树:一个深度为k且有2^(k-1)个节点的二叉树称为满二叉树。

完全二叉树:如果对一颗深度为k的二叉树节点按照编号规则进行编号,所得顺序与满二叉树相应节点的编号顺序一致,则称这棵树是完全二叉树。

满二叉树一定是完全二叉树,而完全二叉树不一定是满二叉树。,但是完全二叉树的前(k-1)层一定是满二叉树。在完全二叉树中如果一个节点没有做孩子,则他一定没有右孩子。完全二叉树可以在最后一个层次上没有最后几个叶子节点。

二叉树的存储结构及创建
①顺序存储结构

通过增加虚节点,将二叉树转化为完全二叉树。然后进行编号存储。(可能会造成内存浪费)

②链式存储结构
二叉树的节点至少包括三个域:数据域,左孩子指针域,右孩子指针域。如果为了方便查找还可以增加一个双亲指针域。

typedef struct node
{
    int data;                    //数据域      
    struct node *lchild,*rchild;//左指针域和右指针域      
}BTNode;
 
//按前序输入二叉树中节点的值 
//#表示空树,构造二叉链表表示二叉树T 
void CreateBiTree(BTNode * T)
{
    int ch;
    scanf("%c",ch);
    if(ch == '#')
    {
        *T = NULL;
    }
    else
    {
        *T=(BTNode)malloc(sizeof(BTNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)-> data =ch;//生成根节点         
        CreateBiTree(&(*T)->lchild);//构造左子树         
        CreateBiTree(&(*T)->rchild);//构造右子树     
    }
}

查找节点FindNode(*b,x)
找到值为x的结点后返回节点指针,否则返回NULL

用递归算法,采用”根-左子树-右子树”的顺序,查找值为x的节点。

BTNode *FindNode(BTNode *b,ElemType x)  
{      
    BTNode *p;   
    if (b==NULL)      
        return NULL;   
    else if (b->data==x)         
        return b;    
    else     
    {         
        p=FindNode(b->lchild,x);    
        if (p!=NULL)      
            return p;   
        else return FindNode(b->rchild,x);  
    }  
}  

这里使用的是递归,仔细分析即可。

求高度BTNodeDepth(*b)
二叉树的高度的递归模型f()

int BTNodeDepth(BTNode *b)
{    
    int lchilddep,rchilddep;
    if (b==NULL)return(0); //空树的高度为0      else
        
    {
        lchilddep=BTNodeDepth(b->lchild); //求左子树的高度          
        rchilddep=BTNodeDepth(b->rchild); //求右子树的高度          
        return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1));
        
    }
}

二叉树的遍历递归算法
三种遍历

先序遍历:根节点–>左子树–>右子树。

中序遍历:左子树–>根节点–>右子树。

后序遍历:左子树–>右子树–>根节点.

先序遍历算法

void PreOrder(BTNode *b)
{
    if (b!=NULL)
    {
        printf("%c ",b->data);
        PreOrder(b->lchild);
        PreOrder(b->rchild);
    }
}

中序遍历算法

void InOrder(BTNode *b)
{
    if (b!=NULL)
    {
        InOrder(b->lchild);
        printf("%c ",b->data);
        InOrder(b->rchild);
    }
}

后序遍历算法

void PostOrder(BTNode *b)
{
    if (b!=NULL)
    {
        PostOrder(b->lchild);
        PostOrder(b->rchild);
        printf("%c ",b->data);
    }
}

我在大话数据结构这本书中明白了,这几种方式遍历的顺序。下面说一下:

1、先序遍历二叉树顺序:根节点 –> 左子树 –> 右子树,即先访问根节点,然后是左子树,最后是右子树。 上图中二叉树的前序遍历结果为:0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6

2、中序遍历二叉树顺序:左子树 –> 根节点 –> 右子树,即先访问左子树,然后是根节点,最后是右子树。 上图中二叉树的中序遍历结果为:3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6

3、后续遍历二叉树顺序:左子树 –> 右子树 –> 根节点,即先访问左子树,然后是右子树,最后是根节点。 上图中二叉树的后序遍历结果为:3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0

3、树与二叉树的转化
(一)树转化为二叉树

1.加线。在所有兄弟结点之间加一条连线。
2.去线。对树中每个结点,只保留它与第一个孩子结点的连线,删除它与其他孩子结点之间的连线。
3.层次调整。以树的根结点为轴心,将整棵树瞬时间旋转一定的角度。使之结构层次分明。之一第一个孩子是二叉树结点的左孩子,兄弟转换过来的孩子是结点的右孩子。

(二)森林转换为二叉树 森林是由若干棵树组成的,所以完全可以理解为,森林中的每一棵树都是兄弟,可以按照兄弟的处理办法来操作,如下:

1.把每个树转换为二叉树;
2.第一棵树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用连线连接起来。当多有的二叉树连接起来后就得到森林转化的二叉树。
(三)二叉树转换为树 二叉树转换为树是树转换为二叉树的逆过程。

1.加线。若某结点的左孩子结点存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子的结点……哈,反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。
2.去线。删除原二叉树中所有结点与其右孩子结点的连线。
层次调整。使之结构层次分明。
(四)二叉树转换为森林 判断一棵树是否能转换为一棵树还是森林,就看它是否有右结点,若有,就可以转为森林,否则,就是一棵树。

1.从根结点开始,若右孩子存在,则把与右孩子结点的连线删除,再查看分离后的二叉树,若右孩子存在,则连线删除……,直到所有右孩子连线都删除为止,得到分离的二叉树。
2.再将每棵分离后的二叉树转换为树即可。

1 图的定义

​ 图是由顶点的有穷非空集合和顶点之间边的集合组成,通过表示为G(V,E),其中,G标示一个图,V是图G中顶点的集合,E是图G中边的集合。

​ 无边图:若顶点Vi到Vj之间的边没有方向,则称这条边为无项边(Edge),用序偶对(Vi,Vj)标示。

​ 对于下图无向图G1来说,G1=(V1, {E1}),其中顶点集合V1={A,B,C,D};边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}:

​ 有向图:若从顶点Vi到Vj的边是有方向的,则成这条边为有向边,也称为弧(Arc)。用有序对(Vi,Vj)标示,Vi称为弧尾,Vj称为弧头。如果任意两条边之间都是有向的,则称该图为有向图。

​ 有向图G2中,G2=(V2,{E2}),顶点集合(A,B,C,D),弧集合E2={<A,D>,{B,A},<C,A>,<B,C>}.

​ 权(Weight):有些图的边和弧有相关的数,这个数叫做权(Weight)。这些带权的图通常称为网(Network)。

​ 图的定义和术语总结:

无向网的邻接矩阵创建:

#define MAXVEX 100 /*最大顶点数*/ 
#define INFINITY 65535 /*表示∞*/ 
typedef char VertexType;
typedef int EdgeType;
typedef struct  
{
    VertexType vexs[MAXVEX];       /*顶点表*/
    
    EdgeType arc[MAXVEX][MAXVEX];  /*边表,即邻接矩阵*/
    
    int numVertexes, numEdges;
}MGraph;
void CreateMGraph(MGraph *G)
{
    int i, j, k, w;
    printf("输入顶点数和边数:\n");
    
    scanf("%d,%d", &(G->numVertexes), &(G->numEdges));
    for (i = 0; i < G->numVertexes; i++)
        
        scanf(&(G->vexs[i]));   /*输入顶点,建立顶点表*/
    
    for (i = 0; i < G->numVertexes; i++)
        
        for (j = 0; j < G->numVertexes; j++)
            
            G->arc[i][j] = INFINITY;   /*邻接矩阵初始化*/
    
    for (k = 0; k < G->numEdges; k++)  /*输入边信息,建立邻接矩阵*/
        
    {
        printf("输入边(vi,vj)的下标i,下标j,权重w: \n");
        scanf("%d,%d,%d", &i, &j, &w);
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];   /*无向网,i->j和j->i都写入矩阵*/
        
    }
}

对于n个顶点和e条边,时间复杂度是 O(n+n2+e),其中 G->arc 的初始化就耗费了 O(n2) 的时间。

邻接表 邻接矩阵在边数相对点数较少时会对空间造成浪费。所以可以换种存储方式,数组和链表相结合的邻接表。

无向图的邻接表创建:

typedef struct EdgeNode     /*边表结点*/
    
{
    
    int adjvex;                /*邻接点域,顶点对应的下标*/
        EdgeType weight;        /*存储权值,非网图可以不需要*/
        struct EdgeNode *next;  /*链域,就是把某顶点的几个邻接点写成链表*/
}EdgeNode;

typedef struct VertexNode   /*顶点表结点*/
{
    VertexType data;
    EdgeNode *firstedge;    /*边表头指针*/
}VertexNode, AdjList[MAXVEX];

typedef struct  
{
    AdjList adjList;
    int numVertexes, numEdges;
}GraphAdjList;

/*建立无向图的邻接表*/

void CreateALGraph(GraphAdjList *G)
{
    int i, j, k;
    EdgeNode *e;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d", &(G->numVertexes), &(G->numEdges));
    for (i = 0; i < G->numVertexes; i++)   /*建立顶点表*/
        {
        scanf(&(G->adjList[i].data));
        G->adjList[i].firstedge = NULL;    /*边表头初始置空*/
        
    }
    for (k = 0; k < G->numVertexes; k++)   /*建立边表*/
        
    {
        printf("输入边(vi,vj)的顶点序号:\n"); /*无向图,在两个顶点i和j都要加入这条边*/
        
        scanf("%d,%d", &i, &j);
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
    e->adjvex = j;                       /*邻接序号为j,则是顶点i的链表*/
        
        e->next = G->adjList[i].firstedge; /*e的下一个变为头结点指针的指向*/
            G->adjList[i].firstedge = e;       /*头结点指针变成e,则e插入到链表中*/
            e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = i;                       /*邻接序号为i,则是顶点j的链表*/
        
        e->next = G->adjList[j].firstedge; /*e的下一个变为头结点指针的指向*/
            G->adjList[j].firstedge = e;       /*头结点指针变成e,则e插入到链表中*/
        
        }
} 

对于n个顶点e条边的图,时间复杂度是 O(n+e)。

另外,还有一些复杂的具有不同优势的存储方式,比如十字链表,邻接多重表,边集数组等。

图的遍历 深度优先遍历(DFS)

/* 邻接矩阵的深度优先搜索 */

bool visited[MAX];        /*访问标志的数组*/

void DFS(MGraph *G, int i)
{
    int j;
    visited[i] = true;
    printf("%c", G->vexs[i]);
    for (j = 0; j < G->numVertexes; j++)
    {
        if (G->arc[i][j] == 1 && !visited[j])
            DFS(G, j);   /*对访问的邻接顶点递归,深度优先,类似于树的前序遍历*/
        
    }
}
void DFSTraverse(MGraph *G)
{
    int i;
    for (i = 0; i < G->numVertexes; i++)
        visited[i] = false;
    for (i = 0; i < G->numVertexes; i++)
        if (!visited[i])
            DFS(G, i);   /*进入递归*/
    
}
/* 邻接表的深度优先搜索 */

void DFS(GraphAdjList *GL, int i)
{
    visited[i] = true;
    printf("%c", GL->adjList[i].data);
    EdgeNode *p;
    p = GL->adjList[i].firstedge;
    while (p)
    {
        if (!visited[p->adjvex])
            DFS(GL, p->adjvex);
        p = p->next;
    }
}
void DFSTraverse(GraphAdjList *GL)
{
    int i;
    for (i = 0; i < GL->numVertexes; i++)
        visited[i] = false;
    for (i = 0; i < GL->numVertexes; i++)
        if (!visited[i])
            DFS(GL, i);
}

对邻接矩阵而言,访问所有元素的时间复杂度 O(n2);而对邻接表来说,取决于点和边数,时间复杂度是 O(n+e)。

广度优先遍历(BFS)

/* 邻接矩阵的广度优先搜索 */


bool visited[MAX];        /*访问标志的数组*/

void BFSTraverse(MGraph *G)
{
    int i, j;
    Queue Q;
    for (i = 0; i < G->numVertexes; i++)
        visited[i] = false;
    InitQueue(&Q);
    for (i = 0; i < G->numVertexes; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            printf("%c", G->vexs[i]);
            EnQueue(&Q, i);    /*将此顶点进入队列*/
            
            while (!QueueEmpty(Q))
            {
                DeQueue(&Q, &i);
                for (j = 0; j < G->numVertexes; j++);
                {
                    /*其他顶点与i存在边且未访问,广度优先,类似于树的层次遍历*/
                    
                    if (G->arc[i][j] == 1 && !visited[j])
                    {
                        visited[j] = true;
                        printf("%c", G->vexs[j]);
                        EnQueue(&Q, j);  /*该层次上的顶点先进队列*/
                        
                    }
                }
            }
        }
    }
}
/* 邻接表的广度优先搜索 */

void BFSTraverse(GraphAdjList *GL)
{
    int i;
    EdgeNode *p;
    Queue Q;
    for (i = 0; i < GL->numVertexes; i++)
        visited[i] = false;
    InitQueue(&Q);
    for (i = 0; i < GL->numVertexes; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            printf("%c", GL->adjList[i].data);
            EnQueue(&Q, i);    /*将此顶点进入队列*/
            
            while (!QueueEmpty(Q))
            {
                DeQueue(&Q, &i);
                p = GL->adjList[i].firstedge;
                while (p)
                {
                    /*i的边表链表中的未访问的顶点*/
                    
                    if (!visited[p->adjvex])
                    {
                        visited[p->adjvex] = true;
                        printf("%c", GL->adjList[p->adjvex].data);
                        EnQueue(&Q, p->adjvex);  /*该层次上的顶点先进队列*/
                        
                    }
                    p = p->next;
                }
            }
        }
    }
}

图的 BFS 和 DFS 算法在时间复杂度上是一样的,只是对顶点的访问顺序不一样。

Last modification:July 9th, 2019 at 02:11 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment