数据结构6章 树和二叉树

《数据结构6章 树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章树和二叉树6.1树6.2二叉树的定义及性质6.3二叉树的遍历6.4线索二叉树6.5堆排序6.6树与二叉树的转换6.1树6.1.1树的定义6.1.2树的术语6.1.3树的广义表形式表示《数据结构（Java版）》叶核亚6.1.1树的定义树（tree）是由n（n≥0）个结点组成的有限集合。n=0的树称为空树；对n>0的树T，有：有一个特殊的结点称为根结点（root），它只有直接后继结点，没有直接前驱结点。当n>1时，除根结点之外的其他结点分为m（m≥0）个互不相交的集合T1,T2,…,Tm，其中每个集合Tm（1≤i≤m）本身又是一棵结构与树类同的子树（subtree）。每棵子树的根结点有且仅

2、有一个直接前驱结点，但可以有零或多个直接后继结点。《数据结构（Java版）》叶核亚6.1.2树的术语1．结点2．孩子结点与双亲结点3．兄弟结点4．结点的度5．叶子结点与分支结点6．树的度7．结点的层次8．树的深度或高度9．森林《数据结构（Java版）》叶核亚6.2二叉树的定义及性质6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构6.2.4声明二叉树类《数据结构（Java版）》叶核亚6.2.1二叉树的定义1．二叉树的递归定义二叉树（binarytree）是n（n≥0）个结点组成的有限集合。n=0时称为空二叉树；n>0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右

3、子树的子二叉树构成。《数据结构（Java版）》叶核亚2．二叉树的基本形态图6.53个结点树与二叉树的基本形态《数据结构（Java版）》叶核亚6.2.2二叉树的性质1．性质1若根结点的层次为1，则二叉树第i层的结点数目最多为2i-1（i≥1）。2．性质2在深度为k的二叉树中，至多有2k-1个结点（k≥0）。3．性质3二叉树中，若叶子结点数为n0，2度结点数为n2，则有n0=n2+1。《数据结构（Java版）》叶核亚4．满二叉树与完全二叉树5．性质4如果一棵完全二叉树有n个结点，则其深度。6．性质5若将一棵具有n个结点的完全二叉树按顺序表示，对于编号为i（1≤i≤n）的结点，有如下特点：若i=1

4、，则i为根结点，无双亲；若i≠1，则i的双亲是编号为i/2的结点。若2i≤n，则i的左孩子是编号为2i的结点；若2i＞n，则i无左孩子。若2i+1≤n，则i的右孩子是编号为2i+1的结点；若2i+1＞n，则i无右孩子。《数据结构（Java版）》叶核亚6.2.3二叉树的存储结构1．二叉树的顺序存储结构《数据结构（Java版）》叶核亚2．二叉树的链式存储结构《数据结构（Java版）》叶核亚6.2.4声明二叉树类1．二叉树的结点类packageds_java;publicclassTreeNode1//二叉树的结点类{publicStringdata;//数据元素publicTreeNode1le

5、ft,right;//指向左、右孩子结点的链publicTreeNode1(){this("?");}publicTreeNode1(Stringd)//构造有值结点{data=d;left=right=null;}《数据结构（Java版）》叶核亚2．二叉树类packageds_java;importds_java.TreeNode1;publicclassTree1//以先根、中根次序遍历序列建立二叉树{protectedTreeNode1root;//指向二叉树的根结点publicTree1()//构造空二叉树{root=null;}}《数据结构（Java版）》叶核亚6.3二叉树的遍历6

6、.3.1二叉树遍历的概念6.3.2二叉树遍历的递归算法6.3.3建立二叉树6.3.4二叉树遍历的非递归算法6.3.5按层次遍历二叉树《数据结构（Java版）》叶核亚6.3.1二叉树遍历的概念遍历（traversal）二叉树就是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问一次。所谓访问，是指对每一个结点的数据元素进行查阅、修改等操作。一次完整的遍历按照一种规则对二叉树中的结点产生一种线性次序。若规定对子树的访问按“先左后右”的次序进行，则遍历二叉树有3种次序：先根次序：访问根结点，遍历左子树，遍历右子树。中根次序：遍历左子树，访问根结点，遍历右子树。后根次序：遍历左子树，遍历

7、右子树，访问根结点。《数据结构（Java版）》叶核亚按先根次序遍历二叉树的过程《数据结构（Java版）》叶核亚6.3.2二叉树遍历的递归算法1．按先根次序遍历二叉树的递归算法若二叉树为空，返回；否则，继续。从根结点开始，访问当前结点。按先根次序遍历当前结点的左子树。按先根次序遍历当前结点的右子树。publicvoidpreorder(TreeNode1p)//先根次序遍历二叉树{if(p!=null){Sys