二叉树整理（三）

1、求二叉树中叶子节点的个数

递归解法：  （1）如果二叉树为空，返回0  （2）如果二叉树不为空且左右子树为空，返回1  （3）如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数  参考代码如下：

int GetLeafNodeNum(BinaryTreeNode * pRoot) { if(pRoot == NULL) return 0; if(pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL) return 1; int numLeft = GetLeafNodeNum(pRoot->m_pLeft); // 左子树中叶节点的个数 int numRight = GetLeafNodeNum(pRoot->m_pRight); // 右子树中叶节点的个数 return (numLeft + numRight); } 12345678910 12345678910

2、判断两棵二叉树是否结构相同

不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。  递归解法：  （1）如果两棵二叉树都为空，返回真  （2）如果两棵二叉树一棵为空，另一棵不为空，返回假  （3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假  参考代码如下：

bool StructureCmp(BinaryTreeNode * pRoot1, BinaryTreeNode * pRoot2) { if(pRoot1 == NULL && pRoot2 == NULL) // 都为空，返回真 return true; else if(pRoot1 == NULL || pRoot2 == NULL) // 有一个为空，一个不为空，返回假 return false; bool resultLeft = StructureCmp(pRoot1->m_pLeft, pRoot2->m_pLeft); // 比较对应左子树 bool resultRight = StructureCmp(pRoot1->m_pRight, pRoot2->m_pRight); // 比较对应右子树 return (resultLeft && resultRight); } 12345678910 12345678910

3、 判断二叉树是不是平衡二叉树

递归解法：  （1）如果二叉树为空，返回真  （2）如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假  参考代码：

bool IsAVL(BinaryTreeNode * pRoot, int & height) { if(pRoot == NULL) // 空树，返回真 { height = 0; return true; } int heightLeft; bool resultLeft = IsAVL(pRoot->m_pLeft, heightLeft); int heightRight; bool resultRight = IsAVL(pRoot->m_pRight, heightRight); if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) // 左子树和右子树都是AVL，并且高度相差不大于1，返回真 { height = max(heightLeft, heightRight) + 1; return true; } else { height = max(heightLeft, heightRight) + 1; return false; } }