山东大学《数据结构》讲义04树和二叉树.docx

第四章树和二叉树

内容概述

树是一种非线性数据结构。树结构经常用于描述和处理数据元素的层次关系，尤其适

用于大规模的信息处理任务，例如建立数据库管理系统时所用的层次模型 就是一种树

型结构。本章主要以二叉树为例，讲述树结构及其应用，主要内容包 括：

(1)树的定义、术语及性质；

(2)二叉树的定义、性质，二叉树的存储结构及二叉树的遍历等各种操作的算 法实现；

(3)线索二叉树；

(4)树、森林与二叉树的转化；

思考.树型结构的结构特点

1 .树和二叉树的主要差异表现在哪些方面？

2 .二叉树具有那些重要特性？

3 .二叉树有哪些遍历策略？如何利用算法实现？

4 .某二叉树的后序遍历序列和中序遍历序列，如何求解出其前序遍历序列。

5 .一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该

elsereturnOK;}//PreOrderT raverse

算法4-1二叉树的先序遍历递归算法(2)中序遍历算法

StatusInOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)){〃采用二叉链表存储

结构，visit是对数据元素操作的应用函数

StatusPostOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)){

〃采用二叉链表存储结构，visit是对数据元素操作的应用函数〃该算法采用递归的方

式，对每个数据元素调用函数visit

if(T){if(PostOrderTraverse(T->left,visit))

if( PostOrderT raverse(T- > right,visit)) if(visit(T->data))returnOK;returnERROR;

)elsereturnOK;

}//PostOrderT raverse算法4-3二叉树的后序遍历递归算法

以上的三种算法均为递归算法，在运行过程中，函数需要使用系统设立的''递归 工作

栈〃存储调用函数和被调用函数之间的链接及信息的交换。下面我们以中序 算法为例，

结合图4.8(a)的二叉树，分析它的执行过程。

③ if(InOrderr raverse(T-> left, visit))(4) if(visit(T->data))

⑤if(InOrderT raverse(T- > right,visit))

returnERROR;

)

elsereturnOK;

递归工作栈状态（返

址，指针值）

0,Ta4,Tb

0,Ta4,Td

三层 1,2,34,Tb0,Ta

四层1,2,3O,Ta