二叉树性质练习题

E F D GAB/+ +* - C* 第六章树和二叉树一、选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DED. -+A*BC/DE【北京航空航天大学 1999 一、3 （2分)】2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（）【中山大学 1999 一、5】A ．ab+cde/*B ．abcde/+*+C ．abcde/*++ D．abcde*/++3. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（）【南京理工大学1999 一、20（2分）】A. A*B+C/(D*E)+(F-G)B. (A*B+C)/(D*E)+(F-G)C. (A*B+C)/(D*E+（F-G ）)D. A*B+C/D*E+F-G4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（）A ．5 B．6 C．7D ．8【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（）【南京理工大学 1999 一、4 （1分）】①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A ．①②③ B ．②③④ C．②④D ．①④6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F中第一棵树的结点个数是（）A ．m-nB ．m-n-1C ．n+1D ．条件不足，无法确定【南京理工大学2000 一、17（1.5分）】7. 树是结点的有限集合，它（(1）)根结点，记为T 。

其余结点分成为m （m>0）个(（2）)的集合T1，T2，…，Ｔm ，每个集合又都是树，此时结点T 称为Ti 的父结点，Ti 称为T 的子结点（1≤i ≤m ）。

一、下面是有关二叉树的叙述，请判断正误（∨）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（ X ）2.二叉树中每个结点的两棵子树的高度差等于1。

（∨）3.二叉树中每个结点的两棵子树是有序的。

（ X ）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（ X）5.二叉树中所有结点个数是2k-1-1，其中k是树的深度。

（ X ）6.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（ X ）7.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i－1个结点。

（∨）8.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

（ X ）9. 具有12个结点的完全二叉树有5个度为2的结点。

二、填空1．由３个结点所构成的二叉树有 5 种形态。

2. 一棵深度为6的满二叉树有 26-33 个分支结点和 32 个叶子。

3．一棵具有２５７个结点的完全二叉树，它的深度为 9 。

4. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。

（分析：完全二叉树中三种节点个数n0，n1，n2,其中n1为0或1；n0=n2+1；总节点个数N=n0+n1+n2=n0+n1+n0-1=2*n0-1+n1.由此推出当完全二叉树中节点个数为偶数时n1为1，否则为0，则可计算本题）5. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。

因而二叉树的遍历次序有六种。

最常用的是三种：前序法（即按N L R次序），后序法（即按 LRN 次序）和中序法（也称对称序法，即按L N R次序）。

这三种方法相互之间有关联。

若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 FEGHDCB 。

6. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 (1+2)*3+3*2+(4+5)*2= 33 。

一、选择题1．关于二叉树的下列说法正确的是（B ）A．二叉树的度为2 B．二叉树的度可以小于2C．每一个结点的度都为2 D ．至少有一个结点的度为2 2．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为（C ）A．3 B．4C．5 D ．63．若一棵完全二叉树中某结点无左孩子，则该结点一定是（D ）A．度为1的结点B．度为2的结点C．分支结点 D ．叶子结点4．深度为k的完全二叉树至多有（C ）个结点，至少有（ B ）个结点。

A．2k-1-1 B．2k-1C．2k-1 D ．2k5．在具有200个结点的完全二叉树中，设根结点的层次编号为1，则层次编号为60的结点，其左孩子结点的层次编号为（ C 2i ），右孩子结点的层次编号为（ D 2i+1），双亲结点的层次编号为（60/2=30 A ）。

A．30 B．60C．120 D ．1216．一棵具有124个叶子结点的完全二叉树，最多有（B ）个结点。

A．247 B．248C．249 D ．250二、填空题1．树中任意结点允许有零个或多个孩子结点，除根结点外，其余结点有且仅有一个双亲结点。

2．若一棵树的广义表表示法为A（B（E，F），C（G（H，I，J，K），L），D（M （N））），则该树的度为 4 ，树的深度为 4 ，树中叶子结点的个数为8 。

3．若树T中度为1、2、3、4的结点个数分别为4、3、2、2，则T中叶子结点的个数为14 。

