当前位置：文档库 › 二叉树

二叉树

1、一棵完全二叉树共有360个结点，则在该二叉树中度为1的结点个数为______。

本题考查知识点是二叉树基本性质。

完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。根据二叉树性质，设完全二叉树共有n个结点。如果从根节点开始，按层序（每一层从左到右）用自然数1，2……，n给结点进行编号，则对于编号为k的结点有如下结论。

若k=1，则该结点为根结点。若k>1，则该结点的父结点编号为INT(k/2)，其中INT表示取整意思。最后一个结点360的父结点编号为180。若2k<=n，则编号为k 的结点的左结点编号为2k，否则该结点无左子结点（显然也没有右子结点）。若2k+1<=n，则编号为k的结点的右子结点编号为2k+1，否则该结点无右子结点。在本题中，2*180<=360，条件满足，故该结点无左子结点，由于该二叉树是完全二叉树，显然180是最后一个父结点，且没有右子结点。

所以本题答案为B。

2、设二叉树共有150个结点，其中度为1的结点有10个，则该二叉树中的叶子结点数为______。

本题考查知识点是二叉树性质。

任意一颗二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。可以设度为0的结点数问n，则度为2的结点数为n-1，根据题意可得n+n-1+10=150，n不是整数，故不可能有这样的二叉树。

所以本题答案为C。

3、某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为（根结点在第1层）______。

本题考查知识点是二叉树。

在任意一颗二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。叶子结点只有一个，即没有度为2的结点，这样度为1的结点就是11个。每一层有一个结点，故深度为12。

所以本题答案为A。

4、本题考查知识点是完全二叉树的性质。

完全二叉树的总结点为奇数时，叶子结点数是总结点加一再除以2。

所以本题答案为B。

深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为

______。

5、设二叉树如下：

则后序序列为______。

C、DGEBHFCA

7、

数据结构二叉树习题含答案

2.1 创建一颗二叉树创建一颗二叉树，可以创建先序二叉树，中序二叉树，后序二叉树。我们在创建的时候为了方便，不妨用‘#’表示空节点，这时如果先序序列是：6 4 2 3 # # # # 5 1 # # 7 # #，那么创建的二叉树如下：下面是创建二叉树的完整代码：穿件一颗二叉树，返回二叉树的根 2.2 二叉树的遍历二叉树的遍历分为：先序遍历，中序遍历和后序遍历，这三种遍历的写法是很相似的，利用递归程序完成也是灰常简单的： 2.3 层次遍历层次遍历也是二叉树遍历的一种方式，二叉树的层次遍历更像是一种广度优先搜索（BFS）。因此二叉树的层次遍历利用队列来完成是最好不过啦，当然不是说利用别的数据结构不能完成。 2.4 求二叉树中叶子节点的个数树中的叶子节点的个数= 左子树中叶子节点的个数+ 右子树中叶子节点的个数。利用递归代码也是相当的简单， 2.5 求二叉树的高度求二叉树的高度也是非常简单，不用多说：树的高度= max(左子树的高度，右子树的高度) + 1 2.6 交换二叉树的左右儿子交换二叉树的左右儿子，可以先交换根节点的左右儿子节点，然后递归以左右儿子节点为根节点继续进行交换。树中的操作有先天的递归性。。 2.7 判断一个节点是否在一颗子树中可以和当前根节点相等，也可以在左子树或者右子树中。 2.8 求两个节点的最近公共祖先求两个节点的公共祖先可以用到上面的：判断一个节点是否在一颗子树中。（1）如果两个节点同时在根节点的右子树中，则最近公共祖先一定在根节点的右子树中。（2）如果两个节点同时在根节点的左子树中，则最近公共祖先一定在根节点的左子树中。（3）如果两个节点一个在根节点的右子树中，一个在根节点的

数据结构：二叉树子系统

/* *题目：按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构。 * 编写前序遍历、中序遍历、后序遍历、层次遍历程序。 * 编写求二叉树的叶结点数、总结点数和深度的程序。 * 设计一个选择式菜单，以菜单方式选择下列操作。 * 二叉树子系统 * *************************** **** * * 1 -- 建二叉树* * * 2 -- 凹入显示* * * 3 -- 先序遍历* * * 4 -- 中序遍历* * * 5 -- 后序遍历* * * 6 -- 层次遍历* * *7 -- 求叶子数* * *8 -- 求结点数* * *9 -- 求树深度* * *0 -- 返回* * *************************** **** * 请选择菜单号（0--9） */ #include #include typedef struct bTree // 二叉树结点{ char data; // 值域 struct bTree *lchild; // 左孩子 struct bTree *rchild; // 右孩子 }BT; BT *createTree(); void showTree(BT *t); void preOrder(BT *t); void postOrder(BT *t); void inOrder(BT *t); void levelOrder(BT *t); int leafNum(BT *t); int nodeNum(BT *t); int treeDepth(BT *t); /************************************************* Function: main() Description: 主调函数 Calls: createTree() showTree() preOrder() postOrder() in Order() leafNum() levelOrder() no deNum() treeDepth() In put: NULL

