frank

数据结构-树
1 背景小明和小红栽了一棵树,这棵树从根发出2个枝干,又从枝干发出4根枝条,枝条又发出八个枝条......这,就是...
扫描右侧二维码阅读全文
14
2018/07

数据结构-树

1 背景

小明和小红栽了一棵树,这棵树从根发出2个枝干,又从枝干发出4根枝条,枝条又发出八个枝条......这,就是树。🤣🤣🤣

2 树的基本概念

咱们先说一说树。树是一种非线性的数据结构,用他能很好地描述有分支和层次特性的数据集合。用通俗易懂的话说,就是有一个点不断向外发散出更多的点就是树!🌳🌳🌳

一棵树是由n(n>0)个元素组成的有限集合,其中:
(1)每个元素成为结点(node);
(2)有一个特定的节点,成为根节点或树根(root);
(3)除根节点为其余节点能分成m(m>=0)个互不相交的有限集合 T0、T1、T2、T3 ······ Tm-1。其中的每个子集又都是一个二叉树,这些集合称为这棵树的子树。

一个节点的子树个数称为这个节点的度,度为0的节点称为叶节点,即一棵树的末端

3 树的存储结构

3.1 存储结构

知道了树,如何用变量去实现树的存储。

方法一:数组,被称为“父亲表达法”

const int m=10; //树的节点数
struct node
{
    int data, parent; //数据域,指针域
};
node tree[m];

优缺点:利用树中除根节点外,其它节点均有唯一的父亲的性质,很容易递归到根,但找孩子需要遍历整个线性表。

方法二:树性单链表结构,称为”孩子表示法“

const int m=10; //树的度
typedef struct node;
typedef node * tree;
struct node
{
    char data; //数据域
    tree child[m]; //指针域,指向它的m个孩子
};
tree t;

缺陷:只能从父节点遍历到子节点,不能从子节点返回父节点。😱😱😱

当的确需要返回父节点时,就需要在节点中多开一个指针域指向它的父节点。这种结构又叫带逆序的数据结构。

方法三:树型双链表结构,称为”父亲孩子表示法“。

const int m=10; //树的度
typedef struct node;
typedef node * tree;
struct node
{
    char data; //数据域
    tree child[m]; //指针域,指向m个孩子节点
    tree father; //指针域,指向父亲节点
};
tree t;

这种表示方法弥补了方法三的缺陷,需要遍历父亲又要遍历孩子时,首推这种方法,易懂简洁👍👍👍

方法四:二叉树型表示法,称为”孩子兄弟表示法“。

typedef struct node;
typedef node * tree;
struct node
{
    char data; //数据域
    tree firstchild,next; //指针域,分别指向第一个孩子节点和下一个兄弟节点
};
tree t;

3.2 例题:找树根和孩子

题目

大家可以前往此网址做题,网站专门为此博客服务,尽情提交哦!

分析与思路:

用tree数组记录父节点,tree[i]表示第i个节点的父亲。当tree[i]=0时,这个点没有父亲,则必然是根节点(root)。找孩子最多时开两重循环,i表示选择的父节点,j循环tree数组找父亲为i的有几个,如果大于max就记录数量和i。

难度:入门 / 普及-

题解:

为了创建良好的社区环境,请在提交自己的程序并在本页回复后方可查看题解。

<hide>

#include<iostream>
using namespace std;
int n,m,tree[101]={0};
int main()
{
    int i,x,y,root,maxroot,sum=0,j,Max=0;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        tree[y]=x;
    }
    for(i=1;i<=n;i++)                     //找出树根 
        if(tree[i]==0)
        {
            root=i;
            break;
        }
    for(i=1;i<=n;i++)                     //找孩子最多的结点
    {
        sum=0; 
        for(j=1;j<=n;j++)
            if(tree[j]==i) sum++;
        if(sum>Max)
        {
            Max=sum;
            maxroot=i;
        }
    }
    cout<<root<<endl<<maxroot<<endl;
    for(i=1;i<=n;i++)
        if(tree[i]==maxroot) cout<<i<<" ";
    return 0; 
}

</hide>

4 树的遍历

4.1 遍历

                        1
                      / | \
                     /  |  \
                    2   3   4
                   / \      |
                  /   \     7
                 5     6   / \
                          /   \
                         8     9

在应用树结构解决问题时,往往要求按照某种次序获得树中全部结点的信息,这种操作叫作树的遍历。遍历的方法有多种,常用的有:

  1. 先序(根)遍历:先访问根结点,再从左到右按照先序思想遍历各棵子树。如上图先序遍历的结果为:125634789;
  2. 后序(根)遍历:先从左到右遍历各棵子树,再访问根结点。如上图后序遍历的结果为:562389741;
  3. 层次遍历:按层次从小到大逐个访问,同一层次按照从左到右的次序。如上图层次遍历的结果为:123456789;
  4. 叶结点遍历:有时把所有的数据信息都存放在叶结点中,而其余结点都是用来表示数据之间的某种分支或层次关系,这种情况就 用这种方法。如上图按照这个思想访问的结果为:56389;

