Question

以二叉链表作为二叉树的储存结构,判别两棵树是否相等所用到的递归方程是

Answer 1

问：以二叉链表作为二叉树的储存结构,判别两棵树是否相等所用到的递归方程是

答：您好，亲，以二叉链表作为二叉树的储存结构，判别两棵树是否相等所用到的递归方程是：具有n个结点的完全二叉树的深度为「log2n」+1 ！！！ 二叉树的计算方法： 若一棵二叉树为空，则其深度为0；否则其深度等于左子树和右子树的最大深度加1。即有如下递归模型： depth(b)=0 /*如果b=NULL*/ depth(b)=max(depth(b->left),depth(b->right))+1 /*其它*/ 因此，求二叉树深度的递归函数如下： int depth(btree *b) int dep1,dep2; if(b==NULL)return(0); else { dep1=depth(b->left); dep2=depth(b->right); if(dep1>dep2)return(dep1+1); else return(dep2+1); } 二叉树的基本性质 ★树的基本定义 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）。