NOIP初赛复习7二叉树的遍历和性质

1、noip初赛复习7二叉树的遍历和性质 noip初赛复习7二叉树的遍历和性质 二叉树的遍历 （图1） （图2） 二叉树的遍历运算（递归定义） (1) 先序遍历： 根，左子树，右子树 根在先 例如图1：271653894；图2：abckdehfjg (2) 中序遍历： 左子树，根，右子树 根在中 例如图1：175632849；图2：bkcahedhfg (3) 后序遍历： 左子树，右子树，根 根在后 例如图1：153674982；图2：kcbhejgfda 题型一：已知其中一些遍历结果，求其他遍历结果 题型二：统计个不同的点可以构造多少棵不同的二叉树? catalan数=c(n,2*n)/(n+1

2、) 题型三：中缀表达式向前缀和后缀表达式的转化 每日练习 注：题1已知先序和中序，二叉树是唯一的。 题2已知后序和中序，二叉树是唯一的。 题3已知先序和后序，二叉树不是唯一的。 1、已知先序：1 2 4 3 5 7 6， 中序：2 4 1 7 5 3 6，请画出整棵二叉树。 2、已知后序：4 5 2 6 7 3 1， 中序：4 2 5 7 6 3 1，请画出整棵二叉树。 3、已知先序：1 2 3 4 5 6， 后序：3 2 5 6 4 1，请画所有二叉树的情况。 4、如果只知道先序，画出所有可能二叉树形状，并且计算多少种？ 5、如果只知道中序，画出所有可能二叉树形状，并且计算多少种？ 6、如果

3、只知道后序，画出所有可能二叉树形状，并且计算多少种？ 往年真题 1. 一颗二叉树的前序遍历序列是abcdefg，后序遍历序列是cbfegda，则根结点的左子树的结点个数可能是（ ）。 a0 b2 c4 d 6 2. 表达式a*(b+c)-d的后缀表达式是： a) abcd*+- b) abc+*d- c) abc*+d- d) -+*abcd 3. 二叉树t，已知其先序遍历是1 2 4 35 7 6（数字为节点编号，以下同），后序遍历是4 2 7 56 3 1，则该二叉树的中根遍历是（ ） a4 2 1 7 5 3 6 b2 4 1 7 5 3 6 c4 2 1 75 6 3 d2 4 1 5

4、7 3 6 4. 二叉树t，已知其先根遍历是1 2 4 35 7 6（数字为结点编号，以下同），中根遍历是2 4 1 57 3 6，则该二叉树的后根遍历是（ ） a. 4 2 5 7 6 3 1 b. 4 2 7 5 6 3 1 c. 7 4 2 5 6 3 1 d. 4 2 7 6 5 3 1 5. 已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的编号，以下同), 后根遍历是4 6 5 2 7 3 1,则该二叉树的可能的中根遍历是( ) a. 4 2 6 5 1 7 3 b. 4 2 5 6 1 3 7 c. 4 2 3 1 5 6 7 d. 4 2 5 6 1 7

5、3 6. 已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是4 2 6 51 7 3，则该二叉树的后根遍历是（ ） a4 6 5 27 3 1 b4 6 5 2 1 3 7 c4 2 3 1 5 4 7 d4 6 5 3 1 7 2 7. 已知6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 64 1，则该二叉树的可能的中根遍历是（ ） a. 3 2 1 46 5 b. 3 21 5 4 6 c. 2 3 1 5 4 6 d. 2 31 4 6 5 二叉树的性质 性质1：二叉树第i层上的结点数目

6、最多为。 性质2：深度为k的二叉树至多有个结点(k1)。 性质3：二叉树中，叶子节点数为n0，度为2的结点数为n2，则n0=n2+1。 满二叉树 定义：一棵深度为k且有个结点的二又树称为满二叉树。 。 特点：每层都饱满完全二叉树 定义：除了最下层，其他每层都饱满，最下层的结点都集中在该层最左边的若干位置上。 特点： 满二叉树是完全二叉树，完全二叉树不一定是满二叉树； 在满二叉树的最下层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。若i为结点编号则 如果i1，则其父结点的编号为i/2；若2*in，则无左儿子若2*i+1n，则无右儿子。 例题1：画一个深度为4的满二叉树。画一个深度为4的完全二叉树。 例题2：具有3个结点的完全二叉树的深度为（ ） 具有6个结点的完全二叉树的深度为（ ） 具有8个结点的完全二叉树的深度为（ ） n + 3，则它的叶结点个数为（ ）。 a 2*n b 2*n-1 c 2*n+1 d 2*n-2 e 2*n+2 5.满二叉树的叶结点个数为n，则它的结点总数为（ ）。 a n b 2*n c 2*n1 d 2*n+1 e 2n1 6.在有n个