第6讲 树和二叉树(二叉树的遍历)(完成)

数据结构与算法设计任课教师：刘晋萍Email：785297343@QQ:

785297343第六讲树和二叉树树的基本概念树的定义树的基本术语二叉树二叉树的定义二叉树的性质二叉树的基本操作二叉树的存储结构二叉树的遍历树与二叉树树与二叉树的转换树的遍历二叉树的遍历二叉树的遍历二叉树遍历的概念二叉树的遍历二叉树遍历的概念二叉树遍历的方法二叉树的遍历二叉树遍历的概念二叉树遍历的方法二叉树遍历的应用二叉树的遍历二叉树遍历的概念二叉树遍历的方法二叉树遍历的应用二叉树遍历的实现算法结束二叉树遍历的概念遍历的含义访问结构中的所有元素且只访问一次二叉树遍历的定义按一定规律对二叉树中每个结点访问且仅访问一次二叉树遍历的目的在对二叉树的很多处理中，需要二叉树结点的一个线性序列实质而言，遍历的目的就是对二叉树进行线性化处理，以得到一个结点的线性序列对二叉树处理而言，遍历的目的是为二叉树的其他运算奠定基础非线性结构遍历结点的访问序列线性化回去二叉树遍历的方法有哪些方法二叉树由三个基本部分组成：根结点

左子树

右子树遍历二叉树实质就是完成如下三项工作：访问根结点D遍历左子树L遍历右子树R这三项工作按顺序组合可以得到6种遍历方案：DLRDRLLDRRDLLRDRLD对这6种方案加上“先左后右”的限定，则得到如下3种遍历方案：DLR称为先（根）序遍历LDR称为中（根）序遍历LRD称为后（根）序遍历遍历方法的描述根左子树右子树看图路径DLRDRLLDRRDLLRDRLDDLRDRLLDRRDLLRDRLDDLR

DRLLDRRDLLRDRLDDLR

DRL

LDR

RDL

LRD

RLD访问根结点、遍历左子树、遍历右子树访问根结点、遍历右子树、遍历左子树遍历左子树、访问根结点、遍历右子树遍历右子树、访问根结点、遍历左子树遍历左子树、遍历右子树、访问根结点遍历右子树、遍历左子树、访问根结点回去二叉树遍历的方法有哪些方法二叉树由三个基本部分组成：根结点

左子树

右子树遍历二叉树实质就是完成如下三项工作：访问根结点D遍历左子树L遍历右子树R这三项工作按顺序组合可以得到6种遍历方案：DLRDRLLDRRDLLRDRLD对这6种方案加上“先左后右”的限定，则得到如下3种遍历方案：DLR称为先（根）序遍历LDR称为中（根）序遍历LRD称为后（根）序遍历遍历方法的描述根左子树右子树看图三种遍历方案的遍历路径一样，只是访问根结点的时机不同二叉树遍历的方法有哪些方法遍历方法的描述先序遍历二叉树若二叉树为空，则空操作；否则

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。中序遍历二叉树若二叉树为空，则空操作；否则

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。后序遍历二叉树若二叉树为空，则空操作；否则

(1)后序遍历左子树；

(2)后序遍历右子树;(3)访问根结点。根左子树右子树看例先序序列中序序列后序序列（根、左、右）（左、根、右）（左、右、根）二叉树遍历方法例1先序序列中序序列后序序列ABCDEFGHK待遍历的二叉树根右子树左子树ABCEFGDHK回去CDBAEHGKFDCBHKGFEA二叉树遍历的应用输出二叉树中的所有结点输出二叉树中的叶子结点求二叉树的深度对每一个应用问题：确定“访问”的具体操作是什么分析对遍历顺序的要求，确定用先序遍历、中序遍历还是后序遍历给出解决问题的算法描述思考练习：用何种遍历实现对二叉树左右子树的交换？在交换二叉树左右子树的遍历中，“访问”操作是什么？写出一个实现二叉树左右子树交换的算法描述。回去先序遍历二叉树若二叉树为空，则空操作；

否则，依次做如下操作：

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。输出二叉树中的所有结点分析：该问题需要对二叉树进行遍历，即：对所有结点进行“访问”，且只访问一次这里的“访问”就是“结点的输出”“访问”顺序的确定只要能对所有结点进行输出，没有结点输出顺序的要求，因此，按先序、中序和后序都可以这里以先序为例算法描述（基于先序遍历）若二叉树为空，则空操作；否则，依次做如下操作：

(1)输出根结点；

(2)输出左子树中的所有结点；

(3)输出右子树中的所有结点。思考：若基于中序遍历或基于后序遍历，则该问题的算法应该是怎样的？看例子回去基于中序遍历基于后序遍历输出二叉树中的所有结点算法描述（基于中序遍历）若二叉树为空，则空操作；否则，依次做如下操作：

(1)输出左子树中的所有结点；

(2)输出根结点；

(3)输出右子树中的所有结点。中序遍历二叉树若二叉树为空，则空操作；

否则，依次做如下操作：

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。回去输出二叉树中的所有结点算法描述（基于后序遍历）若二叉树为空，则空操作；否则，依次做如下操作：

