二叉树宽度是什么?
二叉树的宽度定义为具有最多结点数的层中包含的结点数。
比如上图中,
第1层有1个节点,
第2层有2个节点,
第3层有4个节点,
第4层有1个节点,
可知,第3层的结点数最多
所以这棵二叉树的宽度就是4
def permute(str,prefix):
if len(str) == 0:
print prefix,
return
permute(str[1:],prefix)
permute(str[1:],prefix+str[0])
permute('123','')
这是解答的结果,和上面二叉树来表示完全一致
3 2 23 1 13 12 123
由于用Python的人并不是很多,所以我也用C写了个程序作为参考
#include
#include
#define BUFFER_SIZE 255
using namespace std;
void permute(char *src, char *prefix)
{
char buf[BUFFER_SIZE];
int len = strlen(prefix);
if (strlen(src) == 0)
{
cout<<prefix<<" ";
return;
}
strcpy(buf,prefix);
permute(src+1, prefix);
prefix[len] = *src;
prefix[len+1] = '\0';
permute(src+1, prefix);
}
int main(int argc,char argv)
{
char buf[BUFFER_SIZE] = "";
permute("12345",buf);
return 0;
}
相比之下,这个程序看起来要复杂得多,远不入Python那么简洁,这就是Python的魅力所在.
另外stone.zh也提供了一个简洁的方法,不过我现在也没有看懂,因为我不知道yield到底是什么做什么用的,不知道有没有知道,顺便告诉一下,谢过了先.
def permute(str):
for i in str:
yield i;
for j in permute(str[str.index(i)+1:]):
yield i+j
for i in permute("12345"):
print i,
宽度:节点的叶子数
深度:节点的层数
算法上有所谓的"宽度优先算法"和"深度优先算法"
二叉树的宽度定义为具有最多结点数的层中包含的结点数。
比如上图中,
第1层有1个节点,
第2层有2个节点,
第3层有4个节点,
第4层有1个节点,
可知,第3层的结点数最多
所以这棵二叉树的宽度就是4
要求二叉树的宽度的话,则可根据树的高度设置一个数组temp。temp[i]用于存放第i层上的结点数(即宽度)。在访问结点时,把相应计算该结点下一层的孩子数并存入相应数组元素中,遍历左子树后向上返回一层计算右子树的宽度,并取出最大的一个数组元素作为树的宽度。
#define M 10 //假设二叉树最多的层数
int Width(BinTree T)
{
int static n[M];//向量存放各层结点数
int static i=1;
int static max=0;//最大宽度
if(T)
{
if(i==1) //若是访问根结点
{
n[i]++; //第1层加1
i++; //到第2层
if(T->lchild)//若有左孩子则该层加1
n[i]++;
if(T->rchild)//若有右孩子则该层加1
n[i]++;
}
else
{ //访问子树结点
i++; //下一层结点数
if(T->lchild)
n[i]++;
if(T->rchild)
n[i]++;
}
if(max<n[i])max=n[i];//取出最大值
Width(T->lchild);//遍历左子树
i--; //往上退一层
Width(T->rchild);//遍历右子树
}
return max;
}//算法结束
希望可以给你帮助!
1:设置两个变量left,right。分别记录“以根节点为基准的偏离值”,再设置maxleft,和maxright记录遍历过程中遇到的最大值。
2:最后宽度就算两个值相加。
首先画出二叉树的层次图
然后取个数最多的一层就是了
什么是四叉树,数据结构的。有图例最好,谢谢。
四叉树是一种数据结构,是一种每个节点最多有四个子树的数据结构。 四叉树可以用来在数据库中放置和定位文件(称作记录或键)。这一算法通过不停的把要查找的记录分成4部分来进行匹配查找直到仅剩下一条记录为止。 在树中,记录被存储在叶子的位置上。这一名字的由来是因为记录被存储在端点上,它们...
C++用递归方法求出二叉树的宽度。
int Width(BTNode *t) \/\/递归求宽度 { int static n[20] = {0};\/\/向量存放各层结点数 int static i=0;int static max=0;\/\/最大宽度 if(t != NULL){ i++;n[i]++;if (n[i] > max) max = n[i];Width(t->lchild);Width(t->rchild);i--;return max;} return 0;} ...
什么叫三叉树、二叉树?
三叉树就是有三个枝叉,二叉树就是有两个枝叉。树,木本植物之总名,主要由根、干、枝、叶、花、果组成。随着计算机的发展,在数据结构中树被引申为由一个集合以及在该集合上定义的一种关系构成的,由根结点和若干颗子树构成的。树是具有木质树干及树枝的植物,多年生。一般将乔木称为树,主干植株...
什么是二叉树宽度优先遍历
就是按层次遍历,这棵树的机构可能是:a \/ \\ b c \/ \\ \/ d e f \/ \\ \/ g h i a \/ \\ b c \/ \/ \\ d e f \/ \\ \/ g h i a \/ \\ b c \/ \\ \\ d e f \/ \\ \/ g h i 不管哪一种大案都是C ...
请问二叉树的宽度(深度)优先遍历是怎么回事?
宽度优先就是层次遍历 深度优先就是前序遍历
二叉树的深度是多少?
一颗深度为k的二叉树,最多有(2^k)-1个节点,第k层最大节点数为2^(k-1)次方。性质1:二叉树的第i层上至多有2i-1(i≥1)个节点。性质2:深度为h的二叉树中至多含有2h-1个节点。性质3:若在任意一棵二叉树中,有n0个叶子节点,有n2个度为2的节点,则必有n0=n2+1。性质4:具有...
什么是二叉树
二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树,且有左右之分。二叉树是n个有限元素的集合,...
二叉树的高度是什么?
二叉树的高度是高度是从下往上数。二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树。完全二叉树的特点是叶子结点只可能出现在层序最大的两层上,并且某个结点的左分支下子孙的最大层序与右分支下子孙的最...
二叉树的深度和高度是怎样定义的?
楼主你好,因技术有限,所以在网上找了一些相关的资料,希望可以帮助到你。树是一种简单的非线性结构,所有元素之间具有明显的层次特性。在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没...
什么叫二叉树的度和深度?
二叉树结点的度数指该结点所含子树的个数,二叉树结点子树个数最多的那个结点的度为二叉树的度。二叉树的根结点所在的层数为1,根结点的孩子结点所在的层数为2,以此下去。深度是指所有结点中最深的结点所在的层数。
漕胥活血: 宽度:节点的叶子数 深度:节点的层数算法上有所谓的"宽度优先算法"和"深度优先算法"
康县13243514763: 二叉树中的宽度是什么呢?希望能举个例子说明下 - ?
漕胥活血: 二叉树的宽度定义为具有最多结点数的层中包含的结点数.比如上图中, 第1层有1个节点,第2层有2个节点,第3层有4个节点,第4层有1个节点, 可知,第3层的结点数最多 所以这棵二叉树的宽度就是4
康县13243514763: 什么是二叉树?二叉树拿来干什么? - ?
漕胥活血: 1、二叉树在图论中是这样定义的:二叉树是一个连通的无环图,并且每一个顶点的度不大于3.有根二叉树还要满足根结点的度不大于2.有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点.然而,没有足够的信息来区分左结点...
康县13243514763: 什么事二叉树的度? - ?
漕胥活血: 1.树的度——也即是宽度,简单地说,就是结点的分支数.以组成该树各结点中最大的度作为该树的度,如上图的树,其度为3;树中度为零的结点称为叶结点或终端结点.树中度不为零的结点称为分枝结点或非终端结点.除根结点外的分枝结点统称为内部结点.1. 树中结点的最大度数没有限制,而二叉树结点的最大度数为2;2. 树的结点无左、右之分,而二叉树的结点有左、右之分.…… 二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:(1)空二叉树——(a); (2)只有一个根结点的二叉树——(b);(3)只有左子树——(c);(4)只有右子树——(d);(5)完全二叉树——(e)
康县13243514763: 什么是二叉树? - ?
漕胥活血: 二叉树 在计算机科学中,二叉树是每个结点最多有两个子树的有序树.通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree).二叉树常被用作二叉查找树和二叉堆. 二叉树的每个结点至多只有二棵子树(不存在度大于2的...
康县13243514763: 计算机c语言中什么是“二叉树”? - ?
漕胥活血: 在计算机科学中,二叉树是每个结点最多有两个子树的有序树.通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree).二叉树常被用作二叉查找树和二叉堆或是二叉排序树. 二叉树的每个结点至多只有二棵子树(不存在度大...
康县13243514763: 以二叉链表为存储结构,写出求二叉树高度和宽度的算法 - ?
漕胥活血: 原题: 以二叉链表为存储结构,分别写出求二叉树高度及宽度的算法.所谓宽度是指在二叉树的各层上,具有结点数最多的那一层上的结点总数. 标准答案: ①求树的高度 思想:对非空二叉树,其深度等于左子树的最大深度加1. Int Depth(...
康县13243514763: 一棵二叉树有10个度为1的结点,7个度为二的结点,则该二叉树共有()个结点?什么叫“度”? - ?
漕胥活血: 25个 因为 总结点个数=总分枝数目+1 10*1+7*2+1=25 树的度——也即是宽度,简单地说,就是结点的分支数.以组成该树各结点中最大的度作为该树的度;树中度为零的结点称为叶结点或终端结点.树中度不为零的结点称为分枝结点或非终端结点.除根结点外的分枝结点统称为内部结点.
康县13243514763: 什么是二叉树宽度优先遍历 - ?
漕胥活血: 就是按层次遍历,这棵树的机构可能是: a / \ b c / \ / d e f / \ / g h i a / \ b c / / \ d e f / \ / g h i a / \ b c / \ \ d e f / \ / g h i 不管哪一种大案都是C
康县13243514763: 有关二叉树的问题 - ?
漕胥活血: 已经改好了#include#include //加stdio.h struct tree{ int data;struct tree *LC;struct tree *RC; }; //加分号 struct tree *create(struct tree *bt) //去掉typedef {int data;printf("Enter the fuck node number:\n");scanf("%d",&data);if(data==0) bt=...