-
完全二叉樹
鎖定
完全二叉樹定義
如果對滿二叉樹的結點進行編號, 約定編號從根結點起, 自上而下, 自左而右。則深度為k的, 有n個結點的二叉樹, 當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時, 稱之為完全二叉樹。
[2]
從滿二叉樹和完全二叉樹的定義可以看出, 滿二叉樹是完全二叉樹的特殊形態, 即如果一棵二叉樹是滿二叉樹, 則它必定是完全二叉樹。
[2]
完全二叉樹性質
2、如果對一棵有n個結點的完全二叉樹的結點按層序編號, 則對任一結點i (1≤i≤n) 有:
[2]
完全二叉樹特點
完全二叉樹完全二叉樹判定
完全二叉樹算法思路
1>如果樹為空，則直接返回錯
2>如果樹不為空：層序遍歷二叉樹
2.1>如果一個結點左右孩子都不為空，則pop該節點，將其左右孩子入隊列；
2.1>如果遇到一個結點，左孩子為空，右孩子不為空，則該樹一定不是完全二叉樹；
完全二叉樹代碼實現
#include <iostream>
#include <queue>
using namespace std;
template <class T>
struct TreeNode
{
T data;
TreeNode<T> *left;
TreeNode<T> *right;
TreeNode(const T &x) : data(x),
left(NULL),
right(NULL) {}
};
template <class T>
bool IsComplete(TreeNode<T> *root)
{
//1.樹為空，返回錯誤
if (root == NULL)
{
return false;
}
//2.樹不為空
queue<TreeNode<T> *> q;
q.push(root);
while (!q.empty())
{
TreeNode<T> *top = q.front();
//2.1如果該節點兩個孩子都有，則直接pop
if (top->left && top->right)
{
q.pop();
q.push(top->left);
q.push(top->right);
}
//2.2如果該節點左孩子為空，右孩子不為空，則一定不是完全二叉樹
if (top->left == NULL && top->right)
{
return false;
}
//2.3如果該節點左孩子不為空，右孩子為空或者該節點為葉子節點，則該節點之後的所有結點都是葉子節點
if ((top->left && top->right == NULL) || (top->left == NULL && top->right == NULL))
{
if (NULL != top->left && NULL == top->right)
{
q.push(top->left);
}
q.pop(); //則該節點之後的所有結點都是葉子節點
while (!q.empty())
{
top = q.front();
if (top->left == NULL && top->right == NULL)
{
q.pop();
}
else
{
return false;
}
}
return true;
}
}
return true;
}
//滿二叉樹
void test1()
{
// 1
// 2 3
// 4 5 6 7
TreeNode<int> *node1 = new TreeNode<int>(1);
TreeNode<int> *node2 = new TreeNode<int>(2);
TreeNode<int> *node3 = new TreeNode<int>(3);
TreeNode<int> *node4 = new TreeNode<int>(4);
TreeNode<int> *node5 = new TreeNode<int>(5);
TreeNode<int> *node6 = new TreeNode<int>(6);
TreeNode<int> *node7 = new TreeNode<int>(7);
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->left = node6;
node3->right = node7;
cout << IsComplete<int>(node1) << endl;
}
//二叉樹為空
void test2()
{
cout << IsComplete<int>(NULL) << endl;
}
//3.二叉樹不為空，也不是滿二叉樹，遇到一個結點左孩子為空，右孩子不為空
void test3()
{
// 1
// 2 3
// 4 5 7
TreeNode<int> *node1 = new TreeNode<int>(1);
TreeNode<int> *node2 = new TreeNode<int>(2);
TreeNode<int> *node3 = new TreeNode<int>(3);
TreeNode<int> *node4 = new TreeNode<int>(4);
TreeNode<int> *node5 = new TreeNode<int>(5);
TreeNode<int> *node7 = new TreeNode<int>(7);
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->right = node7;
cout << IsComplete<int>(node1) << endl;
}
//4.二叉樹不為空，也不是滿二叉樹，遇到葉子節點,則該葉子節點之後的所有結點都為葉子節點
void test4()
{
// 1
// 2 3
// 4 5
TreeNode<int> *node1 = new TreeNode<int>(1);
TreeNode<int> *node2 = new TreeNode<int>(2);
TreeNode<int> *node3 = new TreeNode<int>(3);
TreeNode<int> *node4 = new TreeNode<int>(4);
TreeNode<int> *node5 = new TreeNode<int>(5);
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
cout << IsComplete<int>(node1) << endl;
}
//4.二叉樹不為空，也不是滿二叉樹，遇到左孩子不為空，右孩子為空的結點，則該節點之後的所有結點都為葉子節點
void test5()
{
// 1
// 2 3
// 4 5 6
TreeNode<int> *node1 = new TreeNode<int>(1);
TreeNode<int> *node2 = new TreeNode<int>(2);
TreeNode<int> *node3 = new TreeNode<int>(3);
TreeNode<int> *node4 = new TreeNode<int>(4);
TreeNode<int> *node5 = new TreeNode<int>(5);
TreeNode<int> *node6 = new TreeNode<int>(6);
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->left = node6;
cout << IsComplete<int>(node1) << endl;
}
int main()
{
test1();
/*test2();*/
/*test3();*/
/*test4();*/
/*test5();*/
return 0;
}
- 參考資料
-
- 1. 猿媛之家．Java程序員面試算法寶典：機械工業出版社，2019-06
- 2. 張曉煜,許立.完全二叉樹相關性質的補充證明[J].甘肅科技縱橫 ．中國知網[引用日期2020-05-20]
- 3. 判斷一棵樹是否是完全二叉樹 ．CSDN[引用日期2018-08-07]
- 4. 白鑫,甘勇,白朋飛.新編大學計算機[M].北京:中國鐵道出版社,2022.01:220.