n=n0+n1+n2+n3+n4=n0+4+3+2+2=n0+11n=1+孩子=1+4+6+6+8+25n0+11=25n0=144．一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数是n-2m+1 。

5．深度为k（k>0）的二叉树至多有2k -1 个结点，第i层上至多有2i-1个结点。

6．已知二叉树有52个叶子结点，度为1的结点个数为30，则总结点个数为133 。

7．已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是30+29+0=59 。

习题6解答判断题：1.二叉树中每个结点有两个子女结点，而对一般的树则无此限制，因此二叉树是树的特殊情形。

( ╳ )2.二叉树就是结点度为2的树。

( ╳ )( (哈工大2000年研究生试题)3.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。

( ╳ ) (陕西省1998年自考试题)4.当k≥1时，高度为k的二叉树至多有21 k个结点。

( ╳ )5.完全二叉树的某结点若无左孩子，则它必是叶结点。

(√)(中科院软件所1997年研究生试题)6.用一维数组存放二叉树时，总是以前序遍历顺序存储结点。

( ╳ )7.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。

( ╳ )8.存在这样的二叉树，对它采用任何次序的遍历，结果相同。

(√)(哈工大2000年研究生试题)9.中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。

(√)10.将一棵树转换成二叉树后，根结点没有左子树，( ╳ )(北邮1999年研究生试题。

)11.由树转换成二叉树，其根结点的右子树总是空的。

(√)12.前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。

( ╳ )13.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。

( ╳ )14.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。

( ╳ )15.霍夫曼树一定是满二叉树。

( ╳ )16.树的度是树内各结点的度之和。

( ╳ )17.由二叉树的结点构成的集合可以是空集合。

(√)18.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。

( ╳ )选择题：19.树最适合用来表示( C )。

A．有序数据元素 B. 无序数据元素C．元素之间具有分支层次关系的数据 D. 元素之间无联系的数据20.如果结点A有3个兄弟，而且B是A的双亲，则B的度是( D )。

第 6 章树和二叉树1．选择题（ 1）把一棵树变换为二叉树后，这棵二叉树的形态是（）。

A．独一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子（ 2）由 3 个结点能够结构出多少种不一样的二叉树？（）A． 2 B ． 3 C ． 4 D． 5（ 3）一棵完整二叉树上有1001 个结点，此中叶子结点的个数是（）。

A． 250 B ． 500 C ． 254 D． 501（ 4）一个拥有 1025 个结点的二叉树的高h 为（）。

A． 11 B ． 10 C．11 至 1025 之间 D ．10 至 1024 之间（ 5）深度为 h 的满 m叉树的第 k 层有（）个结点。

(1=<k=<h)k-1B kCh-1 hA． m ． m-1 ． m D．m-1（ 6）利用二叉链表储存树，则根结点的右指针是（）。

A．指向最左孩子 B ．指向最右孩子 C ．空 D ．非空（ 7）对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采纳（）遍历实现编号。

A．先序 B. 中序 C. 后序 D.从根开始按层次遍历（8）若二叉树采纳二叉链表储存结构，要互换其全部分支结点左、右子树的地点，利用（）遍历方法最适合。

A．前序B．中序C．后序D．按层次（9）在以下储存形式中，（）不是树的储存形式？A．双亲表示法 B ．孩子链表表示法 C ．孩子兄弟表示法D．次序储存表示法（ 10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树必定满足（）。

A．全部的结点均无左孩子B．全部的结点均无右孩子C．只有一个叶子结点D．是随意一棵二叉树（ 11）某二叉树的前序序列和后序序列正好相反，则该二叉树必定是（）的二叉树。

A．空或只有一个结点B．任一结点无左子树C．高度等于其结点数 D ．任一结点无右子树（ 12）若 X 是二叉中序线索树中一个有左孩子的结点，且 X 不为根，则 X 的前驱为（）。

A
F
B
J
E
F H
G
I J
例6.14
Huffman编码设计实例
已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05， 0.29，0.07，0.08，0.14， 0.23，0.03，0.11，试设计Huffman编码。 解一：先构造Huffman树，再进行编码。 Huffman编码实现过程：以报文所用的不同字符为叶结点，以字符 出现频率为权重构造Huffman树；然后将树中结点指向其左孩子的 分支标“0”，指向其右孩子的分支标“1”；每个字符的编码即为 从根到每个叶子（字符）的路径上得到的0、1序列。这种对字符的 编码就是Huffman编码。
100
0 1
HC
42
0 1 0
58
1
0
1 2
0 1
1 0
1
0
3
1
1 1 0 0 0
1
1 1 0 1 1
1
1 0 1 1
0
1
23
0
19
1
29
1
29
1
11
0
8 5
14
0
15
1
4 5 6 7 8
1
3 Huffman树
7
8 Huffman编码
解二：利用Huffman编码算法实现。根据题意，取8个字符的权分别为 （5，29，7，8，14，23，3，11），n=8，则m=2*8-1=15，按上述 算法可构造一棵Huffman树，如下左图和右图分别Huffman树的初始 状态和终止状态。
a
b b d g e h i c ^ d c ^
f e ^ g
^ ^ ^

（4）若一棵完全二叉树中，某节点无左孩子，则该 结点一定是（ ）。 A.度为1的结点 B.度为2的结点 C.分支节点 D.叶子结点 （5）高度为k的完全二叉树至多有（ ）个结点， 至少有（ ）个结点。 A.2K-1-1 B. 2K-1 C.2K-1 D.2K （6）先序序列为ABC的二叉树有（ ）棵。 A. 3 B.4 C.5 D.6 （7）在有200个结点的完全二叉树中，根的编号为1， 则编号为60的结点左孩子编号是（ ），右孩子的编 号是（ ）。 A.30 B.60 C.120 D.121
（8）遍历一棵具有n个结点的完全二叉树，在先序， 中序和后序序列中，叶子结点的相对次序（ ）。 A.都不同 B.完全相同 C.先序和中序相同 D.中序与后序相同 （9）在由4棵树组成的森林中，1，2，3，4棵树，树 中结点的个数分别为30，10，20，5，当把森林转化 成为二叉树后，对应的二叉树中根结点的左子树中结 点的个数是（ ），右子树中结点的个数是（ ）。 A.20 B.29 C.30 D.35 （10）有n（n>1）个结点的二叉树的先序序列与后序 序列相反，则二叉树中除了叶子外，每个结（ ）。 A.仅有左孩子 B.仅有右孩子 C.仅有一个孩子 D.都有两个孩子
（4）一棵深度为h的满k叉树有如下性质： 第h层上 的结点都是叶子结点，其余各层上每个结点都有 k棵 非空子树。 如果按层次顺序(同层自左至右)从1开始 对全部结点编号，问： ① 各层的结点数是多少? ② 编号为i的结点的双亲结点(若存在)的编号是 多少? ③ 编号为i的结点的第j个孩子结点(若存在)的编 号是多少? ④ 编号为i的结点的有右兄弟的条件是什么? 其 右兄弟的编号是多少?
（6）一个含有68个结点的完全二叉树，它的高度是 （ ）。 （），其中叶子结点个数是 （ ）；则总结点数至多是（ ），其中叶子结 点个数是（ ）。 （8）一棵树转化成二叉树后，这棵二叉树的根节点 一定没有（ ）孩子，若树中有m个分支结点，则对 应二叉树中（ ）个结点没有右孩子。 （9）若用二叉链表表示具有n个结点的二叉树，则有 （ ）个空链域。 （10）具有m个叶子结点的赫夫曼树，共有（ ）个 结点。

二叉树的遍历（图1）（图2）二叉树的遍历运算（递归定义）(1)先序遍历：根，左子树，右子树根在先例如图1：271653894；图2：ABCKDEHFJG(2)中序遍历：左子树，根，右子树根在中例如图1：175632849；图2：BKCAHEDHFG(3)后序遍历：左子树，右子树，根根在后例如图1：153674982；图2：KCBHEJGFDA题型一：已知其中一些遍历结果，求其他遍历结果题型二：统计ｎ个不同的点可以构造多少棵不同的二叉树?Catalan数=C(n,2*n)/(n+1)题型三：中缀表达式向前缀和后缀表达式的转化每日练习注：题1已知先序和中序，二叉树是唯一的。

题2已知后序和中序，二叉树是唯一的。

题3已知先序和后序，二叉树不是唯一的。

1、已知先序：1243576，中序：2417536，请画出整棵二叉树。

2、已知后序：4526731，中序：4257631，请画出整棵二叉树。

3、已知先序：123456，后序：325641，请画所有二叉树的情况。

4、如果只知道先序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？5、如果只知道中序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？6、如果只知道后序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？往年真题1.一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（）。

A．0B．2C．4D．62.表达式a*(b+c)-d的后缀表达式是：A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd3.二叉树T，已知其先序遍历是1243576（数字为节点编号，以下同），后序遍历是4275631，则该二叉树的中根遍历是（）A．4217536B．2417536C．4217563D．24157364.二叉树T，已知其先根遍历是1243576（数字为结点编号，以下同），中根遍历是2415736，则该二叉树的后根遍历是（）A.4257631B.4275631C.7425631D.42765315.已知7个节点的二叉树的先根遍历是1245637(数字为结点的编号，以下同),后根遍历是4652731,则该二叉树的可能的中根遍历是()A.4265173B.4256137C.4231567D.42561736.已知7个节点的二叉树的先根遍历是1245637（数字为节点的编号，以下同），中根遍历是4265173，则该二叉树的后根遍历是（）A．4652731B．4652137C．4231547D．46531 727.已知6个结点的二叉树的先根遍历是123456（数字为结点的编号，以下同），后根遍历是325641，则该二叉树的可能的中根遍历是（）A.321465B.321546C.231546D.231465二叉树的性质性质1：二叉树第i层上的结点数目最多为。

8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（）A.4B.5C.7D.8若根结点的层数为1，则具有n个结点的二叉树的最大高度是( )A.nB.C. n+1D.n/2在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )A．4 B．5 C．6 D．7已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）A. 0B. 1C. 48D. 49除第一层外，满二叉树中每一层结点个数是上一层结点个数的（）A．1/2倍B．1倍C．2倍D．3倍．已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（）A．7 B．8C．9 D．10高度为5的完全二叉树中含有的结点数至少为( )A.16B.17C.31D.32有64个结点的完全二叉树的深度为( )(根的层次为1)。