基于matlab构造最优二叉树

摘要 Matlab是一种用于算法开发,数据可视化，数据分析以及数值计算的高级技术计算语言和交互式环境。MATLAB是当今最优秀的科技应用软件之一，利用MATLAB 对层次分析法的判断、分析和计算过程进行处理后，为决策者提供方便友好的对话界面。只要决策者在MATLAB软件中输入自己的层次结构方案和两两对比的判断矩阵后能迅速得出相应的结果，为解决实际问题提供一个快捷的方法。从而提高人们的决策效率，同时也为科技工作者使用层次分析法提供一种新思路。本文是利用matlab的强大功能来构造最优二叉树。二叉树是一种非常重要以及常见的数据结构，不仅在计算机系统中运用广泛，而且在日常生活中也有一定的应用。本文概述了二叉树的数据结构以及使用matlab来模拟出二叉树的数据结构，从而来实现二叉树的插入，删除，查询等常用功能。关键词：Matlab；二叉树；数据结构；

ABSTRACT Matlab is used for algorithm development, data visualization, data analysis and numerical calculation of the senior technical computing language and interactive environment. Matlab is the most outstanding application of science and technology, using MATLAB to determine the right level of analysis, analysis and computation processing, in order to provide decision makers with convenient user-friendly dialog interface. When the decision-makers in MATLAB software, enter their own hierarchy of the program and judgment matrix to determine quickly after the corresponding results obtained, in order to solve practical problems to provide a quick method. Thereby enhancing the efficiency of people's decision-making, but also for the scientific and technological workers to use AHP to provide a new idea.This article is using matlab to construct optimal binary tree. Binary Tree is a very important and common data structures, it is widely used in the computer system. This article outlines the binary tree data structure and the use of matlab to simulate a binary tree data structure, in order to achieve the binary tree insertion, deletion, query and other commonly used functions. Key words：Matlab；binary tree；data struction；

二叉树遍历方法技巧

二叉树遍历方法 1.中序遍历的投影法如果给定一棵二叉树的图形形态，是否能根据此图快速地得出其中序遍历的序列？回答是肯定的。具体做法是：首先按照二叉树的标准绘制二叉树形态，即将所有左子树都严格绘于根结点的左边；将所有右子树都严格绘于根结点的右边。然后假设现在有一个光源从该二叉树的顶部投射下来，那么所有结点在地平线上一定会有相应的投影，从左至右顺序读出投影结点的数据即为该二叉树的中序遍历序列。如图11.10所示。图示的中序遍历序列： D J G B H E A F I C 2.先序遍历的填空法如果给定一棵二叉树的图形形态，可在图形基础上，采用填空法迅速写出该二叉树的先序遍历序列。具体做法是：我们知道，对于每个结点都由三个要素组成，即根结点，左子树、右子树；又已知先序遍历顺序是先访问根结点、然后访问左子树、访问右子树。那么，我们按层分别展开，逐层填空即可得到该二叉树的先序遍历序列。图11.10 中序遍历投影法示意图如图11.10 中的二叉树采用填空法的步骤如下： (1)根结点左子树右子树 A( )( ) (2)A （根结点（左子树）（右子树））（根结点（左子树）（右子树）） A B C (3)A(B(根结点（左）（右）)(根结点（左）（右）))（C(……)(……)） A B D 无 G E H 无 C F 无 (4)A B D G J E H C F I 此即为该二叉树的先序遍历序列。注：后序遍历的序列亦可以此方法类推，请读者自己尝试。

