数据结构（Java语言） 课件 项目七 树-家族族谱

项目七树---家族族谱目录项目七5123

典型工作任务7.1树项目需求分析典型工作任务7.2树数据结构设计典型工作任务7.3树软件代码设计典型工作任务7.4树软件测试执行典型工作任务7.5树软件文档编写46典型工作任务7.6树项目验收交付知识目标了解树的相关术语理解树的存储结构掌握二叉树的性质掌握二叉树的链式存储掌握二叉树的3种遍历及实现技能目标能够正确使用树的术语能够分析、确定树的应用场合能够熟练创建二叉树能够应用二叉树解决实际问题思政目标培养家国情怀传承中华民族优良家风培养尊老爱幼的传统美德树立正确的家庭价值观总体要求

家族族普简称家谱，家谱用于记录某家族历代家族成员信息以及成员之间关系。家谱系统就是利用计算机对一个家族所有成员信息进行管理。在家谱系统中不仅要考虑成员信息如何表示，还要考虑成员之间的关系如何存储。家谱中的成员即有父母又有孩子，一个成员只有一个父母，而孩子的数量不止一个所以家谱问题是一对多的树形问题，对应数据结构中的树形结构。一个家族的家谱就是一棵树，家谱中的成员对应树中的结点，家谱中第几代人，对应树中的层的概念，家谱中家长和孩子，对应树中的双亲结点和孩子结点。树形结构是非线性结构，非线性结构的问题比线性结构问题复杂一些。

家谱系统需要考虑成员信息和成员之间关系的存储，然后在此基础上对成员信息进行添加、查找、修改、统计等操作。因此，家谱系统功能模块包含创建家谱，显示家谱，编辑家族中成员信息，统计成员信息。家谱系统主要功能模块图如图7-1。图7-1家谱系统主要功能模块图典型工作任务7.1树项目需求分析7.2.1树

1.树的定义树是若干个结点组成的有限集合，其中必须有一个结点是根结点，其余结点划分为若干个互不相交的集合，每一个集合还是一棵树，称为根的子树。

当n=0时，这棵树是空树。这个树的定义是递归定义。结点的度：一个结点拥有的子树的数目称为该结点的度。树的度：一棵树的度是指该树中结点的最大度数。叶子和分支结点：度为零的结点称为叶子或终端结点。度不为零的结点称为分支结点。典型工作任务7.2树数据结构设计2.树的定义

树形表示法。用一棵倒立的树表示，形象直观，数据结构中经常使用这种表示方法。

嵌套集合表示法。将树的根结点看成一个大集合，其中包含若干个子树构成的互不相交的子集，一直嵌套下去，就构成一棵树的嵌套集合表示。

凹入表表示法。主要用于树的输出。

广义表表示法。根结点作为由子树组成的表的名字，写在表的左边，这样依次将树表示出来。(A(B(E,F),C,D(G)))树形表示法嵌套集合表示法凹入表示法广义表表示法典型工作任务7.2树数据结构设计3.树的存储结构1）双亲表示法

双亲表示法就是用一组连续的存储空间（一维数组）存储树中的各个结点，数组中每个元素存储本结点信息和双亲结点在数组中的位置。

树及双亲表示法典型工作任务7.2树数据结构设计dataABCDEFGparent-1000113下标01234562）孩子表示法

用指针表示出每个结点的孩子结点。由于每个结点的孩子结点个数不同，所以每个结点的孩子结点构成一个链表。

典型工作任务7.2树数据结构设计3）双亲孩子表示法

在孩子表示法中，将每个结点的双亲表示出来。由于每个结点的孩子结点个数不同，所以每个结点的孩子结点构成一个链表。

典型工作任务7.2树数据结构设计4）孩子兄弟表示法

在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。

典型工作任务7.2树数据结构设计7.2.2二叉树

1.二叉树的定义二叉树是一种每个结点最多拥有2个子树的树结构，其中第1个子树被称为左子树，第2个子树被称为右子树。二叉树是有序的，它的每个结点至多只有两棵子树，且有左、右之分，不能互换；左右子树也可以是空二叉树。

二叉树中所有结点的形态共有5种，空结点、无左右子树结点、只有左子树结点、只有右子树结点和左右子树均存在的结点。

如果一棵二叉树，所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这棵树称为满二叉树。一棵深度为k的满二叉树，有2k-1个结点。有n个结点的二叉树，当且仅当其每一个结点都与满二叉树中前n个结点编号一一对应，这棵树称为完全二叉树。完全二叉树中叶子结点只可能在层次最大的两层上出现。典型工作任务7.2树数据结构设计

