前言：我們前面已經(jīng)了解了二叉樹的一些概念，那么我們今天就來了解下二叉樹的遍歷實現(xiàn)和一些性質(zhì)。

二叉樹的遍歷方式有三種：前序，中序，后序。

前序：先根節(jié)點，再左子樹，最后右子樹。
中序：先左子樹，再根節(jié)點，最后右子樹。
后序：先左子樹，再右子樹，最后根節(jié)點。

前序遍歷：

void PrevOrder(TreeNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

如果我們的根節(jié)點為空就返回空，不為空就遞歸左子樹，如果左子樹為空就返回遞歸訪問右子樹。

中序遍歷：

void InOrder(TreeNode* root)
{if (root == NULL){printf("N");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

先訪問遍歷左子樹，再根節(jié)點，最后在訪問右子樹。

后序遍歷：

void Tailorder(TreeNode* root)
{if (root == NULL){printf("N");return;}Tailorder(root->left);Tailorder(root->right);printf("%d", root->data);
}

先遍歷左子樹，再遍歷右子樹，最后在根節(jié)點。

求二叉樹節(jié)點個數(shù)：

int TreeSize(TreeNode* root)
{return root == NULL ? 0 :TreeSize(root->left) +TreeSize(root->right) + 1;
}

我們遞歸實現(xiàn)，左子樹的節(jié)點個數(shù)加上右子樹的節(jié)點個數(shù)再加上根節(jié)點的個數(shù)就是節(jié)點的總個數(shù)。

求葉子結點的個數(shù)：

int TreeLeafSize(TreeNode* root)
{// 空 返回0if (root == NULL)return 0;// 不是空，是葉子 返回1if (root->left == NULL&& root->right == NULL)return 1;// 不是空 也不是葉子  分治=左右子樹葉子之和return TreeLeafSize(root->left) +TreeLeafSize(root->right);
}

求二叉樹的高度：

int TreeHeight(TreeNode* root)
{if (root == NULL)return 0;int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

因為我們的遞歸結合上三目操作符會使得非常的復雜，所以我們用一個數(shù)據(jù)來保存左右子樹的高度，我們的二叉樹的高度為左右子樹較高的那個子樹加上1，所以我們返回的是左右子樹高度更高的再加上1就是二叉樹的高度。

我們的代碼還可以進行改進，我們C語言的fmax函數(shù)：該函數(shù)的作用是比較兩個數(shù)得到較大的那一個數(shù)

int TreeHeight(TreeNode* root)
{if (root == NULL)return 0;return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}

求二叉樹第k層節(jié)點個數(shù)：

int TreeLevelK(TreeNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return TreeLevelK(root->left, k - 1)+ TreeLevelK(root->right, k - 1);
}

第k層的節(jié)點等于第k-1層的節(jié)點數(shù)相加。

現(xiàn)在我們要求第三層的節(jié)點數(shù)，相當于我們返回它的第二層，而我們的第二層節(jié)點數(shù)要返回我們的第一層節(jié)點數(shù)，我們的左子樹返回一個節(jié)點，右子樹返回兩個節(jié)點，所以就是三個節(jié)點。

如果對大家有所幫助的話就支持一下吧！