第6章 树和二叉树第1次(1).ppt

第6章 树和二叉树 授课人：邹丽霞 6.2.3 二叉树抽象数据类型 Package dataStructure.tree; public interface BinaryTTreeE { //二叉树接口 boolean isEmpty(); //判断是否空二叉树 int count(); //返回二叉树的结点个数 int height(); //返回二叉树的高度 BinaryNodeE getRoot(); //返回二叉树的根结点 BinaryNodeE getParent(BinaryNodeE node); //返回node父母结点 void preOrder(); //先根次序遍历二叉树 void inOrder(); //中根次序遍历二叉树 void postOrder(); //后根次序遍历二叉树 void levelOrder(); //按层次遍历二叉树 BinaryNodeE search(E element); //查找并返回元素为element结点 void insert(BinaryNodeE p, E element, boolean leftChild); //插入element元素作为p结点的左/右孩子 void remove(BinaryNodeE p, boolean leftChild); //删除p的左/右子树 void clear(); //清空 } 6.3.2 二叉树的二叉链表实现 二叉链表结点类 package dataStructure.tree; public class BinaryNodeE { //二叉树的二叉链表结点类 public E data; //数据元素 public BinaryNodeE left, right; //分别指向左、右孩子 6.3.2 二叉树的二叉链表实现 二叉树类 package dataStructure.tree; import dataStructure.tree.BinaryNode; public class BinaryTreeE //二叉树类 { protected BinaryNodeE root; //根结点 6.3.3 二叉树的遍历 问题的提出：为什么要对二叉树进行遍历操作？ 问题的引入： 树和二叉树是一种典型的层次结构（即一对多关系），要想详细了解、研究该结构，并且对其进行各种操作，就要对其组成的结点进行处理，比如：在树或者二叉树中查找具有某种特征的结点，或者对其中的全部结点逐一处理，都需要对该结构中的具体结点进行查询，因此引入二叉树的遍历操作。 6.3.3 二叉树的遍历 二叉树的遍历过程是递归的： 先根遍历序列：A B D G C E F H 中根遍历序列：D G B A E C H F 后根遍历序列：G D B E H F C A 6.3.4 构造二叉树 先根和中根序列表示 2.标明空子树的先根序列表示 3.广义表表示 4.以完全二叉树的层次遍历序列构造链式存储结构的完全二叉树 【例6.3】 建立二叉链表表示的完全二叉树。 6.3.5 二叉树的插入和删除操作 插入一个结点 public void insert(BinaryNodeE p, E element, boolean leftChild) //插入元素element作为p结点的孩子 { //若leftChild为true，插入结点作为左孩子，否则作为右孩子