2.二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。性质2：深度为k的二叉树至多有2k-1个结点（k≥1）。性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2＋1。性质4：具有n个结点的完全二叉树的深度为⌊log2n⌋+1。性质5：在一棵有n个结点的完全二叉树中，某结点编号为i,则如果有左孩子和右孩子，他们的编号为2*i和2*i+1。典型工作任务7.2树数据结构设计

3.二叉树的存储结构1）顺序存储结构用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。一般的二叉树按从上至下、从左到右的顺序将结点存储到一维数组中，不能用下标的关系来表示二叉树中结点的关系，这时仅存储了二叉树中的结点数据，并没有存储结点间的关系。所以一般的二叉树需要进行转换，添加一些空结点，使其成为完全二叉树，然后再用一维数组顺序存储。

一般二叉树转换后的完全二叉树典型工作任务7.2树数据结构设计

ABCD^^F012345672）链式存储结构

二叉树的链式存储就是用链表来存储一棵二叉树，称为二叉链表。

结点域用来存储元素的数据，lchild和rchil分别存放左、右孩子结点的存储地址，如果左孩子或右孩子不存在时，对应指针的指针域值为空，用^表示。

二叉树二叉树的链式存储结构典型工作任务7.2树数据结构设计lchilddatarchild

4.二叉树的基本操作二叉树的基本操作通常有以下几种：创建一棵空的二叉树。创建一棵有根结点的二叉树。在二叉树的parent结点中插入左孩子结点，若parent结点已有左子树，让左子树成为新插入结点的左子树。在二叉树的parent结点中插入右孩子结点，若parent结点已有右子树，让右子树成为新插入结点的右子树。删除二叉树中parent结点的左子树。删除二叉树中parent结点的右子树。在二叉树中查找数据元素x。按某种方式遍历二叉树中所有结点。典型工作任务7.2树数据结构设计

5.二叉树的类型描述

