二叉树的面试题之判断树
在前面，已经介绍过了，有关二叉树中的一些基本操作，如果大家对这些还不是十分熟悉，可以参考上一篇文章，有关二叉树的遍历方式：http://blog.csdn.net/aaronlanni/article/details/78698559
今天，主要介绍一些二叉树中，常见的一些操作：
一、判断一棵树是否是完全二叉树
完全二叉树：如果一棵具有N个结点的二叉树的结构与满二叉树的前N个结点的结构相同，称为完全二叉树。
不是完全二叉树的情况：只有右子树，没有左子树，此时，这种情况不是完全二叉树，具体分为几下几种：
（1）只有左子树，没有右子树，但是在当前结点的同一层上，其后结点的左或者右子树存在
（2）只有右子树，没有左子树
思路：利用标记法
（1）只有右，没有左—–>返回false
（2）只有左，没有右—–>将标记改为true—–>判断下一个结点是否存在左或者右—–>存在—–>返回false（反之，继续取队头）—–>队列中为空，没有退出，则返回true
（3）左右孩子均存在—->压入到队列中
具体情况如图所示：
代码如下所示：
在此处，对函数在类中进行了一次封装，便于传递参数，对于封装的那一个函数，在这里就不一一给出了。
（一）代码一
bool _IsCompeteTree(pNode pRoot)
{
if (NULL == pRoot)
return true;
bool flag = false;
pNode pCur = NULL;
queue<pNode> q;
q.push(pRoot);
while (!q.empty())
{
pCur = q.front();
q.pop();
if (!flag)
{
if (pCur->_pLeft&&pCur->_pRight)
{
q.push(pCur->_pLeft);
q.push(pCur->_pRight);
}
//当前结点存在左孩子，因此之后的结点不能存在右孩子（同一层上）
if (pCur->_pLeft&&pCur->_pRight == NULL)
{
q.push(pCur->_pLeft);
flag = true;
}
if (pCur->_pLeft == NULL&&pCur->_pRight)
return false;
}
else
{
if (pCur->_pLeft || pCur->_pRight)
return false;
}
}
return true;
}（二）代码二
bool _IsCompeteTree1(pNode pRoot)
{
if (NULL == pRoot)
return true;
bool flag = false;
pNode pCur = NULL;
queue<pNode> q;
q.push(pRoot);
while (!q.empty())
{
pCur = q.front();
//当前结点只有右----->不是
if (pCur->_pLeft == NULL&&pCur->_pRight)
return false;
//当前结点只有左或者左右都不存在----->判断当前结点的下一个结点
//判断当前结点的下一个结点
if (flag&&(pCur->_pLeft != NULL || pCur->_pRight != NULL))
return false;
if (pCur->_pLeft == NULL || pCur->_pRight == NULL)
{
flag = true;
}
if (pCur->_pLeft)
q.push(pCur->_pLeft);
if (pCur->_pRight)
q.push(pCur->_pRight);
q.pop();
}
return true;
}（三）代码三
//左右子树分开
bool _IsCompeteTree2(pNode pRoot)
{
if (NULL == pRoot)
return true;
bool flag = false;
pNode pCur = NULL;
queue<pNode> q;
q.push(pRoot);
while (!q.empty())
{
pCur = q.front();
q.pop();
if (pCur->_pLeft)
{
if (flag)
return false;
q.push(pCur->_pLeft);
}
else
flag = true;
if (pCur->_pRight)
{
if (flag)
return false;
q.push(pCur->_pRight);
}
else
flag = true;
}
return true;
}以上判断是否是完全二叉树中，三种方法的大概思路是一致的，在第一种与第二种的思路一致，在第三种方法中，程序看上去比较简洁且比较容易实现，因此在这种方法中，效率能更高些。
测试代码如下所示：
void TestTree()
{
char array[] = "abd###ce##f";
BindaryTree<char> bt(array, strlen(array), '#');
//树存在
cout << "非空树1:"<<endl;
if (bt.IsCompeteTree())
cout << "是" << endl;
else
cout << "不是" << endl;
if (bt.IsCompeteTree1())
cout << "是" << endl;
else
cout << "不是" << endl;
if (bt.IsCompeteTree2())
cout << "是" << endl;
else
cout << "不是" << endl;
char array1[] = "abd##c##f";
BindaryTree<char> bt2(array1, strlen(array1), '#');
//树存在
cout << "非空树2:" << endl;
if (bt2.IsCompeteTree())
cout << "是" << endl;
else
cout << "不是" << endl;
if (bt2.IsCompeteTree1())
cout << "是" << endl;
else
cout << "不是" << endl;
if (bt2.IsCompeteTree2())
cout << "是" << endl;
else
cout << "不是" << endl;
//空树
BindaryTree<char> bt1;
cout << "空树:"<<endl;
if (bt1.IsCompeteTree())
cout << "是" << endl;
else
cout << "不是" << endl;
if (bt1.IsCompeteTree1())
cout << "是" << endl;
else
cout << "不是" << endl;
if (bt1.IsCompeteTree2())
cout << "是" << endl;
else
cout << "不是" << endl;
}结果如下所示：
二、判断一棵二叉树是否是平衡树
平衡树：左子树-右子树的绝对值<1，则这样的树称为平衡树
思路：
（1）空树—->平衡
（2）只有一个结点—->平衡
（3）多个结点—–>左子树的高度-右子树的高度的绝对会<1
在这里，就有一个问题，就是求二叉树的高度，因此，在这里，顺便给出二叉树高度的求解思路：
（1）空树—->返回0
（2）只有一个结点—->返回1
（3）多个结点—->左子树与右子树中较高的树加上1即可
平衡树
注意：在这里调用之时，调用的是经过封装的函数，从而为了传递参数的准确性。
具体代码实现如下所示：
封装前：
//判断一棵树是否是平衡二叉树
bool IsBalanceTree()
{
if (_IsBalanceTree(_pRoot))
return true;
else
return false;
}封装后
bool _IsBalanceTree(pNode pRoot)
{
if (pRoot == NULL)
return true;
if (pRoot->_pLeft == NULL&&pRoot->_pRight == NULL)
return true;
int Left = _Height(pRoot->_pLeft);
int Right = _Height(pRoot->_pRight);
return abs(Left - Right) < 1;
}求树的高度
代码实现如下所示：
size_t _Height(pNode pRoot)
{
if (NULL == pRoot)
return 0;
if (NULL == pRoot->_pLeft&&NULL == pRoot->_pRight)
return 1;
size_t left = _Height(pRoot->_pLeft);
size_t right = _Height(pRoot->_pRight);
return left >= right ? left + 1 : right + 1;
}测试代码如下所示：
void TestTree()
{
//利用数组
char array[] = "abd###ce##f";
BindaryTree<char> bt(array, strlen(array), '#');
cout << "非空树1（多个结点）---->" ;
if (bt.IsBalanceTree())
cout << "平衡" << endl;
else
cout << "不平衡" << endl;
cout << "非空树2（多个结点）---->" ;
char array1[] = "abd##c";
BindaryTree<char> bt1(array1, strlen(array1), '#');
if (bt1.IsBalanceTree())
cout << "平衡" << endl;
else
cout << "不平衡" << endl;
char array2[] = "a";
BindaryTree<char> bt2(array2, strlen(array2), '#');
cout << "非空树3（只有一个结点）---->" ;
if (bt2.IsBalanceTree())
cout << "平衡" << endl;
else
cout << "不平衡" << endl;
//空树
cout << "空树---->";
BindaryTree<char> bt3;
if (bt3.IsBalanceTree())
cout << "平衡" << endl;
else
cout << "不平衡" << endl;
}有关树的判断，就这么多了，还请大家多多关照！！！
只有不停的奔跑，才能不停留在原地！！！
上一篇： pandas的基本使用
下一篇： SDUT-2561 九九乘法表