1 00:00:00,335 --> 00:00:08,202 Hello, everybody , this lecture of data structure 大家好,数据结构 2 00:00:08,202 --> 00:00:13,821 and algorithm is Chapter 6: tree. Today we introduce a chain store structure of tree. 与算法这一讲的内容是第六章:树。今天我们介绍树的链式存储结构。 3 00:00:13,821 --> 00:00:20,239 The first is the child node table , that child node table does, in fact, correspond to the 首先是子结点表,那子结点表,其实就对应与 4 00:00:20,239 --> 00:00:25,564 adjacency table of graph, that is to say , we express the information of nodes , 图的邻接表,也就是说,我们表达结点的信息, 5 00:00:25,564 --> 00:00:29,263 and the information of its contact edge 以及每一个节点,它的触边的信息 6 00:00:29,263 --> 00:00:33,796 In the tree, the table is the information of its child nodes . 在树里面就是表示它的子结点的这些信息。 7 00:00:33,796 --> 00:00:39,889 Then we can use the link of static " left child 还有我们可以用静态的“左孩子 8 00:00:39,889 --> 00:00:54,053 / Right Brothers" to express.Well, if this tree is relatively stable , which means modification are few, after we save it in an array, /右兄弟” 这样的链接的形式表达。如果这个树它是相对比较稳定,也就是修改不多的情况下,我们把它存到一个数组里头以后, 9 00:00:54,053 --> 00:00:57,732 We know that every node is in what position , 我们知道每一个结点,它处在什么位置, 10 00:00:57,732 --> 00:01:01,276 Then I would use such form of index, 那我就用这样的一个下标的形式, 11 00:01:01,276 --> 00:01:08,136 Make a virtual pointer to point to its corresponding "left most 做一个虚的一个指针来指向它相应的"left most 12 00:01:08,136 --> 00:01:24,482 child ", that is, it is its first left child , as well as the first brother at its right.Well, another way to do that is to use a dynamic representation, because we are in the structure of tree, child", 也就是它自己的第一个左子孩子, 还有它的右边的第一个兄弟。还有一个方法,就是用动态的表示方法, 因为我们在树结构里面, 13 00:01:24,482 --> 00:01:35,204 the number of children of each node is not the same .Well, for each node , we can assign 每一个结点它的子孩子的个数是不一样的。我们对于每一个结点,我们可以分配 14 00:01:35,204 --> 00:01:42,023 a different pointer. These methods 不同的这个指针 这一些方法, 15 00:01:42,023 --> 00:02:04,379 are troublesome. That is , the operation is not particularly convenient for us .The most common way to do that , is still the representation of binary chain of dynamic " Left / right brother ".That corresponds with our form of binary chain, we can see that 都是比较麻烦的。也就是,在操作上 我们不是特别的方便。最常用的方法,还是动态的“左子/右兄”的二叉链形式的表示。对应与我们的这种二叉链形式的表示,我们可以看到, 16 00:02:04,379 --> 00:02:07,834 for a node, the most important information is, 对一个结点,它最重要的信息,就是 17 00:02:07,834 --> 00:02:11,237 its first child. 它自己的第一个子孩子。 18 00:02:11,237 --> 00:02:14,830 Therefore, we expressed 因此我们表示出 19 00:02:14,830 --> 00:02:17,232 such an information of pchild. pchild 这样的一个信息。 20 00:02:17,232 --> 00:02:23,660 Then what is its next sibling , we use the psibling to express. 还有就是说,它的下一个兄弟,是什么,把 psibling 表示出来。 21 00:02:23,660 --> 00:02:32,550 After expressing each node in this way, the whole form of the binary chain is built up. 每一个结点都这么表达的话,那整个这个二叉链的形式,就给它建立起来了。 22 00:02:32,550 --> 00:02:37,138 Moreover, it can index the information of the forest completely. 而且,它能够完整的去引申到这个森林的信息。 23 00:02:37,138 --> 00:02:41,032 That in the implementation of it , 那在实现中, 24 00:02:41,032 --> 00:02:46,529 We want to define these two pointers , which is 我们就是要定义这两个指针,也就是 25 00:02:46,529 --> 00:02:50,883 The first left child pointer as well as the right sibling pointer. 第一个左子孩子的指针还有右兄弟的指针。 26 00:02:50,883 --> 00:03:00,606 Then , similar as the form of a binary tree , we will define a operation 然后,类似与我们的二叉树的形式, 我们会定义它的一个 27 00:03:00,606 --> 00:03:05,694 to look for the parent of current node. 寻找当前结点父指针的这么一个运算。 28 00:03:05,694 --> 00:03:11,424 In the binary tree, the way we find the parent of current node. 在二叉树的里面,我们寻找当前结点的父指针。 29 00:03:11,424 --> 00:03:19,819 is relatively simple . Although we are looking down from the root . If we do not keep the parent pointer , then 是比较的简单的。虽然说我们也是要从根往下找。如果我们没有存这个父指针的话, 30 00:03:19,819 --> 00:03:25,029 in the forest inside it , it is relatively more trouble, 那在森林里面,它相对来说是更麻烦一点, 31 00:03:25,029 --> 00:03:31,502 For now, we are using a Breadth-First-Search framework to achieve this parent 那现在,我们用的是一个 宽搜的框架, 来实现这个parent 32 00:03:31,502 --> 00:03:32,631 function . 的 函数。 33 00:03:32,631 --> 00:03:37,307 When achieving this Breadth-First-Search framework 那实现这个宽搜框架的时候 34 00:03:37,307 --> 00:03:40,379 Of course, we also want to use the queue. 当然我们也是要用到队列。 35 00:03:40,379 --> 00:03:49,015 For the root itself, it has no parent pointer. That is, its parent pointer is empty . 对于根结点本身, 它是没有父指针的。也就是说它的父指针就是空。 36 00:03:49,015 --> 00:03:55,810 Therefore if our root node is the current you are looking for its parent, 那,因此,如果我们这个根接点就是当前你要找的这一个current 37 00:03:55,810 --> 00:04:00,726 what we return is an empty parent pointer. 的结点, 那,我们返回的就是一个空的父指针。 38 00:04:00,726 --> 00:04:07,399 Otherwise , let's put the root of the first tree , 否则,我们就把第一个树的根, 39 00:04:07,399 --> 00:04:15,374 and the roots of the rest trees behind into the queue first. 还有后面的这个其它树的根, 先一次放到队列里面, 40 00:04:15,374 --> 00:04:25,148 And then , after the queue pops up the first element, we look at its left child. 然后,我们从队列里面,弹出第一个元素以后, 我们来看,它的左子孩子 41 00:04:25,148 --> 00:04:30,847 Well, we go down to right sibling chain of the left child, 那,我们降到它的这个左子孩子 42 00:04:30,847 --> 00:04:36,720 including the left child itself , 所指向这样一个的整个的右兄弟链,包括左子孩子本身, 43 00:04:36,720 --> 00:04:40,505 Then we determine whether, in this right sibling chain, 那我们判断一下,在这个右兄弟链里面, 44 00:04:40,505 --> 00:04:44,334 there is the current node that we are looking for. 有没有我们要找的那个current 的结点。 45 00:04:44,334 --> 00:04:50,370 If do , before we down to the "LeftMostChild" 如果有,那就是降到这个 “LeftMostChild” 46 00:04:50,370 --> 00:04:54,921 this "upperlevelpointer" that we save 之前, 我们保存的这个 “upperlevelpointer”, 47 00:04:54,921 --> 00:05:01,215 which is node at the level before is, in fact, the parent node we're looking for. 也就是说指向上一层的这个结点, 那,其实就是我们要找的这个父结点。 48 00:05:01,215 --> 00:05:04,307 Otherwise, we just put the whole 否则,我们就是把整个 49 00:05:04,307 --> 00:05:11,707 into the queue. 我们都放到队列里面, 50 00:05:11,707 --> 00:05:16,635 To continue a process of traversing afterwards. 以便后面的继续的一个遍历的过程。 51 00:05:16,635 --> 00:05:20,809 Then we repeat this process until we 那我们重复这个过程,直到我们 52 00:05:20,809 --> 00:05:23,696 Found the current node, 找到了这个的current为止, 53 00:05:23,696 --> 00:05:30,873 Then we will return the information of its respective parent pointer, or the whole queue is finished, 然后我们就返回它相应的这个父指针的信息,或者是说整个队列都处理完了, 54 00:05:30,873 --> 00:05:44,872 we have not found such corresponding parent pointer. Well, maybe this current node is, in fact, not in the whole tree, 我们还没有找到这样的相应的这个父指针,也许你这个current 的这个结点,其实也许 就不在整个这个树里面, 55 00:05:44,872 --> 00:05:45,997 So we can not find its parent pointer. 那么我们找不到它的父指针。 56 00:05:45,997 --> 00:05:50,901 If we want to remove the forest represented by the root 那如果是删除以root 57 00:05:50,901 --> 00:05:53,801 , in fact, the whole forest, 为代表的森林的所有的结点,其实也就是说, 58 00:05:53,801 --> 00:05:57,685 it is actually quite easy. 删除整个森林,那其实是比较方便的。 59 00:05:57,685 --> 00:06:03,640 In other words, we can start from the LeftMostChild of this root 也就是说, 我们可以从这个root 的 LeftMostChild 60 00:06:03,640 --> 00:06:05,179 in fact 的出发,那其实, 61 00:06:05,179 --> 00:06:08,907 we will recursively delete the first subtree. 就是递归地删除第一棵子树。 62 00:06:08,907 --> 00:06:11,514 Except for the root of the first subtree 除了这个第一棵子树的根以外的 63 00:06:11,514 --> 00:06:16,553 we recursively delete 这些它的子森林。然后,我们递归的删除 64 00:06:16,553 --> 00:06:19,686 the remaining other subtrees. 剩余的,其他的这个子树。 65 00:06:19,686 --> 00:06:25,336 Finally , we come to remove the first one of this sub-tree root . 最后,我们再来删除第一棵子树的这一个根结点。 66 00:06:25,336 --> 00:06:28,538 This is very simple. Well, then we 这非常简单。好,那我们 67 00:06:28,538 --> 00:06:35,850 think for some questions: First, this following algorithm , is it able to traverse the forest ? 有几个思考:首先就是,下面的这个算法,它是不是能够遍历森林? 68 00:06:35,850 --> 00:06:43,089 A closer look at the framework of our algorithm : You can see in the end which nodes are visited, 我们仔细观察一下这个算法的框架:你可以看一下,它到底是遍历了那一些的结点, 69 00:06:43,089 --> 00:06:50,109 Is some information missing? Then , we'll look at 是不是漏掉了某一些信息?然后,我们再来看一下刚才说的这一个 70 00:06:50,109 --> 00:06:56,280 the function of deleting a subtree. 删除这个子树的这的这么一个功能。 71 00:06:56,280 --> 00:07:01,340 What we just do is to remove the entire forset represented by the root, 我们刚才是 删除以root为代表的整个森林, 72 00:07:01,340 --> 00:07:04,016 Then it is a relatively simple algorithm. 那它是比较简单的算法。 73 00:07:04,016 --> 00:07:08,262 What if we just want to delete the subtree represented by the subroot 那如果我们只是说删除以subroot 74 00:07:08,262 --> 00:07:12,144 and that the whole forest can not be destructed, 为根的这个子树, 那整个森林不能够被破坏, 75 00:07:12,144 --> 00:07:15,608 Only the information under this subtree is deleted, 只是这个子树底下的这些信息被删掉, 76 00:07:15,608 --> 00:07:21,544 Then we have to pay attention to a number of boundary conditions, ie if sub-tree is not empty, if subroot 那我们就要注意判断一些边界的条件,也就是说子树是不是空啊,subroot 77 00:07:21,544 --> 00:07:29,581 has a parent pointer, after these boundaries are judged, you should really consider when to delete the entire subtree , 它有没有父指针啊, 这些边界判断以后,你就要考虑说在真的这个删除整个子树的时候, 78 00:07:29,581 --> 00:07:34,707 the relation to each other , and their order of linking to be maintained right. 其他的各有关项,它们的链接的顺序是要正确的维护的。 79 00:07:34,707 --> 00:07:36,891 Well, that talk is all. Thank you. 好,这一讲到这儿。谢谢大家。