二叉树的存储结构_二叉树在实际编程中有那些应用

时间:2021年05月10日 00:07:42

大家好。数据结构与算法这一讲继续第五章。二叉书的学习。我们今天的主要内容是二叉树的存储结构。二叉树是一种复杂的非线性结构。那对于这种复杂结构,我们一般来说呢,呃是不太方便完全用顺序的方法来存储它的。啊,我们往往采用动态的链接的方法来存储。因为二叉树呢,它有左,右指结点这样的信息。因此呢,我们特别方便的就是采用二叉链表的形式来存储它。那,当然中间 还有它具体的这个info 的数据域的信息。 现在也有很多人比较喜欢用三叉链的形式来实现。也就是多加一个 parent 指向父指针的这么一个指针域。 那,有这个域,有什么好处呢?那主要的就是我们在往上头找这些先驱的这些结点以及找它的左右兄弟结点的时候, 比二叉链表呢要方便很多。那我们来看这样一个二叉链表的存储结构,那左边是一个二叉树。那右边呢就是对应的二叉链表的这样的一个存储结构。可以看到很多结点里面的指向,啊左孩子右孩子这个指针域都是空的。可以说几乎有一半这样的结点是空结点。那再来看这个三叉链的形式。它的主要的改进呢就是说,我们加了这么一个父指针域,加了父指针域以后呢我们从任何一个结点可以非常方便的追溯到根。那当然这个追溯的路径上头的一些其它的祖先结点以及它们相应的兄弟的这些信息也都能够很方便的访问得到。但是呢,在我们进行岔路删除操作的时候,也需要同时维护这样的父结点的信息。那我们怎么来实现这样一个二叉链的存储结构呢?那其实在我们前面定义的这样一个二叉树结点的Edit T 之上, 那么除了这个info, 那我们主要的就是要加上这样一个left 和 right这样的相应的指针信息。 那在这样的一个二叉链形式实现的数据结构里面,那我们怎么样来寻找父结点呢?我们要注意,因为它没有往上的这样一个父结点指针,因此,我们所有的这种操作呢,都需要从根开始来找到相应的父结点。那我们来看这样的一个递归实现。那首先呢我们是要从这个当前的这个子根开始,因为它是一个递归实现,所以最开始的时候是传入的根。 然后呢,在中间呢是传入到某一个子根。那如果是子根结点它不空的情况下,那我们判断这个子根的左右子孩子是不是你要找的这个结点。那如果是的话呢,这个子根本身它就是我们要寻找的结点的父结点。如果没有找到,那我们就分别下降到这个子根它的左子树,或者是它的右子树。去继续查找。那我们可以观察一下这个框架,它其实就是一个先序遍历的框架。那,这边是对左子树的一个递归操作。然后这第二个语句呢是对右子树的递归。然后,它的对这个结点进行操作处理的重要的这个部分呢,就是在这两个递归之前,那其实就是替代我们前面说的这样的一个递归的深搜遍历里面程序里面的这个wait 的这个位子。那我们刚才已经讨论过了这个算法它是什么框架以及是用什么序来遍历的。那我们再来想一想,这个刚才用的是递归,那我们能不能够用非递归的呢? 另外就是说,这个算法它能不能够用宽搜来实现呢?另外就是说,这个算法它能不能够用宽搜来实现呢?还有,这个算法它其实是一个比较通用的框架。它这个框架它的主要的是要搜找父结点,但是找兄弟结点其实也是用S的框架实现的。那我们现在来看,用非递归的方法来实现。那我们采用的就是非递归的这个框架。因为它是对应的一个前序遍历的这么一个框架,所以我们用的就是非递归的前序框架。那最开始我们把根结点付给在一个临时的指针。然后呢,我们在一个栈里面呢,是存了一个监视哨。然后我们从这个指针开始往下头找。 那如果这个临时指针pointer 它的左右结点 就是我们要找的那个current 那当前的这个 pointer 呢,它就是 current的父结点。 那如果没有找到的话呢,那我们就要想,我下面再继续操作的时候我应该怎么办。那我们要保留这个pointer 它的一个非空的右子结点,因为我们现在呢可以进到它的左子树,因此呢,下面要左子树访问完了以后那再继续要访问它的右子树的时候就可以从栈里面拿了。因此呢,我们就是把它的非空的右结点入到栈里面。然后就下到它的一个非空的左子结点。那如果是说这个左子结点是空的,那我们就是表示左子树呢已经访问完了。我们要从栈里面呢拿出它前面存的那些代访问的某些右结点的信息。然后呢,弹栈再继续刚才的这样一个操作。啊,我们来分析一下二叉链的空间开销。那首先我们注意一下有这么几个概念。啊,存储密度呢,它表达的是存储的效率,实际上也就是说,有效的数据占整个数据它的比例。 结构性开销呢,实际上就是说我为了存这些有效的数据,我还加了哪些辅助的信息来完成这个存储。那辅助的信息呢,它占整个数据结构的一个比例。那对于这样的一个二叉链的结构,那我们根据满二叉树定理,我们可以看到呢就是有一半的这个指针域是空的。那每个结点它要存两个指针域, 一个数据域。假设指针域和数据域是相等的话呢,那这个结构性的开销呢,就会是三分之二,那实际上它的存储的密度也就只有三分之一。那我们怎么样来提高它的这样一个存储效率呢?啊,在C和C++里面呢,啊,比如说在C里面我们可以用union 的类型来定义。 而似乎 a 就是分支合一结点可以统一。啊,然后呢我们 这个,也许看它哪一个是存得多少,那我们哪一个是不是能够存得更有效一些呢。但是其实,union 它有这么一个特点,也就是, union 里面它有几个,啊,类型的话呢,那我们要预留的存储空间是最常的那个那些,所以这只是说,在表达形式上看起来好像统一了,但其实,啊,在存储效率上其实没有什么本质的改进。然后 在 C++里面呢,啊,也可以用子类和虚函数来 啊实现,那这个也只是说从概念上可能区分。但,其实,啊存储的空间呢其实没有特别本质的改进。早期,因为内存资源有限,可能有一些方法来改进这个存储效率。我们可以直接存储这个叶结点它的值,而不需要再,啊,另外开辟一个叶结点。而这个叶结点,它指向的呢,就都是一些外部的这个空,有 Leaf 的这个指针。当然,为了要区别我们是在利用了这个指针来存到别的数据,还是说本来它就是个指针域,那就是说,还需要用一些方法来标记。那,因为想节省内存,所以就想着说干脆用这个指针来表示,就是指针我们一般它是比较大的,就是一般也就在四枝节,有的是八枝节。那么在高位呢,总是零的。那么就用这个最高位的这个位来做它的标记位。那这种方法的话,它带来算法的复杂度,就是说那种算法是非常难写难读的,难维护的。 因此,我们基本上现在不怎么使用这些方法。好,那对于一些特殊的二叉树,我们可以采用顺序存储方法。例如对这个完全二叉树,它就可以继续顺序的储存。因为,完全二叉树呢,它的这个结构,它是从上到下,从左到右,满满当当的存储的。因此呢,啊,我们可以把它放在一个数组里头,就是按照它的这个编号直接放进去。那从存储上来说,它就是一个线性的了。 但是,逻辑上它还是一个二叉树形的结构。而且我们可以很方便的通过它存储在数组里面的相应的下标,来计算出它的父结点和左右子结点的相关的下标。那我们看一下完全二叉树的下标公式。对于这么一个完全二叉树,啊我们这里的习惯编号是 从 0 开始编。也有人是啊从1 开始编。 那么,在这么一个完全二叉树里面,我们可以看到,大约有一半的结点呢它是没有子结点的。那,对于这个另外一半比较靠近根的结点,啊它有子结点的情况。那么这种时候呢,它的结点 i 它的左孩子呢就是 2i+1,然后相应的右孩子是 2i+2。那我们再来看它的父结点。啊父结点的话呢,啊就是 i -1 除以 2 取下整。那可以算出来。而且这里面有一个规律就是在我们的编号体系里面呢, 左兄弟这个情况呢它们都是奇数的,然后呢,啊,右结点这个情况呢,他们是偶数的。啊因此,对于这个奇数的这么一个结点,那它的右兄弟呢,就是 i + 1。那对于偶数情况呢, 就是把它的下标呢,再减 1就找到它的左兄弟。所以我们可以很方便的计算出 他们的这种相应的逻辑的这种关系。好,那我们给大家啊留两个思考题。那,第一个呢,就是说,啊, 我们的一般的教材呢都是用二叉链的形式来写这个二叉树的相应的算法。那如果我们用三叉链的时候,那这些算法要做一些什么改变?我们要特别注意对于插入删除的时候,维护这种父指针的信息。还有就是对于完全三叉树,我们是不是也有一套下标公式?而且我们当然是可以把它存储在啊这样一个数组里头的。好,谢谢大家。

二叉树概念

https://www.coursera.org/lecture/shuju-jiegou-suanfa/er...