当前课程知识点:Data Structures and Algorithm Design Part I >  05.Binary_Tree >  C.Binary_Tree >  05C-3

返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表

05C-3在线视频

下一节:05D-1

返回《Data Structures and Algorithm Design Part I》慕课在线视频列表

05C-3课程教案、知识点、字幕

接下来我们来介绍

这一节最重要的一点

如何通过二叉树来描述多叉树

也就是一般意义上的树

表面上看 这是不可能的

因为你似乎是在用一种特例

来描述所有的情况

然而很有意思的是 这竟然是事实

这就犹如你可以严格的证明

在0和1之间的实数

与整个实轴上的实数

同样多一样

这里并非没有条件

当然条件也不多

就两条

我们此前所介绍的

有根以及有序

换而言之

凡是有根且有序的树

都可以通过二叉树描述表示

并进而实现

为此我们需要回忆此前

刚刚介绍的长子兄弟表示法

这个方法可以用这样两幅图来示意

我们说在原来一般性的树的表示中

每一个节点的出度不同

它所对应的出边

也就需要相应的记录

这种方法我们分析过

它规整性非常差

那么长子兄弟法呢

它只要求每一个节点

记录两个引用就够了

首先一个是相对于它而言的

所有孩子中的最大者

也就是firstChild() 长子

另一个呢 是相对于

当前这个节点而言的下一个兄弟

也是一个引用

我们曾经介绍过

为了便于理解

我们应该将所有的firstchild()

也就是一代与下一代之间的

所有的引用画为垂直方向的

这样通过高度

就可以区分代继或者叫辈分

而同一代的nextSibling这种引用呢

我们建议大家画成水平的

表示它们虽然有长幼之分

但是从辈分上来讲 都是相同的

它们互为兄弟

那我要指出的是

如果你已经懂得了长子兄弟法

那么再进一步地将这种表示法

转化为二叉树表示法就只差一步

甚至说半步之遥

哪半步呢?

我们只需要将每一个节点

所对应的那样一个局部

也就是firstChild()

和nextSibling()这样一个结构

做一个45度角的旋转

使之变为这样一个形式

firstChild()和nextSibling()

你看到什么了?

没错 这就是一个二叉树的局部

我们如果将这样一个原则

施加到长子兄弟表示法中的

任何一个局部

就可以总体上将原来那样一个表示法

转化为我们这里以左右相别的

二叉树表示法

仍然以我们这里的树为例

再将原来这样一棵一般性的

有根有序树

转化为长子兄弟表示法之后

只需对它的任何局部

实施这样的一个45度的旋转

就可以将它转化为

最右侧这样一个形式

我们可以看到

它们之间是完全对应的

比如说 根节点

再比如说 根节点通往

它的第一个孩子的这条边

这条边经过旋转以后

将会成为这个节点

通往它的左孩子的那条边

再如A这个节点

它的下一个兄弟是B

而在这棵树中呢

A节点将以B作为它的右孩子

其它的位置也是如此

大家不妨在课后逐一地校验

总而言之 通过这样的一个局部的变换

我们就可以将任何一棵一般性的树

转化为它的长子兄弟表示法

并且进一步地转化

并理解为是一棵二叉树

由此可见

如果说我们这一章的任务

是描述并且实现以及利用树结构的话

不如说我们只需研究并且实现二叉树

也正是因为这样的一个原因

尽管后者只是前者的一个特例

我们依然将后者 也就是二叉树

作为我们这一章的标题

这也是为什么

你在第一节会看到一个有趣的现象

树反而会成为那样一个小节的标题

好了

二叉树结构的实现和相关的算法

又是如何的呢?

这正是我们接下来几节

将要陆续讨论的

Data Structures and Algorithm Design Part I课程列表:

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--(a)计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-(xd):LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

05C-3笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。