<你想看的我这里都有😎 >
树的高度
//树的高度 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; }
设计思想：
- 如果即当前子树为空，则返回 0，表示该子树没有任何结点，因此高度为 0
- 如果传入的
root指针不为空，则执行以下操作：
a）调用递归函数TreeHeight(root->left)来计算左子树中结点到达最底层所需经过的边数，并将结果赋值给变量leftHeight
b）调用递归函数TreeHeight(root->right)来计算右子树中结点到达最底层所需经过边数，并将结果赋值给变量rightHeight
c）返回左右子树两者中较大者加上当前节点本身所代表边数（加1）作为该子问题下一级别解答（理解这里十分重要）
解释： 1、某个结点的左子树递归的三目运算符的运算结果都会在最后赋值给leftHeight，右子树递归的三目运算符的运算结果都会在最后赋值给rightHeight
2、每次调用 TreeHeight 函数时都会进行三目运算符的比较，如果是叶子结点，由于没有左右子树为空所以两次递归返回的值均为0，即leftHeight和rightHeight的值均为0（因为0>0为假，故：rightHeight+1，此时rightHeight+1里的+1是为了加上3结点本身的高度，不可能因为左右子树均为空就没有高度了，当前结点也算一个高度）比较后会返回1它被赋值给leftHeight，因为它是2结点的左子树递归得到的，同时它也告诉了2结点你的左子树高度只有1，然后2结点又会递归调用它的右子树但是由于右子树为NULL所以会返回0，所以此时leftHeight和rightHeight的值分别为1和0（因为1>0为真所以leftHeight+1，表明2结点的左子树大于右子树，左子树的高度可以代表2结点的高度）比较后会返回2它被赋值给leftHeight，因为它是1结点的左子树递归得到的，同时它也告诉了1结点你的左子树高度为2
3、然后1结点会递归它的右子树，剩余步骤与上面描述的大致相似，最后右递归会告诉1结点你的右子树高度为2（因为2>2为假所rightHeight+1，此时rightHeight+1里的+1是为了加上1结点本身的高度，不可能左右子树高度相等就没有高度了，当前结点也算一个高度，所以当前结点的左右子树结点高度相等，将当前左右结点子树的高度+1就是整个树的高度）
第k层结点的个数
//第k层结点的个数，k==2 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); }
设计思想：
- 树为空，返回0
- 树不为空且是第一层结点个数，返回1
- 树不为空且是第n(n>1)层结点的个数，返回(左子树的k-1层 + 右子树的k-1层)
k-1而不是k，k相当于判断条件count，当count==1的时候就相当于找到了我们要找的那一层，如果为k，那么递归的返回条件就不存在
解释：
1、查找第3层结点个数，即k == 3
2、树不为空，并且k != 1，所以递归结点1的左子树，结点2不为空，此时k-1 = 2 != 1，所以可以继续递归结点2的左子树，结点3不为空，此时k-1 = 1 == 1，所以返回1，即递归结点2左子树的返回值为1，然后递归结点2的右子树，右子树为空返回0，最后0+1=1，即递归结点1左子树的返回值为1，这说明结点1左子树第3层的结点个数为1
3、然后递归结点1的右子树，结点4不为空，此时k-1 = 2 != 1，所以可以继续递归结点4的左子树，结点5不为空，此时k - 1 =1 == 1，所以返回1，即递归结点4的左子树的返回值为1，然后递归结点4的右子树，结点6不为空，此时k - 1 =1 == 1（这是因为此时处于结点4的TreeLevelK函数中，此时的k为2），所以返回1，即递归结点4的右子树的返回值为1，最后1+1=2，即递归结点1右子树的返回值为2，这说明结点1右子树第3层的结点个数为2
4、最后结点1的左右子树均递归完毕，1+2=3，即该二叉树第3层的结点个数为3
查找值为x的结点
返回值为指针
//查找值为x的结点 TreeNode* TreeFind(TreeNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; TreeNode* ret1 = TreeFind(root->left, x); if (ret1) return ret1; TreeNode* ret2 = TreeFind(root->right, x); if (ret2) return ret2; return NULL; }
解释：整体过程不再进行文字解释，建议自己画图加深对代码的理解
注意对返回值NULL的处理和理解
返回值为布尔类型
//查找值为x的结点,返回值为布尔类型 bool TreeFind(TreeNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; return TreeFind(root->left, x) || TreeFind(root->right, x); }
解释：整体过程不再进行文字解释，建议自己画图加深对代码的理解
整体代码
#include <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }TreeNode; TreeNode* BuyTreeNode(int x) { TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); assert(node); node->data = x; node->left = NULL; node->right = NULL; return node; } TreeNode* CreatTree() { TreeNode* node1 = BuyTreeNode(1); TreeNode* node2 = BuyTreeNode(2); TreeNode* node3 = BuyTreeNode(3); TreeNode* node4 = BuyTreeNode(4); TreeNode* node5 = BuyTreeNode(5); TreeNode* node6 = BuyTreeNode(6); node1->left = node2; node1->right = node4; node2->left = node3; //node2->right = NULL; //node3->left = NULL; //node3->right = NULL; node4->left = node5; node4->right = node6; //node5->left = NULL; //node5->right = NULL; //node6->left = NULL; //node6->right= NULL; return node1; } void PrevOrder(TreeNode* root) { if(root == NULL) { printf("N "); return; } printf("%d ", root->data); PrevOrder(root->left); PrevOrder(root->right); } void InOrder(TreeNode* root) { if (root == NULL) { printf("N "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } void LaterOrder(TreeNode* root) { if (root == NULL) { printf("N "); return; } LaterOrder(root->left); LaterOrder(root->right); printf("%d ", root->data); } //总结点个数 int TreeSize(TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } //叶子结点个数 int TreeLeafSize(TreeNode* root) { //空树 返回0 if (root == NULL) return 0; //非空树，但是没有左右子树（叶子结点/仅有一个结点的树）返回1 if (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; } //第k层结点的个数 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); } //查找值为x的结点,返回值为指针 TreeNode* TreeFind(TreeNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; TreeNode* ret1 = TreeFind(root->left, x); if (ret1) return ret1; TreeNode* ret2 = TreeFind(root->right, x); if (ret2) return ret2; return NULL; } 查找值为x的结点,返回值为布尔类型 //bool TreeFind(TreeNode* root, BTDataType x) //{ // if (root == NULL) // return NULL; // if (root->data == x) // return root; // // return TreeFind(root->left, x) || TreeFind(root->right, x); //} int main() { TreeNode* root = CreatTree(); //前、中、后序遍历 PrevOrder(root); printf("\n"); InOrder(root); printf("\n"); LaterOrder(root); printf("\n"); //获取二叉树中的结点个数 printf("TreeSize：%d\n", TreeSize(root)); //叶子结点个数 printf("TreeLeafSize：%d\n",TreeLeafSize(root)); //树的高度 printf("TreeHeight：%d\n", TreeHeight(root)); //第k层结点个数 int k = 2; printf("TreeLevelK： % d\n", TreeLevelK(root,k)); //查找值为x的结点 int x = 2; printf("TreeLevelK： % d\n", TreeLevelK(root, x)); //查找值为x的结点 if (TreeFind(root, 5)) printf("找到了\n"); else printf("没找到\n"); return 0; }
~over~
