常用数据结构之树的双亲_孩子_孩子兄弟表示法

爱被打了一巴掌 2022-12-11 15:13 268阅读 0赞

## 1.树的双亲表示法 ##

前面我们聊得都是二叉树，今天我们来讨论一下如何去表示一棵普通的树。常用的表示方法有三种：双亲表示法、孩子表示法和孩子兄弟表示法。我们首先来聊一下双亲表示法，顾名思义，双亲表示法就是在每一个节点中，存储其父节点的下标。这样就可以将树中各节点的结构关系表示出来，也可以快速的对父节点进行访问。  
如下图所示我们将一棵普通的树，用图二中的列表形式进行存储。  
![在这里插入图片描述][watermark_ty_E6_99_AE_E9_80_9A_E7_9A_84pe_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][20201003164617949.png_pic_center]  
具体的python实现代码，如下所示(个人手写，不喜勿怪)：

#-*- coding:utf-8 -*-
    class Node:
        def  __init__(self,val,parent):
            self.val = val
            self.parent = parent
    class tree:
        def __init__(self):
            self._array = []
        def addNode(self,val,parent):
            node = Node(val,parent)
            self._array.append(node)
        def show(self):
            for i,v in enumerate(self._array):
                print('节点下标为 = {} 值为 = {} 父节点下标为{}'.format(i,v.val,v.parent))
        def findparent(self,node):
            return self._array[node.parent]
    tree = tree()
    tree.addNode('R',-1)
    tree.addNode('A',0)
    tree.addNode('B',0)
    tree.addNode('C',0)
    tree.addNode('D',1)
    tree.addNode('E',1)
    tree.addNode('F',3)
    tree.addNode('G',6)
    tree.addNode('H',6)
    tree.addNode('K',6)
    tree.show()
    node = Node('K',6)
    node_parent = tree.findparent(node)
    print('父节点为={}'.format(node_parent.val))

## 2. 孩子表示法 ##

上面我们了解了一种存储普通树的方法，在每一个节点中添加指向其父节点的指针。下来我们再来聊一下孩子表示法，其思想和双亲表示法非常类似，不过是换做在每一个节点中存储孩子节点的指针信息，如下图所示：一个节点可能会有多个子节点，所以我们使用一个链表来存储子节点的下标。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center]  
具体实现代码如下：

#-*- coding:utf-8 -*-
    class Node:
        def  __init__(self,val,children):
            self.val = val
            self.children = children
    class childrentree:
        def __init__(self):
            self._array = []
        def addNode(self,val,children):
            node = Node(val,children)
            self._array.append(node)
        def show(self):
            for i,v in enumerate(self._array):
                print('节点下标为 = {} 值为 = {} 孩子节点下标为{}'.format(i,v.val,v.children))
        def findChildren(self,node):
            chilren = [self._array[i].val for i in node.children]
            return chilren
    tree = childrentree()
    tree.addNode('R',[1,2,3])
    tree.addNode('A',[4,5])
    tree.addNode('B',[])
    tree.addNode('C',[6])
    tree.addNode('D',[])
    tree.addNode('E',[])
    tree.addNode('F',[7,8,9])
    tree.addNode('G',[])
    tree.addNode('H',[])
    tree.addNode('K',[])
    tree.show()
    node = Node('F',[7,8,9])
    node_children = tree.findChildren(node)
    print('节点值为={},孩子节点为={}'.format(node.val,node_children))

## 3.孩子兄弟表示法 ##

上面聊到的方法都是如何存储一棵普通的树，接下来我们聊聊如何将一棵普通树转换为二叉树的方法。我们使用孩子兄弟表示法，每一个节点中都包含指向孩子节点的指针和指向兄弟节点的指针。我们使孩子节点为该节点的左子节点，兄弟节点为该节点的右子节点。这样就完成了普通树到二叉树的转换。  
具体代码如下：

