文章目录由二叉树覆盖，平衡完全二叉树和二叉树的二叉树等价于二叉树
满是二叉树
题目描述：
利用二叉树的链表记忆，设计算法来判断二叉树是否充满二叉树。
算法思想：
二叉树是一种深度为h、节点数为2h-1的二叉树。
因此，首先考虑的算法思路是求出二叉树的高度h，看其总结点数是否等于2h-1。
实现代码：
1首先给出求二叉树高度的算法。 这里给出递归求解的算法。 非递归算法可以参照递归算法和非递归算法求解二叉树的高度
//二叉树的高度intgetdepth(bnode*root ) if ) root==null ) { return 0； }intleft=getdepth(root-lchild )； intright=getdepth(root-rchild )； return leftright？ left 1 : right 1； } 2二叉树中节点个数的计算也使用递归算法。 该算法的想法是，如果二叉树为空，则返回节点数0，否则函数在根的左部分树和右部分树中包含的节点个数之和上加1。
//二叉树的节点数intcountnode(bnode*root ) if ) root==null ) return 0； 电子计数节点(root-rchild )计数节点(root-rchild ) 1； } 3那么，判断一棵二叉树是否充满二叉树的函数是
//判断是否为二叉树覆盖的boolisfull(bnode*root ) inth=getdepth ) root )的intsum=countnode(root； if(sum==(pow ) 2，h )-1 ) )返回true； else return false； }
二叉树题目描述：
利用二叉树的链表记忆，设计算法来判断二叉树是否为完全二叉树。
算法思想：
采用层序遍历算法对所有包含空节点的节点进行排队。 如果遇到空节点，则查询之后是否存在非空节点，如果存在，则二叉树不是完全二叉树。
实现代码：
booliscomplete(bnode*root ) { queueBNode * node； if(root==null )//空树满二叉树的return true； node.push(root； //根节点位于堆栈while (！ node.empty () ) { BNode *p=node.front； node.pop (； if(p！=null(//节点不为空，其左右子树为node.push(p-lchild )； node.push(p-rchild； (else ) /如果节点为空，则后跟非空节点while (！ node.empty () ) { BNode *p=node.front； node.pop (； if(p！=null(//如果节点不为空，二叉树为不完全二叉树return false； } } } return true； }
二叉树题目描述：
利用二叉树的链表记忆，设计算法来判断一个二叉树是否为平衡二叉树。 平衡二叉树是指左边的孩子和右边的孩子的高度差在1以下。
算法思想：
采用二叉树高度递归算法实现。 如果一个节点左右子树的高度差为1、-1、0，则算法返回true，否则返回false。
根据二叉树逆向扫描的思路，在扫描一个节点之前已经扫描了其左右子树，扫描每个节点时记录其深度，可以在扫描的同时判断每个节点是否平衡。
穿越某个节点的左右节点后，根据左右子节点的深度判断是否平衡，可以得到当前该节点的深度。 追溯根节点，可以判断该二叉树是否为平衡二叉树。
实现代码：
boolisbalance(bnode*root，int height ) if ) root==null ) /空树高度为0，平衡height=0； return t
rue; } int left,right; if(IsBalance(root->lchild, left) == false) return false; if(IsBalance(root->rchild, right) == false) return false; height = (left>right) ? left+1 : right+1; if(abs(left-right) <= 1) return true; else return false;}相似二叉树
题目描述：
设二叉树采用二叉链表存储，设计一个算法，判断两棵二叉树是否相似。
所谓二叉树T1和T2相似，指的是T1和T2都是空的二叉树或都只有一个根结点；或二叉树T1的左子树和T2的左子树是相似的，且T1的右子树和T2的右子树是相似的。
算法思想：
采用递归的思想求解，若T1和T2都是空树，则相似；若有一个为空另一个不空，则必然不相似；否则递归的比较它们的左、右子树是否相似。
实现代码：
bool IsSimilar(BNode *root1, BNode *root2){ int left,right; if(root1==NULL && root2==NULL){ return true; }else if(root1==NULL || root2==NULL){ return false; }else{ left = IsSimilar(root1->lchild, root2->lchild); right = IsSimilar(root1->rchild, root2->rchild); return left&&right; }}等价二叉树
题目描述：
设二叉树采用二叉链表存储，设计一个算法，判断两棵二叉树是否等价。
所谓两棵二叉树等价，是指二叉树T1和T2不仅在树形上相似，且对应结点的元素值都相等，则称这两棵二叉树等价。
算法思想：
采用递归的方法求解。若二叉树T1和二叉树T2都为空，则它们等价。如果两棵二叉树T1和T2中有一棵为空另一棵不为空，则它们不等价。当它们都不为空时判断根结点的元素值是否对应相等，若不是，则两棵二叉树不等价；若是，则继续判断它们的左子树和右子树是否等价，若它们都等价，则最后两个二叉树等价。
实现代码：
bool IsEqual(BNode *root1, BNode *root2){ if(root1==NULL && root2==NULL) return true; else if(root1==NULL || root2==NULL) return false; else if(root1->data != root2->data) return false; else if(IsEqual(root1->lchild, root2->lchild) && IsEqual(root1->rchild, root2->rchild)) return true; else return false;}