1）顺序存储类型二叉树顺序时，需要先将其转换为完全二叉树，然后再将结点按从上至下、从左向右顺序依次放入一维数组。通常二叉树越接近满二叉树，越节省空间，如果是单支树就比较浪费空间。顺序存储时，增删数据比较麻烦，需要重新建立二叉树。完全二叉树的顺序存储类型描述：classSeqBinaryTree{privateintmaxSize;privateObject[]datas;privateintlength;}典型工作任务7.2树数据结构设计2）链式存储类型由于顺序存储的弊端，树状结构在程序中建立与应用大多采用链式存储，链表的指针处理树比较方便。二叉树链式存储结构中结点类型描述：publicclassNode{ publicNodelChild,rChild;//引用左孩子和右孩子 publicObjectdata;//存储结点数据 publicNode(){//空二叉树data=null;lChild=null;rChild=null; } publicNode(Objectdata){//带根结点的二叉树this.data=data;lChild=null;rChild=null; }}典型工作任务7.2树数据结构设计二叉链表类型描述：publicclassLinkBinaryTree{ publicNoderoot; publicLinkBinaryTree(){}//创建一棵空的二叉树 publicLinkBinaryTree(Objectx){}//创建一棵仅有根结点的二叉树 publicbooleaninsertLeft(Objectdata,Nodeparent){}//parent结点插入左孩子结点 publicbooleaninsertRight(Objectdata,Nodeparent){}//parent结点插入右孩子结点 publicbooleandeleteLeft(Nodeparent){}//删除parent结点左子树 publicbooleandeleteRight(Nodeparent){}//删除parent结点右子树 }典型工作任务7.2树数据结构设计二叉链表类型描述：publicclassLinkBinaryTree{ publicNoderoot; publicLinkBinaryTree(){}//创建一棵空的二叉树 publicLinkBinaryTree(Objectx){}//创建一棵仅有根结点的二叉树 publicbooleaninsertLeft(Objectdata,Nodeparent){}//parent结点插入左孩子结点 publicbooleaninsertRight(Objectdata,Nodeparent){}//parent结点插入右孩子结点 publicbooleandeleteLeft(Nodeparent){}//删除parent结点左子树 publicbooleandeleteRight(Nodeparent){}//删除parent结点右子树 }典型工作任务7.2树数据结构设计操作的实现是基于存储结构的，采用的存储结构不同，操作实现的代码不同。基于二叉链表存储结构的以上基本操作实现如下。（1）创建一棵空的二叉树【算法7-1：创建空二叉树】publicLinkBinaryTree(){ root=newNode(); }（2）创建一棵仅有根结点的二叉树。【算法7-2：创建空二叉树】publicLinkBinaryTree(Objectx){ root=newNode(x); }典型工作任务7.2树数据结构设计（3）给parent结点插入左孩子结点【算法7-3：给parent结点插入左孩子】publicbooleaninsertLeft(Objectdata,Nodeparent){ if(parent==null){ System.out.println("插入错误"); returnfalse; }else{ Nodep=newNode(data); if(parent.lChild==null) parent.lChild=p; else { p.lChild=parent.lChild; parent.lChild=p; } returntrue; } }典型工作任务7.2树数据结构设计（4）给parent结点插入右孩子结点【算法7-4：给parent结点插入右孩子】publicbooleaninsertRight(Objectdata,Nodeparent){ if(parent==null){ System.out.println("插入错误"); returnfalse; }else{ Nodep=newNode(data); if(parent.rChild==null) parent.rChild=p; else{ p.rChild=parent.rChild; parent.rChild=p; } returntrue; } }典型工作任务7.2树数据结构设计（5）删除parent结点左子树【算法7-5：删除parent结点左子树】publicbooleandeleteLeft(Nodeparent){ if(parent==null||parent.lChild==null){ System.out.println("删除错误"); returnfalse; }else{ parent.lChild=null; returntrue; } }（6）删除parent结点右子树【算法7-6：删除parent结点右子树】publicbooleandeleteRight(Nodeparent){ if(parent==null||parent.rChild==null){ System.out.println("删除错误"); returnfalse; }else{ parent.rChild=null; returntrue; } }典型工作任务7.2树数据结构设计二叉树的遍历按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。依次遍历二叉树中的三个组成部分，便是遍历了整个二叉树假设：L：遍历左子树D：访问根结点R：遍历右子树则遍历整个二叉树方案共有：DLR、LDR、LRD、DRL、RDL、RLD六种

二叉树的定义是递归的，二叉树的遍历也是递归过程。典型工作任务7.2树数据结构设计

根结点左子树

右子树

1）先序遍历若二叉树为空树，则遍历结束，否则：第一步：访问根结点；第二步：先序遍历根结点的左子树；第三步：先序遍历根结点的右子树。【算法7-7：二叉树先序遍历】publicvoidpreOrder(Nodep){先序遍历结点序列：ABDECF if(p==null)return; else{ visit(p.getData());//访问根结点数据域 preOrder(p.lChild);//先序遍历左子树 preOrder(p.rChild);//先序遍历右子树 } }典型工作任务7.2树数据结构设计2）中序遍历若二叉树为空树，则遍历结束，否则：第一步：中序遍历根结点的左子树；；第二步：访问根结点第三步：中序遍历根结点的右子树。

右图二叉树中序遍历结点序列是：DBEACF【算法7-8：二叉树中序遍历】publicvoidinorder(Nodep){ if(p==null)return; else{ inorder(p.lChild);//中序遍历左子树 visit(p.getData());//访问根结点数据域 inorder(p.rChild);//中序遍历左子树 } }典型工作任务7.2树数据结构设计3）后序遍历若二叉树为空树，则遍历结束，否则：第一步：后序遍历根结点的左子树；第二步：后序遍历根结点的右子树；第三步：访问根结点。右图二叉树后序遍历结点序列是：DEBFCA【算法7-9：二叉树后序遍历】publicvoidpostOrder(Nodep){ if(p==null)return; else{ postOrder(p.lChild);//后序遍历左子树 postOrder(p.rChild);//后序遍历左子树 visit(p.getData());//访问根结点数据域 } }典型工作任务7.2树数据结构设计家谱中成员之间的关系是一对多的关系，如果我们限制每个成员最多只能有两个孩子，那么家谱问题就是一个二叉树问题。

家谱系统需要实现的功能有创建家谱、显示家谱、编辑家谱和统计。创建家谱是根据原始数据生成家谱二叉链表。显示家谱是以树形结构显示二叉链表中的成员构成图。编辑家谱可以查询某个成员信息、修改成员信息、给某个成员添加孩子。统计功能实现没有孩子成员信息统计、第n代成员信息统计和

家谱系统二级功能模块图家谱中总人数的统计。

典型工作任务7.3树软件代码设计7.3.1成员类的定义家谱系统中每个成员包含3个信息，姓名、年龄和在家谱中排在第几代，这3个不同类型的数据是一个整体，所以定义Member类对成员数据进行封装。

典型工作任务7.3树软件代码设计publicclassMember{ publicStringname; publicintage; publicintgeneration; publicMember(){ super(); } publicMember(Stringname,intage,intgeneration){ super(); =name; this.age=age; this.generation=generation; }}7.3.2成员类的定义家谱中一个成员是家谱树中的一个结点，在二叉链表中，结点不仅要存储数据，还要存储它的左孩子和右孩子。所以结点类型包含3部分，数据域和两个指针域，数据域存储某个成员信息，指针域存储这个成员的孩子结点的存储地址，树中指针域实际存储的是成员之间的关系。

典型工作任务7.3树软件代码设计publicclassFamilyNode{ privateFamilyNodeleftChild;//左孩子 privateFamilyNoderightChild;//右孩子 privateMemberdata;//成员数据 publicFamilyNode(){/初始化/数据域为空的结点 data=null; leftChild=null; rightChild=null; } publicFamilyNode(Memberdata){//初始化数据域为data的结点 this.data=data; leftChild=null; rightChild=null; }

典型工作任务7.3树软件代码设计publicFamilyNode(FamilyNodeleftChild,FamilyNoderightChild,Memberdata){//初始化带有数据和左孩子、右孩子的结点 this.leftChild=leftChild; this.rightChild=rightChild; this.data=data; } publicFamilyNodegetLeftChild(){ returnleftChild; } publicvoidsetLeftChild(FamilyNodeleftChild){ this.leftChild=leftChild; } publicFamilyNodegetRightChild(){ returnrightChild; } publicvoidsetRightChild(FamilyNoderightChild){ this.rightChild=rightChild; } publicMembergetData(){ returndata; } publicvoidsetData(Memberdata){ this.data=data; }}7.3.3家谱二叉链表类的定义二叉链表结点类定义完成后，就可以定义二叉链表类。二叉链表中根结点是关键，通过它可以找到树中所有结点，所以家谱二叉链表类需要一个引用指向根结点。二叉链表中实现的操作有创建家谱链表、显示家谱、查找成员、统计没有孩子的成员信息、第n代人的数量、家谱中成员总人数。

典型工作任务7.3树软件代码设计publicclassFamilyTree{ publicFamilyNoderoot; publicstaticintindex;//创建家谱时记录引用数据的位置 publicFamilyNodeCreateFamilyTree(List<Member>memberList){}//创建家谱 publicFamilyNodemidOrderSearch(FamilyNoderoot,Stringname){}//查找成员 publicvoidprintTree(FamilyNodenode,intlevel){}//输出家谱 publicintgetLeaf(FamilyNodenode){}//统计没有孩子的成员publicintgetGenerationCount(FamilyNodenode,intn){}//统计第n代人的数量 publicintgetSize(FamilyNodenode){}//统计成员总人数}1.创建家谱创建家谱方法按照二叉树的先序遍历顺序生成家谱二叉链表，因此先将成员对象按二叉树的先序遍历序列存入List集合作为构建二叉链表的数据来源，注意叶子结点和单分支结点，它们的孩子用null补齐。对于由上图所示的二叉树，进入集合的序列是A、B、D、null、null、E、null、null、C、null、F、null、null。

典型工作任务7.3树软件代码设计publicFamilyNodeCreateFamilyTree(List<Member>memberList){FamilyNoderoot=null; if(memberList.get(index)!=null){ root=newFamilyNode(memberList.get(index)); index++; root.setLeftChild(CreateFamilyTree(memberList));//设置根结点的左子树 index++; root.setRightChild(CreateFamilyTree(memberList));//设置根结点的右子树 } returnroot; }2.查找成员查找成员方法，根据成员的姓名找到成员结点。查找时按中序遍历顺序依次访问二叉链表中的结点，结点中的姓名与查找姓名进行比较，查找成功后将结点作为方法值返回。可以自行测试其他两种遍历方式查找。

典型工作任务7.3树软件代码设计publicFamilyNodemidOrderSearch(FamilyNoderoot,Stringname){ if(root==null){ returnnull; } FamilyNodeleftChild=midOrderSearch(root.getLeftChild(),name); if(leftChild!=null)returnleftChild; if(root.getData().name.equals(name))returnroot; FamilyNoderightChild=midOrderSearch(root.getRightChild(),name); if(rightChild!=null)returnrightChild; returnnull; }3.输出家谱输出家谱，就是把二叉链表中的数据按树形输出显示。按中序遍历顺序访问二叉链表中各结点，并依次输出。输出时结点处于哪一层，在成员姓名前输出几个’\t’形成缩进，这样就打印输出了树形结构。

典型工作任务7.3树软件代码设计publicvoidprintTree(FamilyNodenode,intlevel){ if(node!=null){ printTree(node.getLeftChild(),level+1); for(inti=0;i<level;i++){ System.out.print("\t"); } System.out.println(node.getData().name); printTree(node.getRightChild(),level+1); } }4.统计没有孩子的成员查询家族中没有孩子的成员，就是查找家谱二叉链表中所有的叶子结点。遍历每个结点，如果左孩子和右孩子都为空，即输出该结点的成员姓名，并统计这种结点的数量。

典型工作任务7.3树软件代码设计publicintgetLeaf(FamilyNodenode){ if(node==null){ return0; }/如果是叶子节点，输出成员姓名 if(node.getLeftChild()==null&&node.getRightChild()==null){ System.out.println("姓名:"+node.getData().name); return1; }else{ returngetLeaf(node.getLeftChild())+getLeaf(node.getRightChild()); } }5.统计第n代人的数量统计家族二叉链表中处于第n层的成员信息及总数量。结点中成员信息里包含第几代的值，统计方法通过参数接收层数n，遍历二叉链表中结点，找到满足条件的成员输出姓名并统计数量。

典型工作任务7.3树软件代码设计publicintgetGenerationCount(FamilyNodenode,intn){ if(node==null){ return0; } if(node.getData().generation==n){//如果是满足条件的结点，输出结点中成员姓名 System.out.print(node.getData().name+","); return1; }else{ returngetGenerationCount(node.getLeftChild(),n)+getGenerationCount(node.getRightChild(),n); }}6.统计成员总人数统计家谱中的总人数，是统计家谱二叉链表中的结点总数。

典型工作任务7.3树软件代码设计publicintgetSize(FamilyNodenode){ if(node==null){ return0; }else{ return1+getSize(node.getLeftChild())+getSize(node.getRightChild()); }}7.3.4系统测试类的实现1.系统主框架

典型工作任务7.3树软件代码设计publicstaticvoidmain(String[]args){ FamilyTreetree=newFamilyTree();//创建空链表 Scannerscan=newScanner(System.in); intxz; do{ menu();//调用主菜单 System.out.println("请选择："); xz=scan.nextInt(); switch(xz){ case1://创建家谱 create(tree); break; case2://输出家谱 tree.printTree(tree.root,0); break; case3://编辑家谱 edit(tree); break; case4://统计 total(tree); break; } }while(xz!=0); System.out.println("谢谢使用，再见！"); } 2.主菜单显示

典型工作任务7.3树软件代码设计publicstaticvoidmenu(){ System.out.println("===========家族族谱系统==========="); System.out.println("\t1创建家谱"); System.out.println("\t2显示家谱"); System.out.println("\t3编辑家谱"); System.out.println("\t4统计"); System.out.println("\t0退出"); System.out.println("==============================="); }

3.创建家谱创建家谱二叉链表前，先准备数据。依据原始数据画出二叉树，创建每个成员对象，按先序遍历序列将家族成员对象添加到List集合中，创建叶子结点和单分支结点时，它们的孩子用null补齐。tree调用FamilyTree类中的CreateFamilyTree(List<Member>memberList)方法，将成员集合传给该方法，该方法将成员对象封装成结点对象，按先序遍历顺序将结点加入二叉链表。成员进入集合的顺序是：王树、王健、王奇、null、null、王力、null、null、王康、null、王宁、null、null。

典型工作任务7.3树软件代码设计

典型工作任务7.3树软件代码设计publicstaticvoidcreate(FamilyTreetree){ List<Member>memberList=newArrayList<Member>(); memberList.add(newMember("王树",70,1)); memberList.add(newMember("王健",48,2)); memberList.add(newMember("王奇",24,3)); memberList.add(null); memberList.add(null); memberList.add(newMember("王力",22,3)); memberList.add(null); memberList.add(null); memberList.add(newMember("王康",49,2)); memberList.add(null); memberList.add(newMember("王宁",20,3)); memberList.add(null); memberList.add(null); tree.root=tree.CreateFamilyTree(memberList); System.out.println("创建成功！"); }

4.显示家谱tree对象直接调用FamilyTree类中的printTree(FamilyNodenode,intlevel)方法，该方法按中序遍历访问各结点，并将结点中成员姓名按二叉树形状输出到界面。tree对象调用printTree()成员方法，二叉树的根和根结点的层数0作为实参传入。5.编辑家谱编辑家谱中包含3个功能，查找成员、修改成员信息和添加新成员。所以需要实现二级菜单，供用户进行选择操作。需要结束编辑操作时，输入菜单项0返回主菜单。

典型工作任务7.3树软件代码设计tree.printTree(tree.root,0);

典型工作任务7.3树软件代码设计publicstaticvoidedit(FamilyTreetree){ intxz; Scannerscan=newScanner(System.in); do{ System.out.println("-