已知二叉树的先序序列,怎么建立二叉树并求其叶子结点和深度????~
全部是左子树或 全部是右子树。 因为先序是 中前后,后续是 前后中。 如果两个子树都有孩子的话,那么按照上面的规定,就肯定不可能成立的,所以是特殊情况,只有一个孩子。
确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。
求解树的子树。找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树。若根节点左边或右边为空,则该方向子树为空;若根节点左边和右边都为空,则根节点已经为叶子节点。
递归求解树。将左子树和右子树分别看成一棵二叉树,重复1、2、3步,直到所有的节点完成定位。
一棵深度为k,且有2^k-1个结点的二叉树,称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且或者最后一层是满的,或者是在右边缺少连续若干结点。
扩展资料:
若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。
除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
平衡二叉树又被称为AVL树(区别于AVL算法),它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
参考资料来源:百度百科--二叉树
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct Node
{
char data;
Node*left_tree;
Node*right_tree;
}RootNode;
RootNode*CreateBinTree() //创建二叉树
{
char ch;
scanf("%c",&ch);
if (ch==',')
{
return NULL;
}
RootNode*t=(Node*)malloc(sizeof(Node));
t->data=ch;
t->left_tree=CreateBinTree();
t->right_tree=CreateBinTree();
return t;
}
void InTraBinTree(RootNode*T) //中序遍历二叉树
{
if (NULL!=T->left_tree)
{
InTraBinTree(T->left_tree);
}
printf("%c",T->data);
if (NULL!=T->right_tree)
{
InTraBinTree(T->right_tree);
}
}
void PoTraBinTree(RootNode*T) //后序遍历二叉树
{
if (NULL!=T->left_tree)
{
InTraBinTree(T->left_tree);
}
if (NULL!=T->right_tree)
{
InTraBinTree(T->right_tree);
}
printf("%c",T->data);
}
int GetLeavesCounts(RootNode*T) //获得叶子结点个数
{
int counts=0; //记录叶子结点个数
if (NULL==T->left_tree && NULL==T->right_tree)
{
return 1;
}
if (NULL!=T->left_tree)
{
counts+=GetLeavesCounts(T->left_tree);
}
if (NULL!=T->right_tree)
{
counts+=GetLeavesCounts(T->right_tree);
}
return counts;
}
int GetBinTreeDeep(RootNode*T) //获得二叉树深度
{
if (NULL==T->left_tree && NULL==T->right_tree)
{
return 1;
}
int left_deep=0,right_deep=0;
if (NULL!=T->left_tree)
{
left_deep=GetBinTreeDeep(T->left_tree); //获得左子树的深度
}
if (NULL!=T->right_tree)
{
right_deep=GetBinTreeDeep(T->right_tree); //获得右子树的深度
}
if (left_deep>right_deep)
{
return left_deep+1;
}
return right_deep+1;
}
void DestroyBinTree(RootNode*T) //销毁二叉树
{
if (NULL==T->left_tree && NULL==T->right_tree)
{
free(T);
return;
}
if (NULL!=T->left_tree)
{
DestroyBinTree(T->left_tree);
}
if (NULL!=T->right_tree)
{
DestroyBinTree(T->right_tree);
}
free(T);
}
void main()
{
system("color 0a");
printf("输入一个长度小于50个字符的字符串:");
RootNode*BinTree=CreateBinTree(); //创建二叉树
InTraBinTree(BinTree); //中序遍历
printf("
");
PoTraBinTree(BinTree); //后序遍历
printf("
");
printf("%d
",GetLeavesCounts(BinTree)); //输出叶子结点个数
printf("%d
",GetBinTreeDeep(BinTree)); //输出二叉树深度
DestroyBinTree(BinTree); //销毁二叉树
system("pause");
}
专门为你编的,若还有疑问请加QQ:2609135351
谭浩忠的书比较好、。易懂。
已知二叉树的前序和中序,构造该二叉树的方法是什么
答:已知一棵二叉树的先序遍历序列和中序遍历序列分别是ABDCEF、BDAECF,求二叉树及后序遍历序列。分析:先序遍历序列的第一个字符为根结点。对于中序遍历,根结点在中序遍历序列的中间,左边部分是根结点的左子树的中序遍历序列,右边部分是根结点的右子树的中序遍历序列。先序:ABDCEF --> A BD CEF ...
2021考研计算机复习备考:依据先序后序生成二叉树
答:思路:先序 pre = DLR,后序 post = LRD,D表示根结点,L表示左子树,R为右子树。从先序出发:取先序的第一个元素pre[0]做根,第二个元素pre[1]做左子树的根(不确定也可能是右子树的根,但是先序是根左右,先认为它是左子树的根),然后去后序序列找pre[1]这个元素的下标位置i,在后序...
已知二叉树的先序序列,怎么建立二叉树并求其叶子结点和深度???~_百度...
答:RootNode*CreateBinTree()//创建二叉树 { char ch;scanf("%c",&ch);if (ch==','){ return NULL;} RootNode*t=(Node*)malloc(sizeof(Node));t->data=ch;t->left_tree=CreateBinTree();t->right_tree=CreateBinTree();return t;} void InTraBinTree(RootNode*T)//中序遍历二叉树...
已知二叉树的先序遍历序列为ABDGCEF,中序遍历序列为DGBAECF,画出二叉树...
答:先看先序,其第一个为树的根,先序遍历是先根再左子树最后右子树,第一个肯定是树的根,先画A,A再中序遍历中左右都有,说明A有左子树也有右子树。
如何根据二叉树的前序遍历和中序遍历如何构建二叉树
答:1. 根据前序序列的第一个元素建立根结点;2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列;3. 在前序序列中确定左右子树的前序序列;4. 由左子树的前序序列和中序序列建立左子树;5. 由右子树的前序序列和中序序列建立右子树。已知一棵二叉树的后序序列和中序序列,构造该二叉树...
已知一棵二叉树的先序遍历序列为: A B C D E F G H I,中序遍历序列为...
答:回答:A / \ B D \ / \ C E F / \ G I \ H
知道二叉树先序,中序,后序其中的两个顺序列,如何画出二叉树
答:(1)由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。(2)由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。设先序序列为:a1,a2,……,an , 中序序列为:ap1,…,api, a1, …,apn 。则a1为根结点;ap1,…,api为左子树的中序序列,a2,…,ai-1为左子树的先序序...
根据先序和中序序列生成二叉树
答:1、先序或中序为空则返回,否则,通过先序序列创建根结点,再通过根节点在中序遍历的位置找出左右子树。2、在根绝点的左子树中,找左子树的根结点(在先序中找),转步骤1。3、在根节点的右子树中,找右子树的根结点(在先序中找),转步骤1。根据上述算法,可以看出创建出二叉树的关键在于先序...
...如果给出了遍历二叉树的前序序列和中序序列,则可以构造出唯一的一...
答:void postorder(BiTree T)//后序遍历 { if (T!=NULL){ postorder(T->lchild);postorder(T->rchild);printf ("%c",T->data);} } void main (){ cout<<"请输入要创建的二叉树包括空格:"<<endl ;BiTree T;CreatBiTree(T);//创建二叉树 cout<<"前序遍历的结果为:"<<endl;pre...
根据先序和中序,画出二叉树
答:二叉树示意图: A / \ B F / \ \ E C G \ / \ D H J \ I先序遍历序列: ABECDFGHIJ中序遍历序列: EBCDAFHIGJ后序遍历序列: EDCBIHJGFA//C语言测试程序#include "stdio.h"#include "stdlib.h"struct tree{ char data; ...