3.利用遍历序列构造二叉树如果已知一棵二叉树的先序遍历序列和中序遍历序列，则可以用这两个遍历序列构造一棵唯一的二叉树形态。我们知道任意一棵二叉树的先序遍历序列和中序遍历序列是唯一的，那么首先从给定的先序遍历序列入手，该先序序列的第一个元素一定是该二叉树的根；再分析这个根结点在中序遍历序列中的位置，中序遍历序列中根结点的左边即为左子树的全部元素，而根结点的右边即为右子树的全部元素；然后据此再将先序遍历序列除根结点以外的其余部分分为左、右子树两部分，并在这两部分中分别找出左、右子树的根结点。依此类推，即可得到完整的二叉树。例11.1 已知一棵二叉树的先序遍历和中序遍历序列分别为：先序： A B C I D E F H G 中序： C I B E D A H F G 请构造这棵二叉树。按前述分析，这棵二叉树的构造过程如图11.11所示图11.11 二叉树的构造过程树、森林与二叉树的转换(flash演示) 如前所述，树（或森林）的存储结构及其操作算法的实现，由于其“度”的不确定性而导致其存储结构不是较为复杂就是浪费空间，因而，定义在其存储结构上的算法也相应地较难兼顾全面。如果我们设定一定的规则，用二叉树来表示树和森林的话，就可以方便地解决树、森林的存储结构及其相关算法问题。 1.树、森林转换为二叉树我们知道，一棵树中每个结点的孩子是无序的，而二叉树中各结点的孩子必须有左右之分。在此，为避免概念混淆，首先约定树中每个结点的孩子按从左至右的顺序升序编号，即将树中同一层上的兄弟分出大小。那么将一棵树转换成二叉树的方法是：（1）在树中同层兄弟间加一连线；（2）对树中每个结点仅保留其与长兄（左边第一个孩子）的连线，擦去其与其它孩子的连线；（3）以树（或子树）的根作为轴心，将所有的水平连线顺时针旋转45度，即可得到与该树完全等价的一棵二叉树。

数据结构二叉树练习题答案

数据结构第6章树和二叉树一、下面是有关二叉树的叙述，请判断正误（√）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。 n个结点的二叉树有n-1条分支（×）2.二叉树中每个结点的两棵子树的高度差等于1。（√）3.二叉树中每个结点的两棵子树是有序的。（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2k-1）（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i -1个结点。

（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，即有后继链接的指针仅n-1个，还有n+1个空指针。）采用二叉链表存储有2n个链域，空链域为：2n-（n-1）=n+1 （√）10.具有12个结点的完全二叉树有5个度为2的结点。最快方法：用叶子数＝[ n/2] ＝6，再求n2=n0-1=5 [n/2] 除的结果四舍五入二、填空 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 (或：总结点数为n=2k-1=26-1=63，叶子数为n0= [ n/2] =32，满二叉数没有度为1的结点，由n0=n2+1得n2=n0-1=32-1=31)

数据结构C++树与二叉树

二叉树定义[二叉树] 二叉树（binary tree）t 是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个称为根的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树。二叉树和树的根本区别是： ? 二叉树可以为空，但树不能为空。 ? 二叉树中每个元素都恰好有两棵子树（其中一个或两个可能为空）。而树中每个元素可有若干子树。 ? 在二叉树中每个元素的子树都是有序的，也就是说，可以用左、右子树来区别。而树的子树间是无序的。像树一样，二叉树也是根节点在顶部。二叉树左(右)子树中的元素画在根的左(右)下方。在每个元素和其子节点间有一条边。二叉树的特性特性1包含n (n> 0 )个元素的二叉树边数为n-1。证明: 二叉树中每个元素(除了根节点) 有且只有一个父节点。在子节点与父节点间有且只有一条边，因此边数为n-1。二叉树的高度（h e i g h t）或深度（d e p t h）是指该二叉树的层数。特性2若二叉树的高度为h，h≥0，则该二叉树最少有h个元素，最多有2h - 1个元素。证明: 因为每一层最少要有1个元素，因此元素数最少为h。每元素最多有2个子节点，则第i 层节点元素最多为2i - 1个，i > 0。h= 0时，元素的总数为0，也就是20 - 1。当h > 0 时，元素的总数不会超过. 特性3 包含n 个元素的二叉树的高度最大为n，最小为[l o g2 (n+ 1 )]。证明: 因为每层至少有一个元素，因此高度不会超过n。由特性2，可以得知高度为h 的二叉树最多有2h-1个元素。因为n≤2h-1，因此h≥log2 (n+ 1 )。由于h 是整数，所以h≥[l o g2 (n+ 1 )]。当高度为h 的二叉树恰好有2h - 1个元素时，称其为满二叉树（full binary tree）假设从满二叉树中删除k个元素，其编号为2h -i, 1≤i≤k，所得到的二叉树被称为完全二叉树（complete binary tree）在完全二叉树中，一个元素与其孩子的编号有非常好的对应关系。其关系在特性4中给出。特性4 设完全二叉树中一元素的序号为i, 1≤i≤n。则有以下关系成立： 1) 当i = 1时，该元素为二叉树的根。若i > 1，则该元素父节点的编号为?i / 2?。 2) 当2i >n时，该元素无左孩子。否则，其左孩子的编号为2i。 3) 若2i + 1 >n，该元素无右孩子。否则，其右孩子编号为2i + 1。证明 :通过对i 进行归纳即可得证。

