二叉树的基本性质图解 结构化程序的三种基本结构

性质一: 在二叉树的第i层上到多有2的i-1次方个结点(i>=1) 性质二: 深度为k的二叉树中至多含有2的k次方再-1个结点 性质三: 对任何一棵二叉树t,如果其终端结点数为n,双分支结点数为m,则n=m+1

一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点和两棵分别称为左子树和右子树的、互不相交的二叉树组成.

二叉树的定义:二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成.(在某个阶段都是两种结果的情形)二叉树的特点有:*每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点.*左子树和右子树是有顺序的,次序不能任意颠倒.*即使树中某结点只有一棵子树,也要区分它是左子树还是右子树.二叉树具有五种基本形态:1.空二叉树.2.只有一个根结点.3.根结点只有左子树.4.根结点只有右子树.5.根结点既有左子树又有右子树.

先介绍一下树:1.树的定义 树是一种常见的非线性的数据结构.树的递归定义如下:. 且其子树有左右之分(次序不能任意颠倒).1、二叉树的递归定义和基本形态 二叉.

树是N个结点的有限集.当N等于0时,是空树(有的书中定义,要求N大于0);当N等于1时,是只有一个根结点的树;当N大于1时,除根结点的其余结点又可以分为多个互补相交的有限集,这些集合又是一棵树,并称为根的子树.二叉树是树的一种,是指每个结点至多只有两棵子树的树.(也就是每个结点可以有两个子结点,可以有一个子结点,也可以没有子结点)其中没有子结点的结点就是叶子结点!如果只看概念不好理解的话,就利用图理解一下,就好理解多了.如果再想理解深一点的知识可以看一下严蔚敏编的数据结构书.

你没错,是书错了,的确2的K-1次方个结点.想不明白就自己画颗树,数学上也不难证明,很多数据结构的书都有教.

3级不会考推导的 呵呵 嘛 如果just for interest 给你解释下吧 设度1的结点数n1,总结点数n,则:n=n0+n1+n2; 此为式一 再看式二:n=n1+2*n2+1; 此式中n1+2*n2为除了根结点的结点数(自己画个树就明白了) 那么比较式一和式二 结论得证矣!

已经够详细了..

二叉树当中的结点只有度为0、1、2三种情况,度为0就是终端结点.构造二叉树的过程就是从原始结点开始“生长”结点的过程,初始状态下,原始结点就是终端结点,n0=1,n1=0,n2=0,每当一个原来的终端结点变成“1度结点”的时候只是把终端的位置向下移动了一点,n1++,不影响n0和n2,而每当一个原来的终端结点变成“2度结点”的时候,原来的终端消失,增加两个终端,总效果就是n0++,n2++,所以二叉树当中的n0和n2总是同步增加,即总是满足n0=n2+1

二叉树性质 性质1 :在二叉树的第i层上至少有2^(i-1)个结点 性质2:深度为k的二叉树至多有2^(k-1)个结点 性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1 性质4:具有n个结点的完全二叉树的深度是【log2n】+1(向下取整) 性质5:如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i(1in),有: 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是i/2 如果2i>n,则结点i无左孩子;如果2in,则其左孩子是2i 如果2i+1>n,则结点i无右孩子;如果2i+1n,则其右孩子是2i+1 还希望采纳