数据结构(四):树
2019-05-17 00:00:09来源:博客园 阅读 ()
树
概念:树是一些节点的集合,一棵树由称作根(root)的节点 r 以及0个或多个非空的(子)树组成,这些子树中每一棵的根都被来自根 r 的一条有向的边(edge)连接。每一棵子树的根叫做根 r 的儿子(child),r 是每一棵子树的根的父亲(parent)。一棵树是N个 节点和N-1条边的集合,其中一个节点叫做根。每条边都将某个节点连接到它的父亲,而除去根节点外每个节点都有一个父亲。
特性:
- 没有儿子的节点称为树叶(leaf)
- 具有相同父亲的节点为兄弟(sibling)
- 在一棵树中从根到每个节点恰好存在一条路径,这条路径上边的条数称为路径的长
- 从根到任意节点 n 的唯一路径的长称为该节点 n 的深度(depth)
- 任意节点 n 到它的子树中一片树叶的最长路径的长称为节点 n 的高
- 所有树叶的高都是0,一棵树的高等于它的根的高,也等于它的最深的树叶的深度
树的实现:实现一棵树通常的思路是定义一个节点类,每个节点除数据外还要有指向该节点的每一个儿子的指针。但是,由于节点的儿子数变化很大并且事先不知道有多少个儿子,所以在节点类中不能直接定义指向儿子的指针。解决这个问题,可以把指向儿子的指针定义为一个链表,及节点类除数据外,还有一个用于存放该节点所有儿子的链表,即可构造一棵树。
代码:
1 from collections import deque 2 3 class TreeNode(object): 4 def __init__(self, root, f_child=None): 5 self.root = root 6 self.depth = 0 7 self.subtree = deque() 8 self.f_child = f_child 9 if self.f_child: 10 self.subtree.append(self.f_child) 11 12 def insert(self, node): 13 node.depth = self.depth + 1 14 if self.f_child is None: 15 self.f_child = node 16 self.subtree.append(node)
树的应用:树的常见应用之一是UNIX等许多操作系统的目录结构。系统的根目录 / 即为树的根节点,根目录下的所有文件或子目录都可以看作根结点的儿子,而子目录下的文件或目录又可以看作儿子节点的儿子,以此形成了操作系统的整棵目录树。
构造文件目录并分级打印:
1 """ 2 / 3 usr 4 local 5 bin 6 root 7 download 8 a.txt 9 c.txt 10 documents 11 bin 12 config 13 """ 14 # 构造上面的文件系统目录并分级打印 15 Dir = TreeNode('/') 16 usr = TreeNode('usr') 17 root = TreeNode('root') 18 bin = TreeNode('bin') 19 download = TreeNode('download') 20 Dir.insert(usr) 21 Dir.insert(root) 22 Dir.insert(bin) 23 usr.insert(TreeNode('local')) 24 usr.insert(TreeNode('bin')) 25 root.insert(download) 26 root.insert(TreeNode('documents')) 27 bin.insert(TreeNode('config')) 28 download.insert(TreeNode('a.txt')) 29 download.insert(TreeNode('c.txt')) 30 31 def printName(node): 32 for _ in range(node.depth): 33 print('\t', end='') 34 print(node.root) 35 36 def ListDir(node): 37 printName(node) 38 for n in node.subtree: 39 ListDir(n) 40 41 if __name__ == '__main__': 42 ListDir(Dir)
二叉树
概念:每个节点最多有两个儿子的树,称为二叉树。
完满二叉树:如果二叉树的所有节点中,除叶节点外都有两个儿子,这样的二叉树称为完满二叉树
完美二叉树:如果完满二叉树的叶节点都在同一层,这样的二叉树称为完美二叉树
完全二叉树:如果二叉树从根节点到倒数第二层满足完美二叉树,最后一层的叶节点不完全填充,但靠左对齐,这样的二叉树称为完全二叉树
树的遍历:
- 先序遍历:在遍历树节点的过程中,先处理根结点,再递归的处理子树,这种遍历方式称为先序遍历
- 后序遍历:在遍历树节点的过程中,先递归的处理子子树,再处理根结点,这种遍历方式称为后序遍历
- 中序遍历:对于二叉树的遍历,先递归的处理左子树,再处理根结点,最后递归的处理右子树,这种遍历方式称为中序遍历
二叉查找树:二叉树的一个重要应用是其在查找中的使用。假设树中的每个节点的值被用来存储整数数据,且所有数据间不重复(重复的数据较复杂,以后讨论)。为了是二叉树具有便于查找的性质,通常规定每个节点的左子树上的值都比它小,右子树上的值都比它大。
实现:构造一棵二叉查找树,通常要实现以下方法:
- make_empty:清空二叉树
- find:查找某个节点
- find_min:查找值最小的节点
- find_max:查找值最大的节点
- insert:插入节点
- delete:删除节点
插入节点的思路分析:二叉查找树节点的插入是一个沿着树的根节点递归向下查找插入位置的过程,即如果插入节点的值大于根结点,则从根结点的右儿子中查找;如果插入节点的值小于根结点,则从根结点的左儿子中查找。如果要插入的节点在树中已存在,则什么都不做,否则将节点插入到遍历的路径上的最后一个节点上。
删除节点的思路分析:对于树结构来说,删除节点是最复杂的操作。要删除某个树节点,首先要对树进行遍历,找到目标节点。如果目标节点为叶节点(没有孩子),则可直接删除;如果目标节点有孩子,为了维持二叉查找树的结构及特性不变,需要用目标节点的右子树中的最小节点或左子树中的最大节点来替换目标节点。
在实现这些操作的基础上,如果想进一步维持一些节点的属性,如节点的高度和深度,则插入和删除操作复杂度又会增加,因为这两个操作会改变一些树节点高度、深度,每进行一次插入或删除操作,就要重新计算、修正一次节点属性,这往往使操作更加耗时。下面分别分析:
- 插入操作:可能(因为树节点的高度由左、右两个儿子中高度较大的那个决定)会改变根结点到插入节点路径上所有节点的高度;插入后要计算自身的高度和深度
- 删除操作:可能会改变根结点到删除节点路径上所有节点的高度;如果删除的节点不是叶节点,那么从替换节点往下的整棵树上的节点(如果有的话)的深度都减1
代码实现:
1 class TreeNode(object): 2 def __init__(self, data, left=None, right=None): 3 self.data, self.left, self.right = data, left, right 4 self.depth = 0 5 self.height = 0 6 7 8 class SearchTree(object): 9 def __init__(self, value): 10 self.root = TreeNode(value) 11 self.size = 1 12 self.min = self.root 13 self.max = self.root 14 15 def _del_node(self, node): 16 if node.right is not None: 17 self._del_node(node.right) 18 if node.left is not None: 19 self._del_node(node.left) 20 del node 21 22 def make_empty(self): 23 if self.root is not None: 24 self._del_node(self.root) 25 self.root = None 26 self.size = 0 27 self.min = None 28 self.max = None 29 30 def _height(self, node): 31 if node is not None: 32 return node.height 33 else: 34 return 0 35 36 def _maxheight(self, left, right): 37 if left is None: 38 return self._height(right) 39 if right is None: 40 return self._height(left) 41 return left.height if left.height > right.height else right.height 42 43 def _add(self, node, root): 44 if node.data > root.data: 45 if root.right is None: 46 root.right = node 47 node.depth = root.depth + 1 48 else: 49 self._add(node, root.right) 50 if node.data < root.data: 51 if root.left is None: 52 root.left = node 53 node.depth = root.depth + 1 54 else: 55 self._add(node, root.left) 56 root.height = self._maxheight(root.left, root.right) + 1 57 58 def _search(self, value, node): 59 if node is None: 60 return None 61 else: 62 if value > node.data: 63 return self._search(value, node.right) 64 if value < node.data: 65 return self._search(value, node.left) 66 else: 67 return node 68 69 def _search_parent(self, value, node): 70 if value < node.data and node.left is not None: 71 if value == node.left.data: 72 return node 73 else: 74 return self._search_parent(value, node.left) 75 if value > node.data and node.right is not None: 76 if value == node.right.data: 77 return node 78 else: 79 return self._search_parent(value, node.right) 80 return None 81 82 def insert(self, value): 83 if self.size == 0: 84 self.__init__(value) 85 else: 86 node = TreeNode(value) 87 self._add(node, self.root) 88 self.size += 1 89 if value > self.max.data: 90 self.max = node 91 if value < self.min.data: 92 self.min = node 93 94 def _find_max(self, node): 95 if node.right is None: 96 return node 97 else: 98 return self._find_max(node.right) 99 100 def _find_min(self, node): 101 if node.left is None: 102 return node 103 else: 104 return self._find_min(node.left) 105 106 def find(self, value): 107 return self._search(value, self.root) 108 109 def find_max(self): 110 if self.size > 0: 111 return self._find_max(self.root) 112 return None 113 114 def find_min(self): 115 if self.size > 0: 116 return self._find_min(self.root) 117 return None 118 119 def _decrease_depth(self, node): 120 node.depth -= 1 121 if node.right is not None: 122 self._decrease_depth(node.right) 123 if node.left is not None: 124 self._decrease_depth(node.left) 125 126 def _update_path_height(self, start_node, end_node): 127 if end_node.data > start_node.data: 128 self._update_path_height(start_node.right, end_node) 129 start_node.height = self._maxheight(start_node.left, start_node.right) + 1 130 if end_node.data < start_node.data: 131 self._update_path_height(start_node.left, end_node) 132 start_node.height = self._maxheight(start_node.left, start_node.right) + 1 133 134 def delete(self, value): 135 # 情况一:节点不存在 136 # 情况二:节点存在且有孩子 137 # 情况三:节点存在,没孩子 138 # 删除节点的同时,保证树上每个节点的高度和深度正确: 139 # 两步走:1.顶替节点的所有子节点深度减1; 140 # 2.如果顶替节点的父节点的高度发生变化,则更新从根到父节点路径上所有节点的高度 141 del_node = self._search(value, self.root) 142 if del_node is not None: 143 max_value = self.max.data 144 min_value = self.min.data 145 del_value = del_node.data 146 if del_node.right is not None: 147 replace_node = self._find_min(del_node.right) 148 replace_parent = self._search_parent(replace_node.data, del_node) 149 del_node.data = replace_node.data # 用替换节点覆盖被删除节点的值,相当于删掉了目标节点 150 if replace_node.right is not None: # 如果替换节点有孩子,更新所有孩子节点的深度 151 self._decrease_depth(replace_node.right) 152 # 将替换节点的孩子嫁接到父节点的树上,此时替换节点已从原树中摘除 153 if replace_parent == del_node: 154 replace_parent.right = replace_node.right # 替换节点是其父节点的右儿子 155 else: 156 replace_parent.left = replace_node.right # 替换节点是其父节点的左儿子 157 if replace_parent.height != self._maxheight(replace_parent.left, replace_parent.right) + 1: # 如果替换节点的父节点高度发生了变化,更新从根到父节点路径上所有节点的高度 158 replace_parent.height = self._maxheight(replace_parent.left, replace_parent.right) + 1 159 self._update_path_height(self.root, replace_parent) 160 del replace_node 161 elif del_node.left is not None: 162 replace_node = self._find_max(del_node.left) 163 replace_parent = self._search_parent(replace_node.data, del_node) 164 del_node.data = replace_node.data 165 if replace_node.left is not None: 166 self._decrease_depth(replace_node.left) 167 if replace_parent == del_node: 168 replace_parent.left = replace_node.left 169 else: 170 replace_parent.right = replace_node.left 171 if replace_parent.height != self._maxheight(replace_parent.left, replace_parent.right) + 1: 172 replace_parent.height = self._maxheight(replace_parent.left, replace_parent.right) + 1 173 self._update_path_height(self.root, replace_parent) 174 del replace_node 175 else: 176 del_node.height = -1 # 目标节点没有孩子,其父节点的高度必然-1,为了避免再次搜索其父,直接更新其自身路径上所有节点的高度 177 self._update_path_height(self.root, del_node) 178 del del_node 179 self.size -= 1 180 if del_value == max_value: 181 self.max = self.find_max() 182 if del_value == min_value: 183 self.min = self.find_min()
原文链接:https://www.cnblogs.com/sheshouxin/p/10753967.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:集合-set
下一篇:封装系统内置功能的函数(字符串)
- 进程相关 2019-08-13
- Python 数据结构理解分享 2019-07-24
- Python-17-反射 2019-07-24
- django修改表数据结构后报错的解决办法 2019-07-24
- Python-16-继承、封装、多态 2019-07-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash