般二叉树 234567891011 a e ol dd o flg f g 从树根起,自上层至下层,每层自左至右的给所有结点编号 ●缺点是有可能对存储空间造成极大的浪费,在最坏的情况 下,一个深度为h且只有h个结点的右单支树,却需要2h-1个 结点存储空间。而且,若经常需要插入与删除树中结点时, 顺序存储方式不是很好! 北京邮电大学自动化学院 21
北京邮电大学自动化学院 21 a b c d e f g ⚫ 从树根起，自上层至下层，每层自左至右的给所有结点编号. 一般二叉树 ⚫ 缺点是有可能对存储空间造成极大的浪费，在最坏的情况 下，一个深度为h且只有h个结点的右单支树，却需要2h-1个 结点存储空间。而且，若经常需要插入与删除树中结点时， 顺序存储方式不是很好！ a b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11
2、链式存储结构 二叉链表:二叉树的每一个结点最多有左、右两棵子树,故链 表的结点结构除数据域外可设两个链域:左孩子(lc)、右孩 子(rc)分别指向左、右孩子。称结点由两个链域组成的链表 为二叉链表。 Achild data rchild typedef struct BitNode f TElem Type data A|∧ struct BiTNode Child, rchild 3 BiTNode, *BiTree; ( A B D E F E F 在n个结点的二叉链表中,有n+1个空指针域 京邮电
北京邮电大学自动化学院 22 typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; A B C D E F G ⚫ 在n个结点的二叉链表中，有n+1个空指针域 A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ ⚫ 二叉链表：二叉树的每一个结点最多有左、右两棵子树，故链 表的结点结构除数据域外可设两个链域：左孩子（lc）、右孩 子（rc）分别指向左、右孩子。称结点由两个链域组成的链表 为二叉链表。 2、链式存储结构 lchild data rchild
叉链表:有时为了便于找到双亲结点,另设一个指向双亲的 链域,结点由三个链域组成的链表称为三叉链表。 ● typedef struct node lchild data parent rchild i datatype data o struct node *Child, *rchild, *parent A|∧ JJD B B ∧C D E F E ∧|F G 北京邮电大学自动化学院
北京邮电大学自动化学院 23 ⚫ typedef struct node ⚫ { datatype data; ⚫ struct node *lchild, *rchild, *parent; ⚫ }JD; A B C D E F G A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ ^ ⚫ 三叉链表：有时为了便于找到双亲结点，另设一个指向双亲的 链域，结点由三个链域组成的链表称为三叉链表。 lchild data parent rchild
线索链表:用链表表示的二叉树中也会存在许多空链域。例如 在含有n个结点的二叉链表中,共有2n个链域,实用n-1链域 (仅有n1个分支),还有n+1个空链域。(可以利用这些空链 域存储其它有用信息,从而得到另一种链式存储结构——一线索 链表。) 63遍历二叉树和线索二叉树 ●6.3.1遍历二叉树 ●1、定义及递归算法 ●遍历二叉树:是指按一定的次序系统地访问二叉树中所有结 点,而且仅被访问一次 ●访问:所谓“访问”可以是对结点作各种处理,如输出结点数 据域值。 北京邮电大学自动化学院
北京邮电大学自动化学院 24 ⚫ 线索链表：用链表表示的二叉树中也会存在许多空链域。例如 在含有n个结点的二叉链表中，共有2n个链域，实用n-1链域 （仅有n-1个分支），还有n+1个空链域。（可以利用这些空链 域存储其它有用信息，从而得到另一种链式存储结构——线索 链表。） 6.3 遍历二叉树和线索二叉树 ⚫ 6.3.1 遍历二叉树 ⚫ 1、定义及递归算法 ⚫ 遍历二叉树：是指按一定的次序系统地访问二叉树中所有结 点，而且仅被访问一次。 ⚫ 访问：所谓“访问”可以是对结点作各种处理，如输出结点数 据域值
6.3.1遍历二叉树 ●二叉树是由三个基本单元组成:根结点、左子树和右子树。 因此,若能依次遍历这三部分,便是遍历了整个二叉树。 ●假如以L、D、R分别表示遍历左子树、访问根结点和遍历右 子树,则可能有:DLR、LDR、LRD、DRL、RDL、RLD六 种遍历二叉树的方案。 ●若限定先左后右,则只有前三种情况,分别称之为先(根) 序遍历,中(根)序遍历和后(根)序遍历。 北京邮电大学自动化学院
北京邮电大学自动化学院 25 ⚫ 二叉树是由三个基本单元组成：根结点、左子树和右子树。 因此，若能依次遍历这三部分，便是遍历了整个二叉树。 ⚫ 假如以L、D、R分别表示遍历左子树、访问根结点和遍历右 子树，则可能有：DLR、LDR、LRD、DRL、RDL、RLD六 种遍历二叉树的方案。 ⚫ 若限定先左后右，则只有前三种情况，分别称之为先（根） 序遍历，中（根）序遍历和后（根）序遍历。 6.3.1 遍历二叉树