数据结构(树)

函数递归在树形结构数据遍历中的应用

函数递归在树形结构数据遍历中的应用 我们在使用树形结构数据时，常常需要遍历整棵树或某一支下的所有结点，用于查找、打印等功能。因为树形结构不同于数组、链表等简单数据结构，它像树枝一样每个根结点可以具有多个子结点，无限延展，因此需要专门的算法去遍历。树形结构的遍历有很多种方法，下面我们以紫金桥监控组态软件(以下简称为“RealInfo”)为例，简单讲解函数递归在这种遍历方法中的应用。 在RealInfo中，“树形控件”是表示树状结构数据的组件，“自由报表”是表示表格数据的组件，这两种组件自身都提供了一些常用方法。我们现在实现这样的功能：将树形控件中的指定分支数据打印在自由报表中。可以利用窗口自定义函数的递归功能。 树形控件中的数据显示方式如下图所示： 每个结点以结点编码为唯一标识，每个结点可以显示一个字符串作为结点文本（详见RealInfo联机帮助）。 本例中，我们将树形结构数据打印在自由报表上，其效果如下图所示： 每个根结点打印完成后，遇到子结点时打印位置自动向右、向下移动一个单元格；遇到兄弟结点时打印位置向下移动一个单元格。 现在我们开始分析算法。我们知道，树的遍历是指沿着某条搜索路线，依次对树中每个

结点均做一次且仅做一次访问。这样，我们把遍历过程想象成为一次单程旅行，出发点是树的根结点，然后按先自左向右、然后自上而下的顺序，先后经过每个结点，最后走到最下方的叶子结点处。 我们可以采用这样的遍历方式： 1)当所在结点具有子结点时，那么按自左向右原则，接着访问它的第一个子结点，直到所 在结点没有子结点为止。 2)当所在结点没有子结点，但具有兄弟结点时，那么按自上向下原则依次访问它的兄弟结 点。 3)当所在结点没有子结点，而且没有兄弟结点时，那么按自上向下原则访问它父结点的兄 弟结点。 分析这个过程并观察树形结构，我们会发现，每个父结点可以拥有n(n>=0)个子结点，若将这n个子结点看作父结点，则每个父结点仍然具有n个子结点。由此看来，每一支数据乃至整棵树都可以看作是有限个父-子结构的组合。在树的遍历过程中，总是不断的重复“父→子”这一访问方式，因此我们可以提取这一方式形成一个函数，并利用函数递归来完成整个遍历。 这个函数用于根据输入的父结点编码和起始打印位置将其所有子结点打印出来。算法如下：

数据结构树的有关算法

《数据结构》课程设计任务书 学期：11-12-2 班级：网络10 一、设计目的 《数据结构》是一门实践性较强的专业基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 二、设计要求 1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 2、学生必须仔细研读《数据结构》课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。 3、本次课程设计按照教学要求需要在一周半时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。 4、编程语言任选。 三、设计选题 题一：线索二叉树（**） 任务： 1.建立中序线索二叉树，并且中序遍历； 2.求中序线索二叉树上已知结点中序的前驱和后继； 需求分析和概要设计： 建立中序线索二叉树，并且中序遍历。首先就是要建立树，再将树中序线索化。求中序线索二叉树上已知结点中序的前驱和后继时，即是将树在遍历一遍。也可以在遍历的过程中，将树的结点放在数组中，当然必须讲述先遍历一遍，这是用空间来换时间。 详细设计： 树的结构体的声明： typedef char TElemtype; typedef enum PointerTag{Link,Thread}; //设置标志：Link为指针，Thread为线索typedef struct BiThrNode{ //树结点结构体 TElemtype data; struct BiThrNode *lchild,*rchild; PointerTag LTag,RTag; }BiThrNode,*BiThrTree; 相关函数的声明：

数据结构——二叉树的操作(遍历及树形输出)

/*实验三：二叉树遍历操作验证*/ #include #include #include #include #include

if(T) //若非空 { if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); } } //递归方法中序遍历二叉树 void inOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->rchild); } } //递归方法后序遍历二叉树 void postOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); if(T->data) { //输出 printf("%c",T->data); } } } //层序遍历二叉树 void LevelTraverse(BiTree T) { queue q;//建队 q.push(T);//根节点入队

数据结构树的实现实验报告

