Home Tags Posts tagged with "空二叉树"

空二叉树

注意二叉树可以为空!

结点数目>=0!!!

根结点为空也可以!

概念

编辑

二叉树是n(n≥0)个结点的有限集合。n=0的树称为空二叉树。n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 [2] 
显然,二叉树是一种有序树。二叉树中某个结点即使只有一个子树也要区分是左子树还是右子树 [2] 
二叉树中所有结点的形态共有5种:空结点、无左右子树结点、只有左子树结点、只有右子树结点和左右子树均存在的结点 [2] 

性质

编辑

性质1:具有n个结点的非空二叉树有且仅有n-1个分支 [3] 
性质2:非空二叉树的第i层最多有2i-1个结点 [3] 
性质3:深度为h的非空二叉树最多有2h-1个结点 [3] 
性质4:在任意非空二叉树中,若叶结点的数目为n0,度为2的结点数目为n2,则有关系n0=n2+1成立 [3] 
性质5:具有n(n>0)个结点的完全二又树的深度h= log2n+1 [3] 

二叉树的基本运算

编辑

1、CreateBTree(bt,str):已知二叉树的括号表示法表达字符串str,建二叉树bt [4] 
2、BTHeight(bt):求二叉树bt的高度 [4] 
3、NodeCount(bt):求二叉树bt的结点个数 [4] 
4、LeafCount(bt):求二叉树bt的叶子结点个数 [4] 

二叉树拓展

编辑

按照某种遍历方式对二叉树进行遍历,可以把二叉树中所有节点排列为一个线性序列。但是,二叉树中每个节点在这个序列中的直接前驱节点和直接后继节点在二叉树的存储结构中并没有反映出来,只有在对二叉树遍历的动态过程中才能够得到这些信息。线索二叉树就是研究在静态下,如何得到这样的信息 [5]  。
3、最优二叉树(哈夫曼树)
在权为w1,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或Huffman(赫夫曼)树 [6]  。
二叉平衡树(balanced binary tree)又称AVL树。它或者是一棵空二叉树,或者是具有下列性质的二叉树: [7] 
(1)它的左、右子树高度之差的绝对值不超过1 [7] 
(2)它的左、右子树都是二叉平衡树 [7]