大家可以看出,AB两种方法的定义是递归的,所以在程序实现时往往也是采用递归的思想。既通常所说的“深度优先搜索dfs”。如用先序遍历编写的过程如下:

void tral(tree t, int m)
{
    if (t)
    {
        cout << t->data << endl;
        for(int i = 0 ; i < m ; i++)
            tral(t->child[i], m);
    }
}

C方法应用也较多,实际上是我们讲的“广度优先搜索bfs”。思想如下:若某个结点被访问,则该结点的子结点应标记,等待被访问。顺序访问各层次上结点,直至不再有未访问过的结点。所以,可以使用一个队列来存储等待访问的子结点,设一个队首和队尾指针分别表示出队、进队的下标。程序框架如下:

const int n =100;
int head, tail, i;
tree q[n];
tree p;
void work()
{
    tail = head = 1;
   q[tail] = t;
    tail++;               //队尾为空
    while(head < tail)
    {
        p = q[head];
        head++;
          cout << p->data << ' ';
          for(i = 0 ; i <m ; i++)
          if(p->child[i])
          {
            q[tail] = p->child[i];
            tail++;
          }
    }
}

4.2 例题:单词查找树

题目

分析与思路:

首先要对建树的过程有一个了解。对于当前被处理的单词和当前树:在根结点的子结点中找单词的第一位字母,若存在则进而在该结点的子结点中寻找第二位……如此下去直到单词结束,即不需要在该树中添加结点;或单词的第n位不能被找到,即将单词的第n位及其后的字母依次加入单词查找树中去。但,本问题只是问你结点总数,而非建树方案,且有32K文件,所以应该考虑能不能不通过建树就直接算出结点数?为了说明问题的本质,我们给出一个定义:一个单词相对于另一个单词的差:设单词1的长度为L,且与单词2从第N位开始不一致,则说单词1相对于单词2的差为L-N+1,这是描述单词相似程度的量。可见,将一个单词加入单词树的时候,须加入的结点数等于该单词树中已有单词的差的最小值。

单词的字典顺序排列后的序列则具有类似的特性,即在一个字典顺序序列中,第m个单词相对于第m-1个单词的差必定是它对于前m-1个单词的差中最小的。于是,得出建树的等效算法:

  1. 读入文件;
  2. 对单词列表进行字典顺序排序;
  3. 依次计算每个单词对前一单词的差,并把差累加起来。注意:第一个单词相对于“空”的差为该单词的长度;
  4. 累加和再加上1(根结点),输出结果。

先确定32KiB(32*1024=32768字节)的文件最多有多少单词和字母。当然应该尽可能地存放较短的单词。因为单词不重复,所以长度为1的单词(单个字母)最多26个;长度为2的单词最多为26*26=676个;因为每个单词后都要一个换行符(换行符在计算机中占2个字节),所以总共已经占用的空间为:(1+2)*26+(2+2)*676=2782字节;剩余字节(32768-2782=29986字节)分配给长度为3的单词(长度为3的单词最多有26*26*26=17576个)有29986/(3+2)≈5997。所以单词数量最多为26+676+5997=6699

定义一个数组:string a[32768];把所有单词连续存放起来,用选择排序或快排对单词进行排序。

难度:普及

题解:

为了创建良好的社区环境,请在提交自己的程序并在本页回复后方可查看题解。

<hide>

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

string a[32768];
int n=0;

bool bj(char a,char b)
{
    if /*(strcmp(a,b)==0)*/(a==b) return true;
    return false;
}

int main()
{
    do
    {
        n++;
        getline(cin,a[n]);
    }
    while (a[n].size()!=0);
    n--;
    
    for (int i=1; i<=n-1; i++)
     for (int j=i+1; j<=n; j++)
      if (a[i]>a[j]) swap(a[i],a[j]);

    int t=a[1].size();
    for (int i=2; i<=n; i++)
    {
        int j=0; 
        while (bj(a[i][j],a[i-1][j])&&j<=a[i-1].size()) j++;
        t=t+a[i].size()-j;
    }
    cout<<t+1;
}

</hide>

5 小结

至此,你已经对树有了大概的了解,已经可以掌握最基本的树,恭喜!

在下一章中,我们将会介绍什么是二叉树?以及树的计数问题。在看完下一篇文章后,普及难度的树你基本上就已经全部掌握了。

Last modification:July 28th, 2018 at 11:31 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment