Java数据结构之树与二叉树.ppt

学习目标 树二叉树的定义及性质二叉树的遍历树与二叉树的转换 树 树的定义树的术语 树的定义 树 tree 是由n n 0 个结点组成的有限集合 n 0的树称为空树 对n 0的树T 有 有一个特殊的结点称为根结点 root 它只有直接后继结点 没有直接前驱结点 当n 1时 除根结点之外的其他结点分为m m 0 个互不相交的集合T1 T2 Tm 其中每个集合Tm 1 i m 本身又是一棵结构与树类同的子树 subtree 每棵子树的根结点有且仅有一个直接前驱结点 但可以有零或多个直接后继结点 树的术语 结点孩子结点与双亲结点兄弟结点祖先结点与后代结点结点的度叶子结点与分支结点树的度 二叉树的定义及性质 二叉树的定义二叉树的性质二叉树的存储结构声明二叉树类 二叉树的定义 二叉树的递归定义二叉树 binarytree 是n n 0 个结点组成的有限集合 n 0时称为空二叉树 n 0的二叉树由一个根结点和两棵互不相交的 分别称为左子树和右子树的子二叉树构成 二叉树的基本形态 3个结点树与二叉树的基本形态 二叉树的性质 性质1若根结点的层次为1 则二叉树第i层的结点数目最多为2i 1 i 1 性质2在深度为k的二叉树中 至多有2k 1个结点 k 0 性质3二叉树中 若叶子结点数为n0 2度结点数为n2 则有n0 n2 1 满二叉树与完全二叉树性质4如果一棵完全二叉树有n个结点 则其深度 性质5若将一棵具有n个结点的完全二叉树按顺序表示 对于编号为i 1 i n 的结点 有如下特点 若i 1 则i为根结点 无双亲 若i 1 则i的双亲是编号为i 2的结点 若2i n 则i的左孩子是编号为2i的结点 若2i n 则i无左孩子 若2i 1 n 则i的右孩子是编号为2i 1的结点 若2i 1 n 则i无右孩子 二叉树的存储结构 二叉树的顺序存储结构 二叉树的链式存储结构 声明二叉树类 二叉树的结点类publicclassTreeNode publicObjectdata 数据元素publicTreeNodeleft right 指向左 右孩子结点的链publicTreeNode this publicTreeNode Objecto 构造有值结点data o left null right null 二叉树类节点 publicvoidsetData Objectdata this data data publicObjectgetData returndata publicvoidsetLeft TreeNodeleft this left left publicTreeNodegetLeft returnleft 二叉树类节点 publicTreeNodesetRight TreeNoderight returnthis right right publicTreeNodegetRight returnright 测试一个节点是否是叶子节点publicbooleanisLeaf returnleft null 如何从最左节点或最右节点获取数据 二叉树类节点 从最左节点或最右节点获取数据publicObjectgetLeftmostData if left null returndata else returnleft getLeftmostData 如何删除最左节点或最右节点 提示 二叉树类节点 删除最左或最右节点publicTreeNoderemoveLeftmost if left null 最左节点是根节点 因为它没有左孩子returnright else 一个递归调用删除左子树的最左节点left left removeLeftmost returnthis 练习 提供复制一棵二叉树的