一顆二叉樹的結點數我們可以看作是根結點+左子樹結點數+右子樹結點數，那左右子樹的結點數又是多少呢？按照相同的方法繼續拆分，層層遞歸直到左右子樹為空樹，返回空樹的結點數0即可。遞歸代碼如下：

// 二叉樹節點個數
int TreeSize(TreeNode* root)
{return root == NULL? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

3.2 二叉樹的葉子結點數

左右子樹都為空的結點即是葉子結點。這里分為兩種情況：左右子樹都為空和左右子樹不都為空。

（1）當左右子樹都為空時，則這顆樹的葉子結點數為1(根節點)。

（2）當左右子樹不都為空，即根結點不是葉子結點時，這棵樹的葉子結點數就為左子樹葉子結點數+右子樹葉子結點數（空樹沒有葉子結點）。
?

// 二叉樹葉子節點個數
int  TreeLeafSize(TreeNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

3.3 二叉樹第k層結點數

一顆樹第k層的結點數我們可以拆分為其左子樹第k-1層結點+右子樹第k-1層結點。（注：當前節點為第一層）

（1）若為空樹，無論哪層節點數都是0

（2）若不是空樹且k==1,則只有一個節點（根節點）

// 二叉樹第k層節點個數
int TreeLevelKSize(TreeNode* root, int k)
{assert(k > 0);if (root!=NULL&&k == 1){return 1;}if (root == NULL){return 0;}if (k > 1){return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);}
}

// 判斷二叉樹是否是完全二叉樹
bool TreeComplete(TreeNode* root)
{Queue pq;QueueInit(&pq);if (root == NULL){QueueDestroy(&pq);return;}QueuePush(&pq, root);while (!QueueEmpty(&pq)){TreeNode* front = QueueFront(&pq);QueuePop(&pq);if (front == NULL){break;}QueuePush(&pq, front->left);QueuePush(&pq, front->right);}while (!QueueEmpty(&pq)){TreeNode* front = QueueFront(&pq);QueuePop(&pq);if (front != NULL){return false;}}QueueDestroy(&pq);return true;
}

四、二叉樹的查找

二叉樹的查找本質上就是一種遍歷，只不過是將之前的打印操作換為查找操作而已。我們可以使用前序遍歷來進行查找：

（1）先比較根結點是否為我們要查找的結點，如果是，返回根節點地址

（2）如果不是，遍歷左子樹，如果左子樹是，直接返回節點地址；不是則遍歷右子樹，如果右子樹是，直接返回節點地址，不是返回空，說明左右子樹都沒找到。

// 二叉樹查找值為x的節點
TreeNode* TreeFind(TreeNode* root, DataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}TreeNode* node1 = TreeFind(root->left, x);if (node1){return node1;}TreeNode* node2 = TreeFind(root->right, x);if (node2){return node2;}return NULL;
}

五、二叉樹的高度/深度

樹中結點的最大層次稱為二叉樹的高度。因此，一顆二叉樹的高度我們可以看作是

1(根結點)+左右子樹高度的較大值。層層遞歸下去直到遇到空樹返回0即可，

這里值得注意的是：不要寫成

return TreeHeight(root->left)>TreeHeight(root->right) ? TreeHeight(root->left)+1:TreeHeight(root->right)+1;
}

這里比較好左右子樹較大的一顆后，又會從新遞歸較大那顆子樹高度，會造成重復計算，時間復雜度增高。

我們要保存好左右子樹層數，避免重復計算，代碼如下：

//二叉樹的高度
int TreeHeight(TreeNode* root)
{if (root == NULL){return 0;}int left = TreeHeight(root->left);int right = TreeHeight(root->right);return  left>right ? left+1:right+1;
}

六、完全二叉樹的判斷

這里的思路利用了層序遍歷，不同的是，將空節點指針也入隊列，當我們遇到第一個空節點指針則退出循環，然后對隊列進行檢測，若第一個空節點指針以后全都是空，則為完全二叉樹，反之，不為完全二叉樹。

注：當在隊列遇到第一個空節點指針時，二叉樹中空節點指針之后所有非空節點指針全部進隊列

思路解析圖如下：