《数据结构》课程教学资源（PPT课件）第六章 树和二叉树（6.3 以结点类为基础的二叉树设计 6.4 二叉树类 6.5 线索二叉树 6.6 哈夫曼树）

6.3 以结点类为基础的二又树设计6.3.1 二叉树结点类class BiTreeNodeprivate BiTreeNode leftChild:private BiTreeNode rightChild;private Object data;public BiTreeNode(leftChild = null;rightChild = null:A

6.3 以结点类为基础的二叉树设计 6.3.1 二叉树结点类 class BiTreeNode{ private BiTreeNode leftChild; private BiTreeNode rightChild; private Object data; public BiTreeNode() { leftChild = null; rightChild = null; }

public BiTreeNode(Objectitem, BiTreeNode left, BiTreeNode right) data = item;leftChild=left;rightChild = right;1public BiTreeNode getLeftOtreturnleftChild;publicBiTreeNodegetRightOreturn rightChild;public Object getDataOreturn data;1

public BiTreeNode(Object item, BiTreeNode left, BiTreeNode right) { data = item; leftChild = left; rightChild = right; } public BiTreeNode getLeft(){ return leftChild; } public BiTreeNode getRight(){ return rightChild; } public Object getData(){ return data; } }

6.3.2 二叉树的遍历指按照某种顺序访问二叉树中的每个结点1、遍历定义使每个结点被访问一次且仅被访问一次。（或指按某条搜索路线遍访每个结点且不重复）。它是树结构插入、删除、修改、查找和排2、遍历用途序运算的前提，是二叉树一切运算的基础和核心

6.3.2 二叉树的遍历 1、遍历定义—— 2、遍历用途—— 指按照某种顺序访问二叉树中的每个结点， 使每个结点被访问一次且仅被访问一次。 （或指按某条搜索路线遍访每个结点且不 重复）。 它是树结构插入、删除、修改、查找和排 序运算的前提，是二叉树一切运算的基础 和核心

3、遍历规则左子树）二叉树由根右子树构成，定义为D、L、RD、L、R的组合定义了六种可能的遍历方案：DLR, DRL, LDR, RDL, LRD, RLD*若限定先左后右，则有三种实现方案：DLRLDRLRD前序遍历中序遍历后序遍历注：（“前、中、尺的意思是指访问的结点D是先于子树出现还是后于子树出现以根结点为参照系

3、遍历规则——— 二叉树由根、左子树、右子树构成，定义为D、L、R 以根结点为参照系 注：“前、中、后”的意思是指访问的结点D是先于子树出 现还是后于子树出现。 ❖ D、 L、R的组合定义了六种可能的遍历方案： DLR, DRL, LDR, RDL, LRD, RLD ❖ 若限定先左后右，则有三种实现方案： DLR LDR LRD 前序遍历 中序遍历 后序遍历

前序遍历(DLR)递归算法为：若二又树为空则算法结束；否则：(1)访问根结点：A(2)前序遍历根结点的左子树；(3）前序遍历根结点的右子树。FHABDGCEF

前序遍历（DLR）递归算法为： 若二叉树为空则算法结束；否则： （1）访问根结点； （2）前序遍历根结点的左子树； （3）前序遍历根结点的右子树。 A D G E C F B A B D G C E F

中序遍历（LDR）递归算法为：若二叉树为空则算法结束；否则：(1) P中序遍历根结点的左子树：A(2)访问根结点：（3）中序遍历根结点的右子树。FHDGBAECF

中序遍历（LDR）递归算法为： 若二叉树为空则算法结束；否则： （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 A D G E C F B D G B A E C F

后序遍历（LRD）递归算法为：若二又树为空则算法结束；否则：（1）后序遍历根结点的左子树：A（2）后序遍历根结点的右子树：（3）访问根结点。RFGDBEFCA

后序遍历（LRD）递归算法为： 若二叉树为空则算法结束；否则： （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点。 A D G E C F B G D B E F C A

层次遍历：按二又树的层次序列（即从根结点层至叶结点层），同一层中按先左子树再右子树的次序遍历二又树。ABABCDEFGEHC由分析可知，二又树层序遍历的特点是，即"先被访问的父结点的孩子结点”先于”后被访问的父结点的孩子结点进行访问。这样，如果把已访问的结点放在一个队列中，那么所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此可以借助队列实现二又树的层序遍历

层次遍历：按二叉树的层次序列（即从根结点层至叶结点 层），同一层中按先左子树再右子树的次序遍历二叉树。 由分析可知，二叉树层序遍历的特点是，即"先被访问 的父结点的孩子结点"先于"后被访问的父结点的孩子结点" 进行访问。这样，如果把已访问的结点放在一个队列中，那 么所有未被访问结点的访问次序就可以由存放在队列中的已 访问结点的出队列次序决定。因此可以借助队列实现二叉树 的层序遍历。 A D G E C F B A B C D E F G

二又树的层序遍历算法如下：（1）初始化设置一个队列：（2）把根结点指针入队列：（3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）；（3.a）出队列取得当前队头结点，访问该结点；（3.b）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入队列：（3.c）若该结点的右孩子结点非空，则将该结点的右孩子结点指针入队列：(4）结束

二叉树的层序遍历算法如下： （1）初始化设置一个队列； （2）把根结点指针入队列； （3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）； （3.a）出队列取得当前队头结点，访问该结点； （3.b）若该结点的左孩子结点非空，则将该结点的左孩子 结点指针入队列； （3.c）若该结点的右孩子结点非空，则将该结点的右孩子 结点指针入队列； （4）结束

虽然二叉树是一种非线性结构，二叉树不能像单链表那样每个结点都有一个惟一的前驱结点和惟一的后继结点，但当对一个二又树用一种特定的遍历方法来遍历时，其遍历序列一定是线性的，且是惟一的

虽然二叉树是一种非线性结构，二叉树不能 像单链表那样每个结点都有一个惟一的前驱结点 和惟一的后继结点，但当对一个二叉树用一种特 定的遍历方法来遍历时，其遍历序列一定是线性 的，且是惟一的