二叉树的基本性质

二叉树的基本性质★树的基本定义1、树是n(n=0)个结点的有限集2、树的结点包含一个数据元素及若干指向其子树的分支3、结点拥有的子树数称为结点的度4、度为0的结点称为叶子或终端结点5、树的度是树内各结点的度的最大值6、结点的层次从根开始定义起，根为第一层，根的孩子为第二层7、树中结点的最大层次称为树的深度或高度8、如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中，最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。★二叉树的定义二叉树是一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。★二叉树的性质性质一在二叉树的第i层上至多有2i-1个结点性质二深度为k的二叉树至多有2k-1个结点（k=1）性质三对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1性质四具有n个结点的完全二叉树的深度为「log2n」+1性质五如果对一棵有n个结点的完全二叉树（其深度为「log2n」+1）的结点按层序编号（从第1层到第「log2n」+1层，每层从左到右），则对任一结点i（1≤i≤n），有①如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲PARENT(i)是结点「i/2」②如果2in，则结点n无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i③如果2i+1n，则结点i无右孩子，否则其右孩子RCHILD(i)是结点2i+1★先序遍历二叉树的操作定义若二叉树为空，则空操作，否则(1)访问根结点(2)先序遍历左子树(3)先序遍历右子树★中序遍历二叉树的操作定义若二叉树为空，则空操作，否则(1)中序遍历左子树(2)访问根结点(3)中序遍历右子树★后序遍历二叉树的操作定义若二叉树为空，则空操作，否则(1)后序遍历左子树(2)后序遍历右子树(3)访问根结点叶子结点就是没有孩子的结点，其度为0，度为二的结点是指有两个子数的结点。比如一棵完全二叉树有三层，叶子结点就是最下面那一层的结点数，没有孩子结点，就是4，度为二的结点有3个。