A. 8B. 7C. 6D. 58．若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（）A．10 B．11C．12 D．不确定的二叉树中第5层上的结点个数最多为( )A.8B.15C.16D.32若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（）A.4B.5C.7D.8.一棵含18个结点的二叉树的高度至少为( )A.3B.4C.5D.6下列陈述中正确的是( )A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分假设一棵完全二叉树含1000个结点,则其中度为2的结点数为___________。

任意一棵完全二叉树中，度为1的结点数最多为________。

已知一棵完全二叉树中共有768结点，则该树中共有个叶子结点。

在含100个结点的完全二叉树中，叶子结点的个数为___________。

已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。

-+/a*efb-cd
二叉树的二叉链表类
class BiTree // 二叉树类 private: {public: NodeType *root; BiTree(){root=NULL;} preorder(NodeType *p); ~BiTree(){destroy(root) ;} //先序遍历 void creat(); inorder(NodeType *p); void preorder() //先序遍历 //中序遍历 { preorder(root); } postorder(NodeType *p); void inorder() //中序遍历 //后序遍历 { inorder(root); } void destroy(NodeType *p); void postorder() //后序遍历 //删除二叉树所有结点 { postorder(root); } //……. //删除二叉树所有结点 }；
1 2 4 8 9 10 5 11 12 6 13 14 3 7 15 4 6 2
1 3 5 7
1 2 4 8 9 10 5 11 12 6 3 7 4 2 5 1 3 6
链式存储结构
二叉链表
struct NodeType { ElemType data; NodeType *lch, *rch; };
void BiTree::creat() { NodeType *q, *s[20]; ElemType x;int i,j; root=NULL; cout<<"\n i,x="; cin>>i>>x; while(i!=0 && x!=0) { q=new NodeType; // 产生一个结点 q->data=x; q->lch=NULL; q->rch=NULL; s[i]=q; if (i==1) root=q; // q为树根root结点 else { j=i/2; // j为双亲结点编号 if ((i%2)==0) s[j]->lch=q; else s[j]->rch=q; } cout<<"\n i,x="; cin>>i>>x; }//while end } // creat end

数据结构与算法二叉树部分习题讲解齐荣嵘qrr0831@edx二叉树（上）一棵有510个结点的完全二叉树的高度为多少？（独根树高度为1）答案:根据公式log2510+1可以计算出高度为9在一棵非空二叉树中，若度为0的结点的个数n，度为2的结点个数为m，则有n=________答案: m+1Problem3-1•下列关于二叉树性质的说法正确的有：1.非空满二叉树的结点个数一定为奇数个。

√•结点度为0或2的数目相差12.当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。

√•倒数第二层的度都为0或者23.一棵非空二叉树的为空的外部结点数目等于其结点数加1。

√•2*n0+n1=n0+n1+n2+14.非完全二叉树也可以用像完全二叉树那样使用顺序存储结构进行存储。

×5.完全二叉树最多只有最下面的一层结点度数可以小于2。

×倒数第二层6.满二叉树的所有结点的度均为2。

×可能为0Problem3-2下列关于二叉树遍历的说法正确的有：1.只有空二叉树和一个根结点的二叉树这两种二叉树的前序和中序遍历的顺序恰好一样。

ו所有结点左子树为空的二叉树也满足要求2.所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。

√3.所有结点右子树为空的二叉树的前序和中序遍历顺序恰好一样。

×4.只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历的顺序恰好一样。

√•前序为中左右，而后序为左右中，所以缺失左子树或者右子树都不能让两者一样。

5.所有结点左子树为空的二叉树的前序和后序遍历顺序恰好一样。

×6.存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。

√•只有一个根结点的二叉树满足要求。

•已知一棵树的前序遍历为ABDEGCF，中序遍历为DBGEACF，求这棵树的后序遍历。

•答案：DGEBFCA•已知一棵树的中序遍历为DBGEACF，后序遍历为DGEBFCA，求这棵树的前序遍历。

数据结构练习试卷3(题后含答案及解析)题型有：1. 选择题选择题（每小题1分，共75分）下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。

1．二叉树(1)。

在完全的二叉树中，若一个结点没有(2)，则它必定是叶结点。

每棵树都能唯一地转换成与它对应的二叉树。

由树转换成的二叉树里，一个结点N的左子结点是N在原树里对应结点的(3)，而N的右子结点是它在原树里对应结点的(4)。

A．是特殊的树B．不是树的特殊形式C．是两棵树的总称D．是只有两个根结点的树形结构正确答案：B 涉及知识点：数据结构2．A．左子结点B．右子结点C．左子结点或者没有右子结点D．兄弟正确答案：A 涉及知识点：数据结构3．A．最左子结点B．最右子结点C．最邻近的右兄弟D．最邻近的左兄弟正确答案：A 涉及知识点：数据结构4．A．最左子结点B．最右子结点C．最邻近的右兄弟D．最邻近的左兄弟正确答案：C解析：树是结点的有限集合，它有且仅有1个根结点。

二叉树有0个或1个根结点，二者是两个不同的概念。

所以，第1空的正确答案为选项B。

在完全二叉树中，如果一个结点没有左子结点，那么必然没有右子结点，所以就一定是叶结点。

第2空的正确答案为选项A。

树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。

按照这种关系很自然地就能将树转换成相应的二叉树：①在所有兄弟结点之间加一连线；②对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子的连线。

因为树根没有兄弟，所以，树转换为二叉树之后，二叉树的根结点的右子树必然为空。

在由树转换成的二叉树中，一个结点N的左一个结点N的左子结点是N在原树里对应结点的最左子结点，而N的右子结点是它在原树里对应结点的最邻近的右兄弟。

所以，第3空的正确答案为选项A，第4空的正确答案为选项C。

知识模块：数据结构5．在一棵非空二叉树中，叶子节点的总数比度为2的节点总数多(43)个。

qu[rear].parent=-1;//根结点没有双亲,其parent置为-1
while (front!=rear)//队不空循环
{front++;
p=qu[front].s;//出队一个结点*p,它在qu中的下标为front
if (p->data==x)//找到值为x的结点
{printf("从根结点到%c结点的路径: ",p->data);
解：先序遍历树中结点的递归算法如下：
void PreOrder1(ElemType A[],int i,int n)
{if (i<n)
if (A[i]!='#')//不为空结点时
{printf("%c ",A[i]);//访问根结点
PreOrder1(A,2*i,n);//遍历左子树
PreOrder1(A,2*i+1,n);//遍历右子树
return h;
else
{l=Level(bt->lchild,x,h+1);//在左子树中查找
if (l!=0)
return l;
else//在左子树中未找到,再在右子树中查找
return(Level(bt->rchild,x,h+1));
}
}
上机实验题
假设一棵二叉树采用二叉链存储结构，其中所有结点值均不相同。设计一个算法求从根结点到值为x的结点的路径。并用相关数据进行测试。
图8.3一棵二叉树
（6）如果一棵哈夫曼树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。
答：一棵哈夫曼树中只有度为2和0的结点，没有度为1的结点，由非空二叉树的性质1可知，n0=n2+1，即n2=n0-1，则总结点数n=n0+n2=2n0-1。

2023年408数据结构选择题一、树与二叉树1. 什么是树结构？- 答案：树结构是由n（n>=1）个结点组成。

- 解析：树结构是一种非线性的数据结构，其中的结点通过边连接在一起，形成层级关系。

树结构由根结点、子结点和边组成。

2. 什么是二叉树？- 答案：每个结点最多有两个子结点的树称为二叉树。

- 解析：二叉树是一种特殊的树结构，每个结点最多有两个子结点，分别称为左子结点和右子结点。

二叉树的结构简单，易于实现和操作。

3. 二叉树的性质有哪些？- 答案：1）第i层最多有2^(i-1)个结点；2）深度为h的二叉树最多有2^h - 1个结点；3）在任意一棵二叉树中，度为0的叶结点数等于度为2的结点数加1。

二、图与搜索1. 什么是图？- 答案：图是由结点和边组成的一种数据结构。

- 解析：图是一种抽象的数据结构，由若干个顶点和边组成，用于描述事物之间的关系。

图可以分为有向图和无向图。

2. 什么是DFS（深度优先搜索）？- 答案：DFS是一种用于遍历或搜索图和树的算法。

- 解析：DFS通过递归或栈实现，首先访问初始结点，然后访问其邻接结点，直到所有结点都被访问过为止。

DFS具有简单、易于实现的特点。

3. 什么是BFS（广度优先搜索）？- 答案：BFS是一种用于遍历或搜索图和树的算法。

- 解析：BFS通过队列实现，首先访问初始结点，然后访问与初始结点相邻的所有结点，直到所有结点都被访问过为止。

BFS具有高效、逐层搜索的特点。

三、排序与查找1. 什么是排序算法？- 答案：排序算法是一种用于对数据进行排序的算法。

- 解析：常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。

不同的排序算法具有不同的时间复杂度和空间复杂度。

2. 什么是查找算法？- 答案：查找算法是一种用于在数据集中查找特定元素的算法。

- 解析：常见的查找算法包括顺序查找、二分查找、哈希查找等。

不同的查找算法适用于不同类型的数据集和查找需求。

专题15树知识点一树的性质1.假设完全二叉树的树根为第1层，树中第10层有5个叶子结点，则完全二叉树最多有个结点()A.511B.516C.2037D.20472.下列Python表达式用于表示“一棵n个节点的二叉树的叶子节点最大可能数量”，正确的是()A.n－1B.n//2C.n//2＋1D.n/2的是()3.某二叉树的结构如图所示，下列说法不正确．．．A.该二叉树是一棵完全二叉树B.该二叉树的叶子节点数是3个C.该二叉树的中序遍历结果是DCBEAFD.该二叉树的度为24.某树的结构如右，下列说法正确的是()A.该树的度为4B.该树的高度为4C.该树的叶子节点为3个D.节点F和G是兄弟节点5.一棵有n(n>0)个节点的二叉树，其节点为0度或2度，则此树的最大高度是()A.(n＋1)//2B.n//2C.(n－1)//2D.int(log2n＋1)6.若一棵二叉树具有10个度为2的节点，5个度为1的节点，则该树形结构的总边数是()A.14B.25C.23D.不能确定7.将一棵有1000个节点的完全二叉树按照从上到下、从左到右的顺序依次进行编号，根节点的编号为1，则编号为35的节点的右孩子编号为()A.36B.70C.72D.718.下列有关二叉树的论述中，正确的是()A.只有一个节点的二叉树的度为0B.二叉树的度为2C.二叉树的左右子树可任意交换D.完全二叉树的所有节点的度均为29.若一棵二叉树具有10个叶子节点，则树形结构度为2的节点数为()A.8B.9C.10D.1110.若一棵二叉树共有10个节点，其中4个是叶子节点，则度为1的节点数量为()A.3B.4C.5D.6知识点二树的遍历1.如图所示的二叉树，若要得到一个递增序列，可以用下列遍历方式是()A.前序遍历B.中序遍历C.后序遍历D.逐层遍历2.有一棵二叉树如图所示：关于该树，以下说法正确的是()A.该二叉树是一棵完全二叉树，树的高度为4B.该二叉树的前序遍历为25、15、46、6、18、28、58、12、22、35、60C.该二叉树的叶子节点有8个D.若用数组(第一个元素下标为0)来表示该树，则节点“46”在数组中下标为23.某二叉树的树形结构如图所示，其后序遍历结果为FBCEAD，则前序遍历结果为()A.ABCDEFB.FEDCBAC.DFACBED.FDBCAE4.某二叉树的前序遍历结果为ABCDEF，后序遍历结果为CDBFEA，下列关于该二叉树的说法，正确的是()A.该二叉树的深度可能为4B.该二叉树的中序遍历结果可能为CBDAEFC.该二叉树可能的形态有3种D.该二叉树度为2的节点可能有3个5.已知一棵二叉树如图所示，下列说法正确的是()A.树的高度是4，节点F是唯一的叶子节点B.中序、后序的遍历方式，节点F先于节点D、E访问C.前序遍历的结果为A－B－C－D－E－FD.使用数组可以表示为[‘A’，‘B’，‘C’，‘D’，‘E’，‘F’]的是()6.用一维数组来表示某二叉树如表所示，则下列说法不正确．．．A.该二叉树的深度为4B.节点B有两个孩子节点，分别为E和FC.该二叉树的中序遍历结果为DBGEAFHCD.叶子节点的数量比度为2的节点数量多17.如图所示，将二叉树A的根节点与二叉树B的根节点连接，使得二叉树A成为二叉树B的左子树，合并为一棵新的二叉树C。

1.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数？1根据“二叉树的第i层至多有2^(i − 1)个结点；深度为k的二叉树至多有2^k − 1个结点（根结点的深度为1）”这个性质：因为2^9-1 < 699 < 2^10-1 ,所以这个完全二叉树的深度是10，前9层是一个满二叉树，这样的话，前九层的结点就有2^9-1=511个；而第九层的结点数是2^(9-1)=256 所以第十层的叶子结点数是699-511=188个；现在来算第九层的叶子结点个数。

由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。

因为第十层有188个，所以应该去掉第九层中的188/2=94个；所以，第九层的叶子结点个数是256-94=162，加上第十层有188个，最后结果是350个2完全二叉树：若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的结点（叶结点）都依次排列在该层最左边的位置上，这样的二叉树为完全二叉树。

比如图：完全二叉树除叶结点层外的所有结点数（叶结点层以上所有结点数）为奇数，此题中，699是奇数，叶结点层以上的所有结点数为保证是奇数，则叶结点数必是偶数，这样我们可以立即选出答案为B！如果完全二叉树的叶结点都排满了，则是满二叉树，易得满二叉树的叶结点数是其以上所有层结点数+1比如图：此题的其实是一棵满二叉树，我们根据以上性质，699+1=700，700/2=350，即叶结点数为350，叶结点层以上所有结点数为350-1=349。

3完全二叉树中，只存在度为2的结点和度为0的结点，而二叉树的性质中有一条是：n0=n2+1；n0指度为0的结点，即叶子结点，n2指度为2的结点，所以2n2+1=699 n2=349；n0=3502.在一棵二叉树上第5层的结点数最多是多少一棵二叉树，如果每个结点都是是满的，那么会满足2^(k-1)1。

所以第5层至多有2^(5-1)=16个结点！3.在深度为5的满二叉树中，叶子结点的个数为答案是16 ~ 叶子结点就是没有后件的结点~ 说白了~ 就是二叉树的最后一层~ 深度为K的二叉树~ 最多有2^k-1个结点~ 最多有2^(k-1)个结点~ 所以此题~ 最多有2^5-1=31个结点~ 最多有2^(5-1)=16个叶子结点~4.某二叉树中度为2的结点有18个，则该二叉树中有几个叶子结点？结点的度是指树中每个结点具有的子树个数或者说是后继结点数。

二叉树性质简证：性质3：设k为其层数，m为其二度结点的个数，n为其叶子的个数！则1>。

当k=2时，易得m=1,n=2=m+12>。

设k＝i时，n=m+1则k=i+1时，设有j个叶子向下分出了二叉(0<=j<=n)，则m'=m+j (1)叶子则为原叶子减去原叶子中向下分出二叉的j个，再加上j个新双亲分出的2j个叶子，即：n'=n-j+2j=n+j (2)由（1）式得：j=m'-m ...(3)代入（2）式得：n'=n+m'-m (4)又因为在k=i时，n=m+1代入（4）式得：n'=(m+1)+m'-m=m'+1故：在i+1层时，n=m+1；综上所述：k=2时，n=m+1;由k层可推出k+1层；故得：对任一二叉树，叶子数＝2度结点数＋1注：有的同学可能说我可以在一些较少层的子树下不止加一层二叉，但此种情况可分两步：1》在叶子下加直至还有最后一层要作为叶子的没加，至此都符合n=m+1；2》在第1》步后用上述证明！性质5：证明：设左孩子标号为a,右孩子标号为b,选定结点标号为k;1。

当只有两层时：根结点标号为k=i=1，他的左孩子为a=2＝2i,右孩子为b=3＝2i+1;2。

当其层数超过两层时：取任一标号为k=i的结点，并设其左孩子标号a=2*i,其右孩子标号b=2*i+1则可求得a与k之间按标号相差的结点个数j=a-k+1=i-1;在研究a的孩子时，a的左孩子和a之间按标号隔的是这（i-1)个结点的所有孩子[2*(i-1)]，以及b点，故得a的左孩子的标号a'=a+2*(i-1)+1+1=4*i=2a,故a的右孩子标号b'=a'+1=4*i+1=2a+1;反方向可证k结点的双亲为i/2;综上所述，k=2时成立；由前一层可推出下一层故：定理得证！简单证明，必有疏漏，还待修改！请老师和同学赐教！——————————折翼天使---。