二叉树的单分支结点个数(精)

# include # include typedef char TElemType;//把二叉树的类型定义为字符型 typedef struct node { TElemType data; struct node *lchild,*rchild; }BiTNode,*BiTree; void InitBiTree(BiTree *root) { (*root)=NULL; } //递归的方法创建一棵二叉树 void Create(BiTree *root) { TElemType x; scanf("%c",&x); getchar(); if(x=='0') return ; else { (*root)=(BiTNode*)malloc(sizeof(BiTNode)); (*root)->data=x; (*root)->lchild=(*root)->rchild=NULL; Create(&((*root)->lchild)); Create(&((*root)->rchild)); } } void PreOrder(BiTree root)//先序遍历二叉树，root为指向二叉树根结点{ if(root!=NULL) { printf("%c ",root->data);//访问根结点 PreOrder(root->lchild);//先序遍历左子树 PreOrder(root->rchild);//先序遍历右子树 } } int OncechildNum(BiTree root) { if(root==NULL) return 0; else if(root->lchild==NULL&&root->rchild==NULL) return 0; else

各类型二叉树例题说明

5.1树的概念树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树 1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。 2.树的深度——组成该树各结点的最大层次，如上图，其深度为4； 3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林； 4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。 5.树的表示树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式： (A(B(E(K,L),F),C(G),D(H(M),I,J))) 5. 2 二叉树 1.二叉树的基本形态：二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态： (1)空二叉树——(a)； (2)只有一个根结点的二叉树——(b)； (3)右子树为空的二叉树——(c)； (4)左子树为空的二叉树——(d)； (5)完全二叉树——(e) 注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。 2.两个重要的概念： (1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树； (2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。如下图：完全二叉树 1页

树与二叉树习题解析(答)

习题五树与二叉树一、选择题 1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足。 A、所有的结点均无左孩子 B、所有的结点均无右孩子 C、只有一个叶子结点 D、是任意一棵二叉树 2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是。 A、250 B、500 C、254 D、505 E、以上答案都不对 3、以下说法正确的是。 A、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点 B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点 C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点 D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点 4、以下说法错误的是。 A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近 B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点 C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树,因为不知道树的根结点是哪一个 D、在前序遍历二叉树的序列中,任何结点其子树的所有结点都是直接跟在该结点之后的 5、一棵有124个叶结点的完全二叉树，最多有个结点。

A、247 B、248 C、249 D、250 E、251 6、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序。 A、不发生变化 B、发生变化 C、不能确定 7、设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是。 A、a在b的右方 B、a在b的左方 C、a是b的祖先 D、a是b的子孙 8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为。 A、不确定 B、2k C、2k-1 D、2k+1 9、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。 A、13 B、12 C、26 D、25 10、下面几个符号串编码集合中，不是前缀编码的是。 A、{0，10，110，1111} B、{11，10，001，101，0001} C、{00，010，0110，1000} D、{b,c,aa,ac,aba,abb,abc} 11、欲实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳的方案是二叉树采用存储结构。 A、三叉链表 B、广义表 C、二叉链表 D、顺序表 12、以下说法错误的是。 A、存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同 B、二叉树是树的特殊情形 C、由树转换成二叉树，其根结点的右子树总是空的 D、在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 13、树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序、中序和后序三种遍历。我们把由树转化得到的二叉树称该树对应的二叉树，则下面是正确的。 A、树的先根遍历序列与其对应的二叉树先序遍历序列相同

数据结构——二叉树基本操作源代码

数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include using namespace std; //------------------------------------------------------------------------------------------------------------------------ //定义二叉树的结点类型BTNode,其中包含数据域、左孩子，右孩子结点。template struct BTNode { T data ; //数据域 BTNode* lchild; //指向左子树的指针 BTNode* rchild; //指向右子树的指针 }; //------------------------------------------------------------------------------------------------------------------------ //CBinary的类模板 template class BinaryTree { BTNode* BT; public: BinaryTree(){BT=NULL;} // 构造函数,将根结点置空 ~BinaryTree(){clear(BT);} // 调用Clear()函数将二叉树销毁 void ClearBiTree(){clear(BT);BT=NULL;}; // 销毁一棵二叉树 void CreateBiTree(T end); // 创建一棵二叉树，end为空指针域标志 bool IsEmpty(); // 判断二叉树是否为空 int BiTreeDepth(); // 计算二叉树的深度 bool RootValue(T &e); // 若二叉树不为空用e返回根结点的值，函数返回true，否则函数返回false BTNode*GetRoot(); // 二叉树不为空获取根结点指针，否则返回NULL bool Assign(T e,T value); // 找到二叉树中值为e的结点，并将其值修改为value。