已知一棵二叉树的层次遍历序列ABCDEFG,中序遍历为BAFGDCE,则这个二叉树怎么画?
层序序列为BAFEGCD吗?
B
A F
E G
C
D
层序遍历为二叉树的根,看中序遍历,a左边的是a的左子树的节点,右边的是右子树节点,看层序,b是a的左子树的根,c是a的右子树的跟(因为c本身就是a的右子树,由第一步可知)依次类推。
一棵空树,或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉排序树;
扩展资料:
性质1:二叉树的第i层上至多有2i-1(i≥1)个节点
性质2:深度为h的二叉树中至多含有2h-1个节点
性质3:若在任意一棵二叉树中,有n0个叶子节点,有n2个度为2的节点,则必有n0=n2+1
性质4:具有n个节点的完全二叉树深为log2x+1(其中x表示不大于n的最大整数)
性质5:若对一棵有n个节点的完全二叉树进行顺序编号(1≤i≤n)
参考资料来源:百度百科-二叉树
根据 层次遍历序列ABCDEFG, 中序遍历序列BAFGDCE, 得到的二叉树是:
A
/ \
B C
/ \
D E
/
F
\
G
先序遍历序列: ABCDFGE
中序遍历序列: BAFGDCE
后序遍历序列: BGFDECA
层次遍历序列: ABCDEFG
如果是如下形状的二叉树,则
层次遍历序列仍然是ABCDEFG,但是,中序遍历序列是BAFDGCE (D,F,G的结构不同了)
A
/ \
B C
/ \
D E
/ \
F G
// C代码测试程序
// 输入先序扩展序列: AB##CDF#G###E##
// 输出4种遍历结果
// 先序遍历序列: ABCDFGE
// 中序遍历序列: BAFGDCE
// 后序遍历序列: BGFDECA
// 层次遍历序列: ABCDEFG
//
// 二叉树示意图:
// A
// / \
// B C
// / \
// D E
// /
// F
// \
// G
//
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef char TElemType;
typedef int bool;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode, *BiTree;
typedef BiTNode * QElemType;
typedef struct QNode
{
QElemType data;
struct QNode * next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue_L(LinkQueue *Q)
{
(*Q).front = (QueuePtr) malloc (sizeof(QNode));
if ((*Q).front == NULL)
return OVERFLOW;
(*Q).front->next = NULL;
(*Q).rear = (*Q).front;
return OK;
}
bool QueueEmpty_L(LinkQueue Q)
{
return (Q.front == Q.rear);
}
Status EnQueue_L(LinkQueue *Q, QElemType e)
{
QNode *s = (QNode *) malloc (sizeof(QNode));
s->data = e;
s->next = NULL;
(*Q).rear->next = s;
(*Q).rear = s;
return OK;
}
Status DeQueue_L(LinkQueue *Q)
{
QNode *q = (*Q).front->next;
(*Q).front->next = q->next;
if (q->next == NULL)
(*Q).rear = (*Q).front;
free(q);
return OK;
}
//创建二叉树: 先序扩展序列 + 递归法
void CreateBiTree(BiTree *T)
{
char input;
scanf("%c",&input); //输入数据
if(input == '#') //'#'是空节点
{
*T = NULL;
}
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
if(*T == NULL)
{
printf("
分配动态内存时出错.
");
exit(1);
}
(*T)->data=input;
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
}
void PreOrder(BiTree T) //先序遍历
{
if(T != NULL)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T) //中序遍历
{
if(T != NULL)
{
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
}
}
void PostOrder(BiTree T) //后序遍历
{
if(T != NULL)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
}
void LevelOrder(BiTree T) //层序遍历
{
LinkQueue Q;
BiTree p = T;
if(p == NULL)
{
return;
}
InitQueue_L(&Q);
EnQueue_L(&Q, p);
while( !QueueEmpty_L(Q) )
{
p = Q.front->next->data;
DeQueue_L(&Q);
printf("%c",p->data);
if(p->lchild != NULL)
{
EnQueue_L(&Q, p->lchild);
}
if(p->rchild != NULL)
{
EnQueue_L(&Q, p->rchild);
}
}
}
int main()
{
BiTree T;
CreateBiTree(&T);
printf("先序遍历序列: ");
PreOrder(T);
printf("
");
printf("中序遍历序列: ");
InOrder(T);
printf("
");
printf("后序遍历序列: ");
PostOrder(T);
printf("
");
printf("层次遍历序列: ");
LevelOrder(T);
printf("
");
return 0;
}
二叉树的基本概念
叶子结点:度为0的结点 分支结点:度不为0的结点 树的度:树中结点的最大的度 层次:根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1 树的高度:树中结点的最大层次 森林:0个或多个不相交的树组成。对森林加上一个根,森林即成为树;删去根,树即成为森林。二、二叉树 二叉树...
一棵5层平衡二叉树最少有几个结点?
至少有12个结点。分析过程如下:因为根结点层次为1,则高度为h的平衡二叉树最少有F(h + 2) -1个结点;其中F 为Fibonacci序列1, 1, 2, 3, 5, 8, 13, 21,...;Fibonacci数列种,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子数的节点数量;易知F(1)=1,F(2)=2,F(3)...
一棵完全二叉树第6层有7个结点,则共有几个结点
第一层1个 第二层2个 第三层4个 第四层8个 第五层16个 第六次层吗,没满,只有7个 ———共1+2+4+8+16+7=38个。补充知识:完全二叉树是指:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的节点都连续集中在最左边,这就是完全...
二叉树深度就是层数吗
二叉树深度就是层数。在二叉树中,深度指的是从根节点到叶子节点的最长路径的长度。深度也可以称为高度或层数,用来表示二叉树的垂直层次结构。根节点的深度为0,每向下一层深度加1。因此,二叉树的深度就等于层数。这个定义是基于常见的二叉树模型,即每个节点最多有两个子节点的情况。
二叉树根结点的层次是什么意思?
根的层次为0,根的直接左右孩子层次为1,以此类推层次逐渐递增。最大树身为99,即所有节点只有左孩子或者右孩子。最小树身为6,即每一层结点都是满的,除了最后一层叶节点。
一棵5层二叉树共有几个结点?
有12个节点 如果根结点层次为1,则高度为h的平衡二叉树最少有F(h + 2) -1个结点 其中F 为Fibonacci序列1, 1, 2, 3, 5, 8, 13, 21,...因此5层最少有F(7) -1 = 13-1 = 12个结点 http:\/\/baike.baidu.com\/albums\/593144\/593144.html#0$dbf554ed49e91f9cb21cb140 就像上面这...
满二叉树和完全二叉树的区别
对任一结点,若其右分支下子孙的最大层次为l,则其左分支下子孙的最大层次必为l或者I加1。满二叉树是一棵深度为k,且有2的k次方减1个节点的二叉树。满二叉树的每一层上的结点数都是最大结点数。满二叉树与完全二叉树的关系:在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有...
为什么对于完全二叉树,叶子节点只可能在层次最大的两层上出现
向左)删除若干个叶子节点,得到一棵完全二叉树,被删叶子节点的上一层(层次第二大的)节点因失去叶子,成为新的叶子节点。如此,叶子节点出现在最大层和次大层。只有当最大层叶子节点删除完,才可以删除次大层叶子节点,此时次大层变成新的最大层,叶子节点仍然只可能出现在层次最大的两层上。
设二叉树根节点的层次为0,对含有100个结点的二叉树,可能的最大树深和...
最大深度:99,因为根结点层次为0,每层只有一个结点,于是深度为100-1=99 最小深度:6,因为从满二叉树的角度看深度为6的结点个数为2的7次方减1,为127个,深度为5的满二叉树结点个数为2的6次方-1,为63个:
判断一棵二叉树是不是空树的标准是什么呢
若某非空二叉树的先序序列和后序序列正好相同,则该二叉树的形态是空树或是只有根结点的树。因为:若:根-左-右 == 左-右-根 当且仅当:左子树与右子树都为空树。
狄嵇苯妥: 先序遍历应该是FCIEDAGBH 前序遍历:FCIEDAGBH 二叉树如图 F / \\ C D \\ / \\ I A H / / E G \\ B
南华县19495043955: 已知一颗二叉树的层次序列为ABCDEFGHIJK,中序序列为DBGEHJACIF,请画出此二叉树. - ?
狄嵇苯妥: 层序遍历第一个就是根,也就是说啊为二叉树的根,看中序遍历,a左边的是a的左子树的节点,右边的是右子树节点 ,看层序 ,b是a的左子树的根,c是a的右子树的跟(因为c本身就是a的右子树,由第一步可知),依次类推.紫色表示左分支...
南华县19495043955: 已知一棵二叉树的先序遍历序列为ABDGHCEIF,它的中序遍历序列是BGDHAEICF,请给出其层次遍历序列. - ?
狄嵇苯妥: 根据先序遍历和中序遍历,我们可以将这颗二叉树画出来,如下图.所以,根据图片,得出层次遍历序列为:ABCDEFGHI.
南华县19495043955: 已知一棵二叉树的后序遍历序列为:ABCDEFGH,中序遍历序列为:CBDEAFHG a 试构造出该二叉树,给出构造过程 b 写出该二叉树的先序遍历的结果 - ?
狄嵇苯妥:[答案] 先序遍历应该是FCIEDAGBH 前序遍历:FCIEDAGBH 二叉树如图 F / \\ C D \\ / \\ I A H / / E G \\ B
南华县19495043955: 已知某二叉树中序遍历的结果是ABC,试画出其可能的二叉树五种形态. - ?
狄嵇苯妥: / \已知某二叉树中序遍历的结果是ABC,试画出其可能的二叉树五种形态 B C C A A / \ A C B A B C / \ / \ / \
南华县19495043955: 二叉树的层次遍历序列为:ABCDEFGHIJ; 二叉树的中序遍历序列为:DBGEHJACIF, - ?
狄嵇苯妥: 该二叉树为: 1. A 2. / \ 3. B C 4. / \ \ 5. D E F 6. / \ / 7. G H I
南华县19495043955: 已知二叉树的层次遍历序列为abcdefghigk中序遍历为dbgehjacikf,请构造一颗二 - ?
狄嵇苯妥: 你的层次遍历有两个g,是不是输入错了. 默认是abcdefghijka/ \b c/ \ \d e f/ \ /g h i\ \j k 层次遍历就是按层次输出得到 abcdefghijk,中序遍历是根结点在遍历左右子树之间,dbgeghacikf
南华县19495043955: 为什么已知一棵二叉树的前序遍历和后序遍历序列,不能唯一确定这棵二叉树? - ?
狄嵇苯妥: 这是因为同样的前序遍历和后序遍历序列,可以对应不同的二叉树. 例如:已知一棵二叉树的前序遍历和后序遍历序列分别为ABC和CBA,则以下四棵二叉树均符合要求: A A A A \ \ / / B B B B \ / / \ C C C C