数据结构设计性实验报告 课程名称_____ ____ 题目名称 学生学院 专业班级 学号 学生姓名 指导教师 2010 年 7 月 6 日

抽象数据类型：树的实现 一．需求分析 树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的内部结构。树的结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得广泛应用，如在编译程序中，可用树来表示源程序的语法结构，又如在数据库系统中，树形结构也是信息的重要组织形式之一。 二．实验目的 对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。 三．实验环境 1、硬件：PC机 2、软件：Microsoft Visual C++ 6.0 四．设计说明 本程序采用树的二叉链表（孩子指针-兄弟指针-双亲指针）存储表示，以下是树的结构定义和基本操作： ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3, …,Dm(m>0)，对于任意j ≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有∈H; (3) 对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1，H2,…,Hm(m>0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),Hi是Di 上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。 基本操作P： InitTree(&T); 操作结果：构造空树T。 DestroyTree(&T); 初始条件：树T存在。 操作结果：销毁树T。 CreateTree(&T,definition); 初始条件：definition给出树T的定义。 操作结果：按definition构造树T。 ClearTree(&T);

java递归树型结构通用数据库

表结构 /** * 删除部门删除时从选中级的所有子级 * * @param dept * @return */ public JsonResult delDept(Dept dept) { JsonResult jr = new JsonResult(); Boolean flags=true; try { String str = ""; User user=new User(); List sortList = new ArrayList(); sortList.add(dept); getDeptSortList(sortList,dept.getId()); //起始根节点id，等级为0 for(Dept bean: sortList){ user.setDeptId(bean.getId()); //判断部门下面是否有用户 List users =userDao.getByDeptIdIsUerOrNO(user); int userSize=users.size(); if(userSize>0){ jr.setMessage("部门名称：(" + users.get(0).getDeptName() + ")已有用户不能删除"); flags=false;

break; } } //部门没有被用户使用时才可以册子 if(flags){ for(Dept bean: sortList){ dept.setId(bean.getId()); deptDao.delDept(dept); jr.setMessage(SuccessMessageEnum.detele.toDescription()); } } jr.setSuccess(true); } catch (Exception e) { log.error("DeptServiceImpl-->delDept:" + e.getMessage()); jr.setCode(ExceptionEnum.SystemError.toCode()); jr.setMessage(e.getMessage()); } return jr; } /** * 删除时递归部门树 * * @param * @return */ public void getDeptSortList(List sortDeptList,Integer parentId)throws Exception { Dept bean = null; //根据选中的部门id得到本部门和第一级所有的子部门的id List deptslist=deptDao.getByDeptIdAllSubDeptId(parentId); //;//每次查询出上级为的分类 // int deptSize=deptslist.size(); if(deptslist.size() > 0){ for(int i=0;i select id from report_sys_dept where parent_id=#value#

数据结构-树练习题

数据结构－树练习题 一、选择题 1、二叉树的深度为k，则二叉树最多有（ C ）个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1 2、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。 A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。 A. adbce B. decab C. debac D. abcde 5、在一棵具有5层的满二叉树中结点总数为（ A ）。 A. 31 B. 32 C. 33 D. 16 6、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。 A. 能 B. 不能 7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。 A. 3 B. 2 C. 4 D. 5 8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。 A. 67 B. 68 C. 69 D. 70 9、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。 A. 98 B. 99 C. 50 D. 48 10、表达式a*(b+c)-d的后缀表达式是（ B ）。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、树最适合用来表示（ C ）。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 13、表达式A*(B+C)/(D-E+F)的后缀表达式是（ C ） A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+ 14、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 15、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（）个。 A. 15 B. 16 C. 17 D. 47 16、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 A. 51 B. 23 C. 53 D. 74

数据结构：树形结构完整代码,各种遍历方法,直接能跑

