[科普中國]-完全二叉樹

一棵深度為k的有n個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下、從左到右的順序進行編號，如果編號為i（1≤i≤n）的結(jié)點與滿二叉樹中編號為i的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。1

定義一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。2

根據(jù)二叉樹的性質(zhì)2, 滿二叉樹每一層的結(jié)點個數(shù)都達到了最大值, 即滿二叉樹的第i層上有2i-1個結(jié)點 (i≥1) 。2

如果對滿二叉樹的結(jié)點進行編號, 約定編號從根結(jié)點起, 自上而下, 自左而右。則深度為k的, 有n個結(jié)點的二叉樹, 當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時, 稱之為完全二叉樹。2

從滿二叉樹和完全二叉樹的定義可以看出, 滿二叉樹是完全二叉樹的特殊形態(tài), 即如果一棵二叉樹是滿二叉樹, 則它必定是完全二叉樹。2

性質(zhì)1.具有n個結(jié)點的完全二叉樹的深度為[Log2 n]+1;2

2.如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號, 則對任一結(jié)點i (1≤i≤n) 有:2

(1) 如果i=1, 則結(jié)點i是二叉樹的根, 無雙親;如果i>1, 則其雙親parent (i) 是結(jié)點[i/2].2

(2) 如果2i>n, 則結(jié)點i無左孩子, 否則其左孩子lchild (i) 是結(jié)點2i;2

(3) 如果2i+1>n, 則結(jié)點i無右孩子, 否則其右孩子rchild (i) 是結(jié)點2i+1.2

特點完全二叉樹的特點：葉子結(jié)點只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點集中在樹的左部。需要注意的是，滿二叉樹肯定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。1

完全二叉樹判定算法思路判斷一棵樹是否是完全二叉樹的思路3

1>如果樹為空，則直接返回錯
2>如果樹不為空：層序遍歷二叉樹
2.1>如果一個結(jié)點左右孩子都不為空，則pop該節(jié)點，將其左右孩子入隊列；
2.1>如果遇到一個結(jié)點，左孩子為空，右孩子不為空，則該樹一定不是完全二叉樹；
2.2>如果遇到一個結(jié)點，左孩子不為空，右孩子為空；或者左右孩子都為空；則該節(jié)點之后的隊列中的結(jié)點都為葉子節(jié)點；該樹才是完全二叉樹，否則就不是完全二叉樹；3

代碼實現(xiàn)#include #include using namespace std;template struct TreeNode{ T data; TreeNode *left; TreeNode *right; TreeNode(const T &x) : data(x), left(NULL), right(NULL) {}};template bool IsComplete(TreeNode *root){ //1.樹為空，返回錯誤 if (root == NULL) { return false; } //2.樹不為空 queue q; q.push(root); while (!q.empty()) { TreeNode *top = q.front(); //2.1如果該節(jié)點兩個孩子都有，則直接pop if (top->left && top->right) { q.pop(); q.push(top->left); q.push(top->right); } //2.2如果該節(jié)點左孩子為空，右孩子不為空，則一定不是完全二叉樹 if (top->left == NULL && top->right) { return false; } //2.3如果該節(jié)點左孩子不為空，右孩子為空或者該節(jié)點為葉子節(jié)點，則該節(jié)點之后的所有結(jié)點都是葉子節(jié)點 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(); //則該節(jié)點之后的所有結(jié)點都是葉子節(jié)點 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 *node1 = new TreeNode(1); TreeNode *node2 = new TreeNode(2); TreeNode *node3 = new TreeNode(3); TreeNode *node4 = new TreeNode(4); TreeNode *node5 = new TreeNode(5); TreeNode *node6 = new TreeNode(6); TreeNode *node7 = new TreeNode(7); node1->left = node2; node1->right = node3; node2->left = node4; node2->right = node5; node3->left = node6; node3->right = node7; cout