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