#include #include #define TElemType int typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; typedef BiTree DataType; typedef struct queuenode{ DataType data; struct queuenode *next; } QueueNode; //LINKQUEUE //HEAD POINTER, AND REAR POINTER ARE A V ALIBALE typedef struct { QueueNode *front; QueueNode *rear; } LinkQueue; int InitQueue(LinkQueue *Q); int DestroyQueue(LinkQueue *Q); int QueueEmpty(LinkQueue Q); int EnQueue(LinkQueue *Q, DataType e); DataType DeQueue(LinkQueue *Q); int CreateBiTree(BiTree *T); int PreOrderTraverse(BiTree T, int (*visit)(TElemType e)); int PreOrderTraverse2(BiTree T, int (*visit)(TElemType e)); int InOrderTraverse(BiTree T, int (*visit)(TElemType e)); int InOrderTraverse2(BiTree T, int (*visit)(TElemType e)); int PostOrderTraverse(BiTree T, int (*visit)(TElemType e)); int PostOrderTraverse2(BiTree T, int (*visit)(TElemType e)); int LevelOrderTraverse(BiTree T, int (*visit)(TElemType e)); int printElem(TElemType e); int InitBiTree(BiTree *T); int DestroyBiTree(BiTree *T); int ClearBiTree(BiTree *T); int BiTreeEmpty(BiTree T); int BiTreeDepth(BiTree T);

树在数据结构中的简单应用

题目：树在数据结构中的简单应用树在数据结构中的简单应用

Simple Application of Tree In Data-structure 摘要 树形结构是一类重要的非线性结构.本文研究了树形数据结构的基础知识，包括相关定义、操作以及树在数据结构中的简单应用问题.主要运用图示以及相关的算法来研究树以及树在数据结构中的若干应用问题，如在编码问题中的应用、在查找算法中的应用等. 关键词:树;二叉树;数据结构;树的应用

ABSTRACT The construction of tree form is an important construction of not line. In this paper, we research the base knowledge of tree including some correlation definition, operation and the simple application of tree in data structure. We research tree and some application of tree in data structure by diagram and some correlative arithmetic, for example, in coding, in arithmetic and so on. Key words : Tree, Tree of two fork; Data construction; The tree's application 目录

树在数据结构中的简单应用

题目：树在数据结构中的简单应用

树在数据结构中的简单应用 Simple Application of Tree In Data-structure 摘要 树形结构是一类重要的非线性结构.本文研究了树形数据结构的基础知识，包括相关定义、操作以及树在数据结构中的简单应用问题.主要运用图示以及相关的算法来研究树以及树在数据结构中的若干应用问题，如在编码问题中的应用、在查找算法中的应用等.

关键词:树;二叉树;数据结构;树的应用 ABSTRACT The construction of tree form is an important construction of not line. In this paper, we research the base knowledge of tree including some correlation definition, operation and the simple application of tree in data structure. We research tree and some application of

tree in data structure by diagram and some correlative arithmetic, for example, in coding, in arithmetic and so on. Key words : Tree, Tree of two fork; Data construction; The tree's application 目录 摘要 (Ⅰ)

数据结构—— 树和二叉树知识点归纳

第6章树和二叉树 6.1 知识点概述 树（Tree）形结构是一种很重要的非线性结构，它反映了数据元素之间的层次关系和分支关系。在计算机科学中具有广泛的应用。 1、树的定义 树（Tree）是n（n≥0）个数据元素的有限集合。当n＝0时，称这棵树为空树。在一棵非空树T中： （1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。 （2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。 2、树的基本存储结构 （1）双亲表示法 由于树中的每一个结点都有一个唯一确定的双亲结点，所以我们可用一组连续的 存储空间（即一维数组）存储树中的结点。每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。 （2）孩子表示法 将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单 链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。 （3）双亲孩子表示法 双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。 （4）孩子兄弟表示法 这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。 3、二叉树的定义 二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 4、满二叉树 定义：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 5、完全二叉树 定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。 6、二叉树的性质

[TREE]采用左右值编码来存储无限分级树形结构的数据库表设计

采用左右值编码来存储无限分级树形结构的数据库表设计 之前我介绍过一种按位数编码保存树形结构数据的表设计方法，详情见：浅谈数据库设计技巧(上) 该设计方案的优点是：只用一条查询语句即可得到某个根节点及其所有子孙节点的先序遍历。由于消除了递归，在数据记录量较大时，可以大大提高列表效率。但是，这种编码方案由于层信息位数的限制，限制了每层能所允许的最大子节点数量及最大层数。同时，在添加新节点的时候必须先计算新节点的位置是否超过最大限制。 上面的设计方案必须预先设定类别树的最大层数以及最大子节点数，不是无限分级，在某些场合并不能采用，那么还有更完美的解决方案吗？通过google的搜索，我又探索到一种全新的无递归查询，无限分级的编码方案——左右值。原文的程序代码是用php写的，但是通过仔细阅读其数据库表设计说明及相关的sql语句，我彻底弄懂了这种巧妙的设计思路，并在这种设计中新增了删除节点，同层平移的需求（原文只提供了列表及插入子节点的sql语句）。 下面我力图用比较简短的文字，少量图表，及相关核心sql语句来描述这种设计方案： 首先，我们弄一棵树作为例子： 商品 |---食品 | |---肉类 | | |--猪肉 | |---蔬菜类 | |--白菜 |---电器 |--电视机 |--电冰箱

