Page 110 - 高中 信息技术 选择性必修1 数据与数据结构

第四章 抽象数据类型

型用ElemType表示。
操作：
void InitBTree(BinTreeType &BT);

//初始化二叉树，把它置为一棵空树
void CreateBTree(BinTreeType &BT);
//建立对应的存储结构
bool EmptyBTree(BinTreeType &BT);

//判断一棵二叉树是否为空，若是则返回true，否则返回false
void TraverseBTree(BinTreeType &BT);

//按照一定的次序遍历一棵二叉树，使得每个结点的值均被访问一次
广东教育出版社
bool FindBTree(BinTreeType &BT, ElemType &node);
//从二叉树中查找值为node的结点，若存在，返回true，否则返回false
int BTreeDepth(BinTreeType &BT);

//求出一棵二叉树的深度
void PrintBTree(BinTreeType &BT);
//输出一棵二叉树

void ClearBTree(BinTreeType &BT);
//清除二叉树中的所有结点，使之变为一棵空树
}ADT 二叉树

4 . 3 . 4 二叉树的基本操作方法

二叉树的基本操作较多，下面以遍历为例，了解二叉树的基本操作方法。
遍历是二叉树的一种基本操作，是指按一定的次序访问树中所有结点，并且每个结点
的值仅被访问一次的过程。由于二叉树是非线性结构，因此二叉树的遍历实质上是将二叉

树的所有结点转换成一个线性序列的过程。
根据二叉树的递归定义，一棵非空二叉树由根结点、左子树和右子树所组成。因
此，遍历一棵非空二叉树的问题可分解为三个子问题：访问根结点、遍历左子树、遍历

右子树。若用L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉
树的遍历有DLR、LDR、LRD、DRL、RDL、RLD六种情况，若限定先左后右，则只有
前三种情况，分别称为前序遍历（或先根遍历）、中序遍历（或中根遍历）、后序遍历

（或后根遍历）。
（1）前序遍历的操作步骤为：
若二叉树为空，则结束操作；

否则：①访问根结点；

102 102

21X2204.indd 102 2019/9/26 13:53:27