#-*- coding:utf-8 -*-
    class Node:
        def  __init__(self,val,children,brother):
            self.val = val
            self.children = children
            self.brother = brother
    class childrenbrotherree:
        def __init__(self):
            self._array = []
        def addNode(self,val,children,brother):
            node = Node(val,children,brother)
            self._array.append(node)
        def show(self):
            for i,v in enumerate(self._array):
                print('节点下标为 = {} 值为 = {} 孩子节点下标为{},兄弟节点下标为{}'.format(i,v.val,v.children,v.brother))
        def findChildren(self,node):
            chilren = [self._array[i].val for i in node.children]
            return chilren
        def findBrother(self,node):
            brother = [self._array[i].val for i in node.brother]
            return brother
    tree = childrenbrotherree()
    tree.addNode('R',[1],[])
    tree.addNode('A',[4],[2])
    tree.addNode('B',[],[3])
    tree.addNode('C',[6],[])
    tree.addNode('D',[],[5])
    tree.addNode('E',[],[])
    tree.addNode('F',[7],[])
    tree.addNode('G',[],[8])
    tree.addNode('H',[],[9])
    tree.addNode('K',[],[])
    tree.show()
    node = Node('F',[7],[])
    node_children = tree.findChildren(node)
    print('节点值为={},孩子节点为={}'.format(node.val,node_children))

## 4.森林转化为二叉树 ##

上面我们讨论了如何将一棵普通树转换为二叉树的办法，孩子兄弟表示法。再进一步，如何将多棵不相交的树转换为二叉树呢？这就是接下来要聊的森林转化换为二叉树。其核心的思想是首先使用孩子兄弟表示法将每一棵树转换为二叉树，然后以第一棵树的根节点为整棵树的根节点，其它树的根节点作为第一个树根节点的兄弟节点，然后使用孩子兄弟表示法将整棵树串联起来。具体流程如下所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 1]

## 5.总结 ##

上面我们讨论的是如何去表示一棵普通的树，以及如何将一棵普通的树甚至是森林表示为一棵二叉树。最常用的表示方法是孩子兄弟表示法，在每一个节点中存储孩子节点和兄弟节的下标，孩子节点作为左子节点，兄弟节点作为右子节点，这样将一棵普通的树转换为二叉树。将多棵树转换为二叉树后，对其根节点使用孩子兄弟表示法，就可以将一个森林转换为二叉树。

## 6.天赋异禀 ##

我一直在寻找正确答案，也一直在错过。我问为什么这个世界上会有那么多不可能的事情，我觉得自己已经足够努力，为什么至今还是寂寂无名。有谁甘心的过着朝九晚五的生活，有谁愿意承认这辈子自己都配不上最喜欢的那个人。我想让自己做一些不一样的事情，是因为觉得自己活得太普通了。无关别人的眼神，只是自己厌烦了这种平庸。是潜意识也好，是集体意识也罢，我只是不想再做受某些事物操控的傀儡。我想去做一些事情，不是因为它有助于我的事业，也不是因为它可以使我变得优秀，不是因为我说的出口的任何一种理由。就只是因为没有其他人做过而已。所谓的潇洒、有趣、价值、使命对我来说没有任何的吸引力，因为在历史中也必定能找得到那样的影子。让我着迷的就是那些未定义的，无意义的，从来没有发生过的事情。因为某些新的生命正在被唤醒，某些新的能力正在自我觉醒，因为《天赋异禀》！

最近超火的抖音神曲《Friendships》跟《天赋异禀》北极星小姐姐气质很搭啊，你肯定听过！

[watermark_ty_E6_99_AE_E9_80_9A_E7_9A_84pe_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1e6b0b91da2945048bcb4e5f34c50d5d.png
[20201003164617949.png_pic_center]: /images/20221123/a91cff917f9e4fd5903e575d1695f9c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/6443dfb43aa540429bb8e9059dc30565.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/6716461848ac40cdaff9bd3d38b4d203.png