select count(*) from tree where lft <= 2 and rgt >= 11 为了方便列表，我们可以为tree表建立一个视图，添加一个层数列，该类别的层数可以写一个自定义函数来计算。该函数如下： CREATE FUNCTION dbo.CountLayer ( @type_id int ) RETURNS int AS begin declare@result int set@result=0 declare@lft int declare@rgt int if exists (select1from tree where type_id=@type_id) begin select@lft=lft,@rgt=rgt from tree where type_id=@type_id select@result=count(*) from tree where lft <=@lft and rgt >=@rgt end return@result end GO 然后，我们建立如下视图： CREATE VIEW dbo.TreeView AS SELECT type_id, name, lft, rgt, dbo.CountLayer(type_id) AS layer FROM dbo.tree ORDE R BY lft GO

数据结构习题 树 数据机构c语言版

1.设二叉树bt 的存储结构如下，其中bt为树根结点指针，left，right分别为结 点的左、右孩子指针，dada为结点的数据域。请完成下列各题： 1）画出二叉树bt的逻辑结构 2）写出按先序、中序、后序遍历二叉树所得到的结点序列 3）画出二叉树bt的后序线索化树 1 2 3 4 5 6 7 8 9 10 2.二叉树结点数值采用顺序存储结构，如图所示， 1）画出二叉树表示 2）写出前序遍历，中序遍历和后序遍历的结果 3）写出结点值c的父结点，其左、右孩子。 4）画出将此二叉树还原成森林的图

3.已知一棵二叉树的中序序列为cbedahgijk，后序序列为cedbhjifa，画出该二叉 树的先序线索二叉树。 4.有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、 2、9，试画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点 的权的次序构造），求出每个字符的Huffman编码。 5.设给定权集w={2，3，4，8，9}，试构造关于w的一棵哈夫曼树，并求其加权路 径长度WPL。 6.假设二叉树采用链接存储方式存储，编写一个中序遍历二叉树的非递归过程。 7.假设二叉树采用链接存储方式存储，root指向根结点，p所指结点为任一给定的 结点。编写一个求出从根结点到p所指结点之间路径的函数。 8.在二叉树中查找值为x的结点，试设计打印值为x的结点的所有祖先的算法，假 设值为x的结点不多于1个。 9.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的所有 结点数。 10.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的单孩 子结点数。

常用数据库的树形查询

常用数据库的树形查询 在ORACLE、MSSQL、MYSQL中树结构表递归查询的实现方法 表recursion数据如下: id name parentid 1 食品分类 -1 2 肉类 1 3 蔬菜类 1 4 产品分类 -1 5 保健品 4 6 医药 4 7 建筑 4 一ORACLE中实现方法: Oracle中直接支持,使用语句select * from tablename start with connect by prior id(子层的列)=parentid(属于顶层的列) 语句说明: start with 指定层次开始的条件，即满足这个条件的行即可以作为层次树的最顶层 connect by prior指层之间的关联条件，即什么样的行是上层行的子行（自连接条件） 实例: select * from recursionstart with connect by prior>查询结果: id name parentid 1 食品分类 -1 2 肉类 1 3 蔬菜类 1 二MSSQL中的实现方法 在MSSQL中需要使用临时表和循环多次查询的方式实现. 创建函数: create function GetRecursion(@id int) returns @t table( idint, namevarchar(50), parentidint ) as begin insert @tselect * from recursion where> while @@rowcount>0 insert @t select a.* from recursion as a inner join @t as b on a.parentid=b.id and a.id not in(select id from @t) return end 使用方法:

树形结构数据表的设计