(1)输出左子树中的所有结点；

(2)输出右子树中的所有结点；

(3)输出根结点。后序遍历二叉树若二叉树为空，则空操作；

否则，依次做如下操作：

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。回去输出二叉树中的所有结点例ABCEFGDHK待输出的二叉树基于先序遍历结点的输出序列：ABCDEFGHK基于中序遍历结点的输出序列：基于后序遍历结点的输出序列：CDBAEHGKFDCBHKGFEA回去输出二叉树中的叶子结点分析：该问题需要对二叉树中所有结点进行“访问”，且只访问一次这里的“访问”是“带判断的输出”，也就是：“是叶子结点就输出”“访问”顺序的确定只要能对所有叶子结点进行输出，没有结点输出顺序的要求，因此，按先序、中序和后序都可以算法描述若二叉树为空，则空操作；否则，依次做如下操作：（1）如果根结点既没有左孩子也没有右孩子，则输出根结点（2）输出左子树中的叶子结点（3）输出右子树中的叶子结点算法描述（基于中序遍历）算法描述（基于后序遍历）（基于先序遍历）思考：该算法是基于先序的？中序的？还是后序的？看例子（1）如果根结点是叶子结点，则输出根结点。回去输出二叉树中的叶子结点分析：该问题需要对二叉树中所有结点进行“访问”，且只访问一次这里的“访问”是“判断+输出”，也就是：“是叶子结点就输出”需要按某种顺序进行“访问”只要能对所有叶子结点进行输出，没有结点输出顺序的要求，因此，按先序、中序和后序都可以算法描述若二叉树为空，则空操作；否则，依次做如下操作：（1）如果当前二叉树的根既没有左孩子也没有右孩子，则输出根结点（2）输出左子树中的叶子结点（3）输出右子树中的叶子结点算法描述（基于中序遍历）算法描述（基于后序遍历）（基于先序遍历）看例子输出二叉树中的叶子结点分析：该问题需要对二叉树中所有结点进行“访问”，且只访问一次这里的“访问”是“判断+输出”，也就是：“是叶子结点就输出”需要按某种顺序进行“访问”只要能对所有叶子结点进行输出，没有结点输出顺序的要求，因此，按先序、中序和后序都可以算法描述算法描述（基于中序遍历）若二叉树为空，则空操作；否则，依次做如下操作：（1）输出左子树中的叶子结点（2）如果当前二叉树的根既没有左孩子也没有右孩子，则输出根结点（3）输出右子树中的叶子结点算法描述（基于后序遍历）（基于先序遍历）看例子输出二叉树中的叶子结点分析：该问题需要对二叉树中所有结点进行“访问”，且只访问一次这里的“访问”是“判断+输出”，也就是：“是叶子结点就输出”需要按某种顺序进行“访问”只要能对所有叶子结点进行输出，没有结点输出顺序的要求，因此，按先序、中序和后序都可以算法描述算法描述（基于中序遍历）算法描述（基于后序遍历）若二叉树为空，则空操作；否则，依次做如下操作：（1）输出左子树中的叶子结点（2）输出右子树中的叶子结点（3）如果当前二叉树的根既没有左孩子也没有右孩子，则输出根结点（基于先序遍历）看例子输出二叉树中的叶子结点例ABCEFGDHK待输出的二叉树基于先序遍历叶子结点的输出序列：DHKDHKDHK基于后序遍历叶子结点的输出序列：基于中序遍历叶子结点的输出序列：思考：输出二叉树叶子结点的算法，不论基于先序、中序和后序，叶子结点的输出顺序都一样吗？为什么？回去求二叉树的深度二叉树深度的定义：结点的最大层次数MAX{左子树的深度，右子树的深度}+1求二叉树深度的算法描述：若二叉树为空，则返回0；否则，依次做如下操作：求左子树的深度lh求右子树的深度rh返回max{lh，rh}+1思考：基于什么遍历顺序后序遍历这里，对结点访问的操作是什么求以该结点为根的二叉树的深度根左子树右子树lhrh二叉树的深度？二叉树的深度=MAX{lh，rh}+1看例子回去思考：根据”二叉树的深度=MAX{lh，rh}+1“这个定义，求二叉树深度能否按先序或中序进行？为什么？求二叉树的深度例求二叉树深度的算法描述：若二叉树为空，则返回0；否则，依次做如下操作：求左子树的深度lh求右子树的深度rh返回max{lh，rh}+1ABCEFGDHK0120003000000112345回去思考与练习交换二叉树的左右子树用何种遍历实现对二叉树左右子树的交换？在交换二叉树左右子树的遍历中，”访问“操作是什么？写出一个实现二叉树左右子树交换的算法描述根据：二叉树的深度=MAX{lh，rh}+1

这个定义，求二叉树深度能否按先序或中序进行？为什么？输出二叉树叶子结点的算法，不论基于先序、中序和后序，叶子结点的输出顺序都一样吗？为什么？二叉树遍历的实现算法先序遍历的递归实现算法中序遍历的递归实现算法后序遍历的递归实现算法解决应用问题的实现算法返回P7先序遍历的递归实现算法先序遍历以root为根的二叉树void

