目錄

前言

查找值為x的結點

返回值為指針

返回值為布爾類型

整體代碼

---

前言

????????在二叉樹結點個數、葉子結點個數、樹的高度、第k層結點個數的計算（C語言）中，我們解決了關于二叉樹的部分問題，但是還有一個問題我們放在本篇解決。

查找值為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)
{//空樹 返回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;
}//第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");elseprintf("沒找到\n");return 0;
}

~over~