树形结构的数据库表Schema设计 程序设计过程中，我们常常用树形结构来表征某些数据的关联关系，如企业上下级部门、栏目结构、商品分类等等，通常而言，这些树状结构需要借助于数据库完成持久化。然而目前的各种基于关系的数据库，都是以二维表的形式记录存储数据信息，因此是不能直接将Tree 存入DBMS，设计合适的Schema及其对应的CRUD算法是实现关系型数据库中存储树形结构的关键。 理想中树形结构应该具备如下特征：数据存储冗余度小、直观性强；检索遍历过程简单高效；节点增删改查CRUD操作高效。无意中在网上搜索到一种很巧妙的设计，原文是英文，看过后感觉有点意思，于是便整理了一下。本文将介绍两种树形结构的Schema设计方案：一种是直观而简单的设计思路，另一种是基于左右值编码的改进方案。 一、基本数据 本文列举了一个食品族谱的例子进行讲解，通过类别、颜色和品种组织食品，树形结构图如下：

二、继承关系驱动的Schema设计 对树形结构最直观的分析莫过于节点之间的继承关系上，通过显示地描述某一节点的父节点，从而能够建立二维的关系表，则这种方案的Tree表结构通常设计为：{Node_id,Parent_id}，上述数据可以描述为如下图所示： 这种方案的优点很明显：设计和实现自然而然，非常直观和方便。缺点当然也是非常的突出：由于直接地记录了节点之间的继承关系，因此对Tree的任何CRUD操作都将是低效的，这主要归根于频繁的“递归”操作，递归过程不断地访问数据库，每次数据库IO都会有时间开销。当然，这种方案并非没有用武之地，在Tree规模相对较小的情况下，我们可以借助于缓存机制来做优化，将Tree的信息载入内存进行处理，避免直接对数据库IO操作的性能开销。 三、基于左右值编码的Schema设计 在基于数据库的一般应用中，查询的需求总要大于删除和修改。为了避免对于树形结构查询时的“递归”过程，基于Tree的前序遍历设计一种全新的无递归查询、无限分组的左右值编码方案，来保存该树的数

数据结构第三章 树 答案

数据结构与算法上机作业第三章树

一、选择题 1、在一棵树中，如果结点A有3个兄弟，B是A的双亲，则B的度为 D A. 1 B. 2 C. 3 D. 4 2、深度为h的完全二叉树至少有 D 个结点，至多有 B 个结点 A. 2h B. 2h-1 C. 2h+1 D. 2h-1 3、具有n个结点的满二叉树有 C 个叶结点。 A. n/2 B. (n-1)/2 C. (n+1)/2 D. n/2+1 4、一棵具有25个叶结点的完全二叉树最多有 C 个结点。 A. 48 B. 49 C. 50 D. 51 5、已知二叉树的先根遍历序列是ABCDEF，中根遍历序列是CBAEDF，则后根遍历序列 是 A 。 A. CBEFDA B. FEDCBA C. CBEDFA D. 不定 6、具有10个叶结点的二叉树中有 B 个度为2的结点。 A. 8 B. 9 C. 10 D. 11 7、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满 足 C 。 A. 所有非叶结点均无左孩子 B. 所有非叶结点均无右孩子 C. 只有一个叶子结点 D. A和B同时成立 8、在线索二叉树中，t所指结点没有左子树的充要条件是 B 。 A. t->left=NULL B. t->ltag=TRUE C. t->ltag=TRUE且t->left=NULL D. 以上都不对 9、n个结点的线索二叉树上含有的线索数为 C 。 A. 2n B. n-1 C. n+1 D. n 10、二叉树按照某种顺序线索化后，任一结点都有指向其前驱和后继的线索，这种说法 B 。 A. 正确 B. 错误 C. 不确定 D. 都有可能 11、具有n(n>1)个结点的完全二叉树中，结点i(2i>n)的左孩子结点是 D 。 A. 2i B. 2i+1 C. 2i-1 D. 不存在 12、具有64个结点的完全二叉树的深度为 C 。 A. 5 B. 6 C.7 D. 8 13、将一颗有100个结点的完全二叉树从上到下、从左到右一次对结点进行编号，根结点的编号为1，则编号为45的结点的右孩子的编号为 D 。 A. 46 B. 47 C. 90 D. 91 14、在结点数为n的堆中插入一个结点时，复杂度为 C 。 A. O(n) B. O(n2) C. O(log2n) D. O(log n2) 15、两个二叉树是等价的，则它们满足 D 。 A. 它们都为空 B. 它们的左右子树都具有相同的结构 C. 它们对应的结点包含相同的信息 D. A、B和C 16、包含n个元素的堆的高度为 C 。（符号「a表示取不小a最小整数） A. n B. 「log2n C. 「log2(n+1) D. n+1 17、以下说法错误的是 B 。 A. 存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同 B. 二叉树是树的特殊情形