PreOrder(BiTree

root){

if(root!=NULL)

{

Visit(root->data);

/*访问根结点*/

PreOrder(root->lchild);

/*先序遍历左子树*/

PreOrder(root->rchild);

/*先序遍历右子树*/

}}返回P26中序遍历的递归实现算法中序遍历以root为根的二叉树void

InOrder(BiTree

root)

{

if(root!=NULL)

{

InOrder(root->lchild);

/*中序遍历左子树*/

Visit(root->data);

/*访问根结点*/

InOrder(root->rchild);

/*中序遍历右子树*/

}}返回P26后序遍历的递归实现算法后序遍历以root为根的二叉树void

PostOrder(BiTree

root)

{

if(root!=NULL)

{

PostOrder(root->lchild);/*后序遍历左子树*/

PostOrder(root->rchild);/*后序遍历右子树*

Visit(root->data);

/*访问根结点*/

}}返回P26解决应用问题的实现算法输出二叉树中结点的实现算法输出二叉树中叶子结点的实现算法求二叉树深度的实现算法二叉树的创建算法算法阅读返回P26输出二叉树中结点的实现算法输出以root为根的二叉树中的结点。基于先序遍历的实现算法void

OutBiTree(BiTree

root){

if(root!=NULL)

{

printf(root->data);

/*输出根结点*/

OutBiTree(root->lchild);

/*输出左子树中的结点*/

OutBiTree(root->rchild);

/*输出右子树中的结点*/

}}返回P30输出二叉树中叶子结点的实现算法输出以root为根的二叉树中叶子结点基于先序遍历的实现算法void

OutLeaf(BiTree

root){

if(root!=NULL)

{

if(root->lchild==NULL&&root->rchild==NULL)

printf(root->data);

/*输出叶子结点*/

OutLeaf(root->lchild);

/*输出左子树中的叶子结点*/

OutLeaf(root->rchild);

/*输出右子树中的叶子结点*/

}}返回P30求二叉树深度的实现算法求以root为根的二叉树的深度int

BiTreeDepth(BiTree

root)

{

if(root!=NULL)

{

hl=BiTreeDepth(root->lchild);

/*求左子树的深度*/

hr=BiTreeDepth(root->rchild);

/*求右子树的深度*/max=hl>hr?hl:hr;

/*得到左、右子树深度较大者*/return(max+1);

/*返回树的深度*/

}

elsereturn(0);

/*如果是空树，则返回0*/}返回P30关于二叉树的创建给定一棵二叉树，可以得到它的遍历序列反之，给定一棵二叉树的遍历序列，也可以画出该二叉树能画出就意味着能创建二叉树已知二叉树的“扩展的遍历序列，画出该二叉树在二叉树的遍历序列中，用特定的元素表示空子树，就得到相应的扩展遍历序列例如，下图

中二叉树的“扩展先序遍历序列”为：AB.DF..G..C.E.H..（这里以‘.’表示空子树）继续关于二叉树的创建画出扩展先序序列为：ACF.GK..H…B.FE…

的二叉树将此过程作为创建二叉树的过程,即:创建二叉链表的过程则对应此过程的实现算法见：“利用‘扩展先序遍历序列‘创建二叉链表的算法”ACFBFGEKH继续利用“扩展先序遍历序列”创建二叉链表的算法voidCreateBiTree(BiTree

&root){

ch=getchar();

if(ch=='.')root=NULL;

else{root=(BiTree)malloc(sizeof(BiTNode));

root->data=ch;

CreateBiTree(root->lchild);

CreateBiTree(root->rchild);

}}继续ABFECFGKHrootACF.GK..H…B.FE…关于二叉树的创建已知某二叉树的先序序列和中序序列如下：先序序列：ABDGCEHF

中序序列：BGDAEHCF

画出该二叉树，并写出其后序序列。ABDGCEFH后序序列：GDBHEFCA由先序序列确定根是A由中序序列确定：（1）A有左、右子树；（2）左子树中的结点有BDG；右子树中的结点有CEFH再由先序序列确定左子树的结点BDG中B是根由中序序列确定B没有左子树，但有右子树，其中右子树中的结点有DG依此类推，直到A的左子树的结构确定。用同样的方法分析右子树的结构。继续关于二叉树的创建已知某二叉树的中序序列和后序序列如下：中序序列：EGHCFAD

后序序列：EGCADFH

画出该二叉树，并写出其先序序列。由后序序列确定根是H由中序序列确定：（1）H有左、右子树；（2）左子树中的结点有GE；右子树中的结点有FDCA再由后序序列确定左子树的结点GE中G是根，由中序序列确定G有左子树，但没有右子树，其中左子树中的结点有E。用同样的方法分析右子树的结构：根：F且F有左子树，也有右子树。左子树有结点：C右子树有结点：DA……先序序列：HGEFCDAHGFEDCA继续关于二叉树的创建思考：利用二叉树的先序和中序或者中序和后序，创建该二叉树对应的二叉链表的过程，给出算法