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

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

1.树的双亲表示法

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

  1. #-*- coding:utf-8 -*-
  2. class Node:
  3.     def  __init__(self,val,parent):
  4.         self.val = val
  5.         self.parent = parent
  6. class tree:
  7.     def __init__(self):
  8.         self._array = []
  9.     def addNode(self,val,parent):
  10.         node = Node(val,parent)
  11.         self._array.append(node)
  12.     def show(self):
  13.         for i,v in enumerate(self._array):
  14.             print('节点下标为 = {} 值为 = {} 父节点下标为{}'.format(i,v.val,v.parent))
  15.     def findparent(self,node):
  16.         return self._array[node.parent]
  17. tree = tree()
  18. tree.addNode('R',-1)
  19. tree.addNode('A',0)
  20. tree.addNode('B',0)
  21. tree.addNode('C',0)
  22. tree.addNode('D',1)
  23. tree.addNode('E',1)
  24. tree.addNode('F',3)
  25. tree.addNode('G',6)
  26. tree.addNode('H',6)
  27. tree.addNode('K',6)
  28. tree.show()
  29. node = Node('K',6)
  30. node_parent = tree.findparent(node)
  31. print('父节点为={}'.format(node_parent.val))

2. 孩子表示法

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

  1. #-*- coding:utf-8 -*-
  2. class Node:
  3.     def  __init__(self,val,children):
  4.         self.val = val
  5.         self.children = children
  6. class childrentree:
  7.     def __init__(self):
  8.         self._array = []
  9.     def addNode(self,val,children):
  10.         node = Node(val,children)
  11.         self._array.append(node)
  12.     def show(self):
  13.         for i,v in enumerate(self._array):
  14.             print('节点下标为 = {} 值为 = {} 孩子节点下标为{}'.format(i,v.val,v.children))
  15.     def findChildren(self,node):
  16.         chilren = [self._array[i].val for i in node.children]
  17.         return chilren
  18. tree = childrentree()
  19. tree.addNode('R',[1,2,3])
  20. tree.addNode('A',[4,5])
  21. tree.addNode('B',[])
  22. tree.addNode('C',[6])
  23. tree.addNode('D',[])
  24. tree.addNode('E',[])
  25. tree.addNode('F',[7,8,9])
  26. tree.addNode('G',[])
  27. tree.addNode('H',[])
  28. tree.addNode('K',[])
  29. tree.show()
  30. node = Node('F',[7,8,9])
  31. node_children = tree.findChildren(node)
  32. print('节点值为={},孩子节点为={}'.format(node.val,node_children))

3.孩子兄弟表示法

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

  1. #-*- coding:utf-8 -*-
  2. class Node:
  3.     def  __init__(self,val,children,brother):
  4.         self.val = val
  5.         self.children = children
  6.         self.brother = brother
  7. class childrenbrotherree:
  8.     def __init__(self):
  9.         self._array = []
  10.     def addNode(self,val,children,brother):
  11.         node = Node(val,children,brother)
  12.         self._array.append(node)
  13.     def show(self):
  14.         for i,v in enumerate(self._array):
  15.             print('节点下标为 = {} 值为 = {} 孩子节点下标为{},兄弟节点下标为{}'.format(i,v.val,v.children,v.brother))
  16.     def findChildren(self,node):
  17.         chilren = [self._array[i].val for i in node.children]
  18.         return chilren
  19.     def findBrother(self,node):
  20.         brother = [self._array[i].val for i in node.brother]
  21.         return brother
  22. tree = childrenbrotherree()
  23. tree.addNode('R',[1],[])
  24. tree.addNode('A',[4],[2])
  25. tree.addNode('B',[],[3])
  26. tree.addNode('C',[6],[])
  27. tree.addNode('D',[],[5])
  28. tree.addNode('E',[],[])
  29. tree.addNode('F',[7],[])
  30. tree.addNode('G',[],[8])
  31. tree.addNode('H',[],[9])
  32. tree.addNode('K',[],[])
  33. tree.show()
  34. node = Node('F',[7],[])
  35. node_children = tree.findChildren(node)
  36. print('节点值为={},孩子节点为={}'.format(node.val,node_children))

4.森林转化为二叉树

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

5.总结

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

6.天赋异禀

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

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

发表评论

表情：
评论列表 （有 0 条评论，348人围观）

还没有评论，来说两句吧...

相关阅读

    相关 数据结构——树——双亲表示法

    数据结构——树——双亲表示法 我们人可能因为种种原因，没有孩子，但无论是谁都不可能是从石头里蹦出来的，孙悟空显然不能算是人，所以是人一定会有父母。树这种结构也不例外，除了

    清疚清疚/ 0 赞/ 564 阅读