数据结构_树的深度

建立树的存储结构 求树的深度 */ 1.源程序： #include #include #define MAX 100 typedef struct CSNode{ //树 char data; struct CSNode *firstchild, *nextsibling; }CSNode; typedef struct { CSNode* *elem; int front; int rear; }LinkQueue; void InitQueue(LinkQueue &Q){ Q.elem=(CSNode **)malloc(MAX*sizeof(CSNode)); Q.front=Q.rear=0; } CSNode* EnQueue(LinkQueue &Q,CSNode *p) { if(Q.front==Q.rear) Q.elem[Q.front]=p; Q.rear++; Q.elem[Q.rear]=p; return p; } CSNode* DeQueue(LinkQueue &Q,CSNode *p) { p=Q.elem[Q.front]; Q.front++; return p; } CSNode* GetHead(LinkQueue Q,CSNode *p){ if(Q.rear != Q.front) p=(Q.elem[Q.front]); else p=NULL; return p;

int TreeDepth(CSNode *T) { if(!T) return 0; else { int h1 = TreeDepth( T->firstchild ); int h2 = TreeDepth( T->nextsibling); return( (h1+1>h2)? h1+1: h2); } } CSNode* GetTreeNode(char c){ CSNode *C; C=(CSNode *)malloc(sizeof(CSNode)); C->data=c; C->firstchild=NULL; C->nextsibling=NULL; return C; } void Preorder(CSNode *T) //先序遍历 { if (T){ printf("%c\t",T->data); // 访问结点 Preorder(T->firstchild); // 遍历左子树 Preorder(T->nextsibling); // 遍历右子树 } } CSNode * CreatTree( CSNode *T ) { char ch,fa; LinkQueue Q; InitQueue(Q); CSNode *p,*r,*s; p=(CSNode *)malloc(sizeof(CSNode)); r=(CSNode *)malloc(sizeof(CSNode)); s=(CSNode *)malloc(sizeof(CSNode)); printf("请输入树的序列：\n"); scanf("%c %c",&fa,&ch); while( ch!='0'){ p = GetTreeNode(ch); // 创建结点 p=EnQueue(Q, p); // 指针入队列 if (fa == '#') T = p; // 所建为根结点 else {

树形结构数据排序算法

需求是把数组按照树形结构排列，假设数据是在数据库中的。 最简单的思路或者说常规的思路就是递归算法了。递归算法是比较快的和准确的，但是有一个问题就是会比较浪费不必要的资源，递归算法执行的过程中会开启 N个函数入口，也就是函数需要一直保存状态等待起递归的运算结果。例如这 个树形有 5层*60行，则在递归算法中浪费的运算至少60次，并且保持5个函 数一直是运算中状态，不合理的是同样要做60+次的数据库查询，因为不管其有没有子类，算法执行过程中都需要去重复执行递归运算，事实上实际执行过程 中不止这个数。 可以写个简单的例子来测试递归算法调用函数的次数。 /* 先假设我的数据是这样子的 array( array(id=>1,pid=>0), array(id=>2,pid=>0), array(id=>3,pid=>2), array(id=>4,pid=>0), array(id=>5,pid=>3), array(id=>6,pid=>1), array(id=>7,pid=>1), array(id=>8,pid=>6), array(id=>9,pid=>7), array(id=>10,pid=>9) ); */ $db = new MysqlDb(); $num = 0; function treeArray($pid) { global $db, $num; $num++; $data = $db ->getAll("SELECT * FROM test_a WHERE pid = ".$pid); //返回一个二维数组 $result = array(); foreach($data as $val) { $val['child'] = treeArray($val['id']); $result[] = $val; } return $result; } print_r(treeArray(0)); //树形的结果 var_dump($num); //11 然后我们系统越作越大了，数据库资源紧张了，我们要求在不改变数据库结构的同时尽可能 的减少数据库的操作。那么这样做就需要我们有一算法来给你的数据排序了。

数据结构树和二叉树习题及答案

习题六树和二叉树 一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋 B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（） A．借助二叉树上的运算方法去实现对树的一些运算 B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 13．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（）。 A．acbed B．decab C．deabc D．cedba