题型：
单选题
填空题
编程题
综合题

数据结构

某二叉树结点的中序序列是ABCDEFG,后序序列为BDCAFGE,则该二叉树前序序列为（）

A. EACBDFG

B. EACBDGF

C.ECBDAFG

D.ECBDAGF

A B C D

正确率：

B

一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）

A.所有结点均无左孩子

B.所有结点均无右孩子

C.只有一个叶子结点

D.任意一棵二叉树

A B C D

正确率：

C

某一二叉树中序遍历为eabdcf，后序遍历为aebfcd，则该二叉树先序遍历的顺序是（）。

A.adbecf B.dfecab C.dbeacf D.abcdef

A B C D

正确率：

C

任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序( )

A.肯定不会发生改变

B.肯定发生改变

C.不能确定

D.有时发生改变，有时不发生

A B C D

正确率：

A

在一非空二叉树的中序遍历序列中，根结点的右边( )

A.只有右子树上的所有结点

B.只有右子树上的部分结点

C.只有左子树上的部分结点

D.只有左子树上额所有结点

A B C D

正确率：

A

将一棵树T转换为一颗二叉树T2，则T的先序遍历是T2的（）。

A.先序 B.中序 C.后序 D.无法确定

A B C D

正确率：

D

将一棵树T转换为一颗二叉树T2，则T的后序遍历是T2的（）。

A.先序 B.中序 C.后序 D.无法确定

A B C D

正确率：

D

一棵二叉树的前序序列和序列可唯一确定一棵二叉树。

1:

若某完全二叉树采用顺序存储结构，结点依次存放的顺序为：ABCDEFGH,则该二叉树的后序遍历序列为:（请使用大写字母）

1:

下面左图中所画树的中序遍历序列为,前序遍历序列为。

1: 2:

先序序列为abc且后序序列为cba的二叉树一共有棵

1:

先序序列为abc且后序序列为bca的二叉树一共有棵

1:

已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，则该二叉树的后序遍历序列为、中序遍历序列为。(答案请使用大写字母）

1: 2:

完成中序遍历二叉树的函数。运行中输入的数据生成如下图所示的二叉树。

分数:

请勿频繁操作

#include <stdio.h>
#include <stdlib.h>

typedef struct _Bitree
{
	char ch;
	struct _Bitree *lchild;
	struct _Bitree *rchild;
} Bitree;

void create(Bitree **t, char **str);
void inorder(Bitree *t);

int main()
{
	char *str;
	
	Bitree *t;

	str = (char *)malloc(100*sizeof(char));

	printf("Input:\n");
	fgets(str, 99, stdin);
	create(&t, &str);
	printf("inorder:");
	inorder(t);
	printf("\n");
	return 0;
}

void create(Bitree **t, char **str)
{
	//先根序递归创建二叉树
	//abc###d##，无左右孩子输入#
	if (*str[0] == '#')
	{
		*t = NULL;
		return ;
	}
	
	*t = (Bitree *)malloc(sizeof(Bitree));
	(*t)->ch = *str[0];
	*str = *str + 1;
	create(&(*t)->lchild, str);
	*str = *str + 1;
	create(&(*t)->rchild, str);

}

/******start******/

/******end******/

#include <stdio.h>
#include <stdlib.h>

typedef struct _Bitree
{
	char ch;
	struct _Bitree *lchild;
	struct _Bitree *rchild;
} Bitree;

void create(Bitree **t, char **str);
void inorder(Bitree *t);

int main()
{
	char *str;
	
	Bitree *t;

	str = (char *)malloc(100*sizeof(char));

	printf("Input:\n");
	fgets(str, 99, stdin);
	create(&t, &str);
	printf("inorder:");
	inorder(t);
	printf("\n");
	return 0;
}

void create(Bitree **t, char **str)
{
	//先根序递归创建二叉树
	//abc###d##，无左右孩子输入#
	if (*str[0] == '#')
	{
		*t = NULL;
		return ;
	}
	
	*t = (Bitree *)malloc(sizeof(Bitree));
	(*t)->ch = *str[0];
	*str = *str + 1;
	create(&(*t)->lchild, str);
	*str = *str + 1;
	create(&(*t)->rchild, str);

}

/******start******/

/******end******/

完成函数输出二叉树的先序序列。运行中输入的数据生成如下图所示的二叉树。

分数:

请勿频繁操作

#include <stdio.h>
#include <stdlib.h>

typedef struct _Bitree
{
	char ch;
	struct _Bitree *lchild;
	struct _Bitree *rchild;
} Bitree;

void create(Bitree **t, char **str);
void preorder(Bitree *t);

int main()
{
	char *str;
	
	Bitree *t;

	str = (char *)malloc(100*sizeof(char));

	printf("Input:\n");
	fgets(str, 99, stdin);
	create(&t, &str);

	printf("pre:");
	preorder(t);
	printf("\n");
	return 0;
}

void create(Bitree **t, char **str)
{
	//先根序递归创建二叉树
	//abc###d##，无左右孩子输入#
	if (*str[0] == '#')
	{
		*t = NULL;
		return ;
	}
	
	*t = (Bitree *)malloc(sizeof(Bitree));
	(*t)->ch = *str[0];
	*str = *str + 1;
	create(&(*t)->lchild, str);
	*str = *str + 1;
	create(&(*t)->rchild, str);

}

/******start******/

/******end******/

#include <stdio.h>
#include <stdlib.h>

typedef struct _Bitree
{
	char ch;
	struct _Bitree *lchild;
	struct _Bitree *rchild;
} Bitree;

void create(Bitree **t, char **str);
void preorder(Bitree *t);

int main()
{
	char *str;
	
	Bitree *t;

	str = (char *)malloc(100*sizeof(char));

	printf("Input:\n");
	fgets(str, 99, stdin);
	create(&t, &str);

	printf("pre:");
	preorder(t);
	printf("\n");
	return 0;
}

void create(Bitree **t, char **str)
{
	//先根序递归创建二叉树
	//abc###d##，无左右孩子输入#
	if (*str[0] == '#')
	{
		*t = NULL;
		return ;
	}
	
	*t = (Bitree *)malloc(sizeof(Bitree));
	(*t)->ch = *str[0];
	*str = *str + 1;
	create(&(*t)->lchild, str);
	*str = *str + 1;
	create(&(*t)->rchild, str);

}

/******start******/

/******end******/

编写算法：统计一棵二叉树的叶子节点数目。

左子树叶子结点右子树叶子结点左右子树叶子结合之和

假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请写出该二叉树的后序遍历序列。

后序ACDBGJKIHFE

假设一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请写出该二叉树的先序遍历序列.

ABCDGEIHFJK

编写求一棵二叉树中结点总数的算法。

遍历每个结点，每遍历一个结点计数器+1