二叉樹的概念

二叉樹（Binary Tree）是數(shù)據(jù)結(jié)構(gòu)中一種非常重要的樹形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，通常稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。這種結(jié)構(gòu)使得二叉樹在數(shù)據(jù)存儲(chǔ)和查找等方面具有高效性，廣泛應(yīng)用于各種算法和程序中。

節(jié)點(diǎn)（Node）：二叉樹的基本單元，用于存儲(chǔ)數(shù)據(jù)和指向子節(jié)點(diǎn)的指針。每個(gè)節(jié)點(diǎn)可以包含三個(gè)部分：數(shù)據(jù)域、左指針和右指針。數(shù)據(jù)域用于存儲(chǔ)節(jié)點(diǎn)的值，左指針指向左子節(jié)點(diǎn)，右指針指向右子節(jié)點(diǎn)。
特點(diǎn)
有序性：二叉樹的每個(gè)節(jié)點(diǎn)都有明確的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)之分，這種有序性使得二叉樹在數(shù)據(jù)查找和遍歷等方面具有高效性。
遞歸性：二叉樹的很多操作都可以通過遞歸的方式來實(shí)現(xiàn)，例如遍歷、插入和刪除等。這種遞歸性使得二叉樹的處理變得簡(jiǎn)潔而統(tǒng)一。
靈活性：二叉樹可以根據(jù)實(shí)際需求進(jìn)行不同的擴(kuò)展和變形，例如平衡二叉樹、二叉搜索樹等，以滿足不同的應(yīng)用場(chǎng)景。

代碼實(shí)現(xiàn)

以下代碼實(shí)現(xiàn)的是最普通的二叉樹

二叉樹的定義

這段代碼定義了一個(gè)簡(jiǎn)單的二叉樹節(jié)點(diǎn)結(jié)構(gòu)體，其中包含指向左子樹和右子樹的指針以及一個(gè)整數(shù)值。
通過這種結(jié)構(gòu)，我們可以構(gòu)建一個(gè)二叉樹，其中每個(gè)節(jié)點(diǎn)都有一個(gè)值，以及可能存在的左子樹和右子樹。

// 首先，定義一個(gè)結(jié)構(gòu)體類型別名BinTreeNode，這個(gè)結(jié)構(gòu)體用于表示二叉樹的節(jié)點(diǎn)。  
typedef struct BinTreeNode {  // left是一個(gè)指向左子樹根節(jié)點(diǎn)的指針。  // 在二叉樹中，每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，這里left表示節(jié)點(diǎn)的左子樹。  struct BinTreeNode* left;   // right是一個(gè)指向右子樹根節(jié)點(diǎn)的指針。  // 與left相似，right表示節(jié)點(diǎn)的右子樹。  struct BinTreeNode* right;  // val表示節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)值，這里是一個(gè)整型值。  int val;  } BTNode; // BTNode是這個(gè)結(jié)構(gòu)體的類型別名，方便后續(xù)在代碼中使用。  

創(chuàng)建一棵樹并初始化

BuyNode函數(shù)是一個(gè)用于創(chuàng)建和初始化二叉樹節(jié)點(diǎn)的函數(shù)。
它接受一個(gè)整數(shù)val作為參數(shù)，動(dòng)態(tài)分配內(nèi)存來創(chuàng)建一個(gè)新的BTNode結(jié)構(gòu)體實(shí)例， 并將該實(shí)例的left和right指針初始化為NULL，val成員設(shè)置為傳入的參數(shù)值。
如果內(nèi)存分配失敗，則打印錯(cuò)誤信息并返回NULL。
如果成功，則返回指向新創(chuàng)建節(jié)點(diǎn)的指針。

// 函數(shù)用于創(chuàng)建一個(gè)新的二叉樹節(jié)點(diǎn)，并初始化它  
BTNode* BuyNode(int val) {  // 使用malloc動(dòng)態(tài)分配內(nèi)存空間，大小為BTNode結(jié)構(gòu)體的大小  // 并將分配到的內(nèi)存地址強(qiáng)制轉(zhuǎn)換為BTNode指針類型，賦值給newnode  BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));  // 檢查malloc是否成功分配了內(nèi)存  // 如果newnode為NULL，說明內(nèi)存分配失敗  if (newnode == NULL) {  // 如果內(nèi)存分配失敗，則打印錯(cuò)誤信息  perror("malloc fail");  // 并返回NULL，表示節(jié)點(diǎn)創(chuàng)建失敗  return NULL;  }  // 初始化新節(jié)點(diǎn)的左子樹指針為NULL，表示當(dāng)前沒有左子樹  newnode->left = NULL;  // 初始化新節(jié)點(diǎn)的右子樹指針為NULL，表示當(dāng)前沒有右子樹  newnode->right = NULL;  // 將傳入的val值賦給新節(jié)點(diǎn)的val成員，設(shè)置節(jié)點(diǎn)的值  newnode->val = val; // 注意這里的val是函數(shù)參數(shù)，表示節(jié)點(diǎn)的數(shù)據(jù)值  // 返回新創(chuàng)建的節(jié)點(diǎn)指針，供外部使用  return newnode; // 節(jié)點(diǎn)創(chuàng)建成功，返回其地址  
}  

組裝二叉樹

CreatNode函數(shù)是一個(gè)用于組裝特定二叉樹的函數(shù)。
它首先調(diào)用BuyNode函數(shù)來創(chuàng)建6個(gè)獨(dú)立的節(jié)點(diǎn)，并分別給它們賦值。
然后，它將這些節(jié)點(diǎn)通過它們的left和right指針連接起來，形成一個(gè)具有特定結(jié)構(gòu)的二叉樹。
最后，它返回根節(jié)點(diǎn)的指針，以便外部可以訪問和操作這棵樹。

// 函數(shù)用于組裝（創(chuàng)建并連接）一個(gè)具體的二叉樹，并返回其根節(jié)點(diǎn)指針  
BTNode* CreatNode() {  // 調(diào)用BuyNode函數(shù)創(chuàng)建6個(gè)新的二叉樹節(jié)點(diǎn)，并分別初始化它們的值為1到6  BTNode* n1 = BuyNode(1); // 創(chuàng)建值為1的節(jié)點(diǎn)，并作為根節(jié)點(diǎn)  BTNode* n2 = BuyNode(2); // 創(chuàng)建值為2的節(jié)點(diǎn)  BTNode* n3 = BuyNode(3);  BTNode* n4 = BuyNode(4);  BTNode* n5 = BuyNode(5); BTNode* n6 = BuyNode(6);  // 下面的代碼將這些節(jié)點(diǎn)連接起來，形成一個(gè)具體的二叉樹結(jié)構(gòu)  n1->left = n2;      // 將n2節(jié)點(diǎn)設(shè)置為n1節(jié)點(diǎn)的左子樹  n1->right = n4;     // 將n4節(jié)點(diǎn)設(shè)置為n1節(jié)點(diǎn)的右子樹  n2->left = n3;      // 將n3節(jié)點(diǎn)設(shè)置為n2節(jié)點(diǎn)的左子樹（n2沒有右子樹）  n4->left = n5;      // 將n5節(jié)點(diǎn)設(shè)置為n4節(jié)點(diǎn)的左子樹  n4->right = n6;     // 將n6節(jié)點(diǎn)設(shè)置為n4節(jié)點(diǎn)的右子樹  //以上是我們?nèi)斯そǖ囊活w二叉樹// 返回根節(jié)點(diǎn)的指針，這樣外部就可以通過這個(gè)指針來訪問整棵樹了  return n1; // 根節(jié)點(diǎn)是n1，所以返回n1的指針  
}  

前序遍歷

從這個(gè)函數(shù)開始，后面的函數(shù)基本都是遞歸了，強(qiáng)烈建議在剛開始學(xué)的時(shí)候多畫幾遍遞歸展開圖，理解每個(gè)函數(shù)的運(yùn)行過程，熟練之后就可以直接在腦海里理解過程了。
PreOrder函數(shù)實(shí)現(xiàn)了二叉樹的前序遍歷。
前序遍歷的順序是：先訪問根節(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。
在遍歷過程中，如果遇到空節(jié)點(diǎn)（即子樹不存在），則打印"N "。這里打印N是為了更易于理解。
這個(gè)函數(shù)通過遞歸的方式簡(jiǎn)潔地實(shí)現(xiàn)了前序遍歷的邏輯。

// 定義前序遍歷函數(shù)，參數(shù)為二叉樹的根節(jié)點(diǎn)指針  
void PreOrder(BTNode* root) {  // 首先檢查根節(jié)點(diǎn)是否為空  if (root == NULL) {  // 如果根節(jié)點(diǎn)為空，則打印"N "表示此處無節(jié)點(diǎn)（NULL的簡(jiǎn)寫）  printf("N ");  // 然后直接返回，不再繼續(xù)遍歷  return;  }  // 如果根節(jié)點(diǎn)不為空，則首先打印根節(jié)點(diǎn)的值  printf("%d ", root->val);  // 接著遞歸地調(diào)用前序遍歷函數(shù)，傳入左子樹的根節(jié)點(diǎn)  // 這樣會(huì)先遍歷整個(gè)左子樹  PreOrder(root->left);  // 最后遞歸地調(diào)用前序遍歷函數(shù)，傳入右子樹的根節(jié)點(diǎn)  // 這樣會(huì)遍歷整個(gè)右子樹  PreOrder(root->right);  
}  

中序遍歷

InOrder函數(shù)遞歸地先處理左子樹，然后打印當(dāng)前節(jié)點(diǎn)的值，最后處理右子樹，直到所有節(jié)點(diǎn)都被訪問并打印出來。如果樹中存在空指針（即某個(gè)節(jié)點(diǎn)沒有左子節(jié)點(diǎn)或右子節(jié)點(diǎn)），則打印"N "來表示該位置為空。
中序遍歷的順序是：先遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遍歷右子樹。
在遍歷過程中，如果遇到空節(jié)點(diǎn)（即子樹不存在），則打印"N "。這里打印N是為了更易于理解。
這個(gè)函數(shù)也是通過遞歸的方式實(shí)現(xiàn)的，每次遞歸都處理當(dāng)前節(jié)點(diǎn)的左子樹、自身和右子樹。

// 定義中序遍歷函數(shù)，參數(shù)為二叉樹的根節(jié)點(diǎn)指針  
void InOrder(BTNode* root) {  // 首先檢查根節(jié)點(diǎn)是否為空  if (root == NULL) {  // 如果當(dāng)前節(jié)點(diǎn)為空（即已經(jīng)遍歷到葉子節(jié)點(diǎn)下面，或者子樹不存在）  // 則打印"N "表示此處無節(jié)點(diǎn)值可輸出  printf("N ");  // 打印完畢后直接返回，不再繼續(xù)遍歷  return;  }  // 如果當(dāng)前節(jié)點(diǎn)不為空，則先遞歸調(diào)用中序遍歷函數(shù)，傳入左子節(jié)點(diǎn)  // 這樣可以確保在打印當(dāng)前節(jié)點(diǎn)之前，先遍歷并打印整個(gè)左子樹  InOrder(root->left);  // 遍歷完左子樹后，回到當(dāng)前節(jié)點(diǎn)，并打印當(dāng)前節(jié)點(diǎn)的值  printf("%d ", root->val);  // 打印完當(dāng)前節(jié)點(diǎn)值后，遞歸調(diào)用中序遍歷函數(shù)，傳入右子節(jié)點(diǎn)  // 這樣可以確保在打印完當(dāng)前節(jié)點(diǎn)后，繼續(xù)遍歷并打印整個(gè)右子樹  InOrder(root->right);  
}  

后序遍歷

PostOrder函數(shù)實(shí)現(xiàn)了二叉樹的后序遍歷。
后序遍歷的順序是：先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點(diǎn)。
這個(gè)過程一直進(jìn)行到所有節(jié)點(diǎn)都被訪問并打印出來為止。
遍歷過程中，若遇到空節(jié)點(diǎn)（即某節(jié)點(diǎn)沒有左子節(jié)點(diǎn)或右子節(jié)點(diǎn)，或子樹不存在），則打印"N "。
函數(shù)通過遞歸方式實(shí)現(xiàn)，遞歸的基準(zhǔn)情況是節(jié)點(diǎn)為空時(shí)返回。

// 定義后序遍歷函數(shù)，參數(shù)為二叉樹的根節(jié)點(diǎn)指針  
void PostOrder(BTNode* root) {  // 首先檢查傳入的根節(jié)點(diǎn)是否為空  if (root == NULL) {  // 如果根節(jié)點(diǎn)為空，表示已經(jīng)遍歷到了葉子節(jié)點(diǎn)下面或者子樹不存在  // 在此處打印"N "，作為空節(jié)點(diǎn)（NULL）的占位符輸出  printf("N ");  // 打印完空節(jié)點(diǎn)后，直接返回，不再繼續(xù)遞歸遍歷  return;  }  // 如果當(dāng)前節(jié)點(diǎn)不為空，則先遞歸調(diào)用后序遍歷函數(shù)，傳入左子節(jié)點(diǎn)  // 后序遍歷的順序是先遍歷左子樹  PostOrder(root->left);  // 接著遞歸調(diào)用后序遍歷函數(shù)，傳入右子節(jié)點(diǎn)  // 后序遍歷接下來遍歷右子樹  PostOrder(root->right);  // 在確保左右子樹都已經(jīng)遍歷完成后，打印當(dāng)前節(jié)點(diǎn)的值  // 后序遍歷的最后一步是訪問（打印）根節(jié)點(diǎn)  printf("%d ", root->val);  
}  

計(jì)算樹的結(jié)點(diǎn)個(gè)數(shù)

TreeSize函數(shù)用于遞歸地計(jì)算一棵二叉樹中節(jié)點(diǎn)的總數(shù)。
函數(shù)首先檢查傳入的根節(jié)點(diǎn)是否為空，如果為空則返回0，表示沒有節(jié)點(diǎn)。
如果根節(jié)點(diǎn)不為空，則函數(shù)遞歸地調(diào)用自身來計(jì)算左子樹和右子樹的節(jié)點(diǎn)數(shù)，
然后將這兩個(gè)數(shù)相加，并加上1（代表當(dāng)前根節(jié)點(diǎn)），從而得到整棵樹的節(jié)點(diǎn)總數(shù)。
對(duì)于每個(gè)非空節(jié)點(diǎn)，函數(shù)會(huì)分別計(jì)算其左子樹和右子樹的節(jié)點(diǎn)數(shù)，然后將這兩個(gè)數(shù)目相加，并加上當(dāng)前節(jié)點(diǎn)自身（計(jì)數(shù)為1），從而得到以當(dāng)前節(jié)點(diǎn)為根的子樹的節(jié)點(diǎn)總數(shù)。這個(gè)過程會(huì)一直遞歸進(jìn)行，直到遍歷完整棵樹，最終返回整棵樹的節(jié)點(diǎn)總數(shù)。
遞歸方法寫的代碼一般都比較短，但是比一般方法更難以理解

// 定義計(jì)算二叉樹節(jié)點(diǎn)個(gè)數(shù)的函數(shù)，參數(shù)為二叉樹的根節(jié)點(diǎn)指針  
int TreeSize(BTNode* root) {  // 使用三目運(yùn)算符（條件運(yùn)算符）判斷根節(jié)點(diǎn)是否為空  // 如果root為空，說明已經(jīng)遍歷到了葉子節(jié)點(diǎn)下面或者子樹不存在，直接返回0  // 否則，遞歸地計(jì)算左子樹的節(jié)點(diǎn)個(gè)數(shù)和右子樹的節(jié)點(diǎn)個(gè)數(shù)，并將它們相加，再加上根節(jié)點(diǎn)自身（即+1）  return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;  
}  

求二叉樹第K層的結(jié)點(diǎn)個(gè)數(shù)

TreeKLevel函數(shù)通過遞歸的方式求解二叉樹第k層的節(jié)點(diǎn)個(gè)數(shù)。
以下方法的核心是：當(dāng)前樹的第k層個(gè)數(shù) ==左子樹的第k-1層個(gè)數(shù) +左子樹的第k-1層個(gè)數(shù)
遞歸的基準(zhǔn)情況有兩種：一是當(dāng)節(jié)點(diǎn)為空時(shí)返回0，二是當(dāng)k等于1時(shí)返回1。
對(duì)于其他情況，函數(shù)會(huì)遞歸地調(diào)用自身來計(jì)算左子樹和右子樹中第k-1層的節(jié)點(diǎn)數(shù)，
然后將這兩個(gè)數(shù)相加得到結(jié)果。這個(gè)過程會(huì)一直進(jìn)行下去，直到達(dá)到基準(zhǔn)情況為止。
小結(jié)：這段代碼的核心思想是利用遞歸逐層向下遍歷二叉樹，同時(shí)記錄當(dāng)前所在的層數(shù)。當(dāng)遍歷到目標(biāo)層時(shí)，返回該層的節(jié)點(diǎn)數(shù)。由于二叉樹的層數(shù)是從根節(jié)點(diǎn)開始計(jì)算的，因此在每次遞歸調(diào)用時(shí)，都需要將目標(biāo)層數(shù)k減去1，以正確地定位到下一層。通過這種方式，函數(shù)能夠準(zhǔn)確地計(jì)算出二叉樹中任意一層的節(jié)點(diǎn)個(gè)數(shù)。

// 定義函數(shù)TreeKLevel，用于求二叉樹第k層的節(jié)點(diǎn)個(gè)數(shù)  
// 參數(shù)root為二叉樹的根節(jié)點(diǎn)指針，k為目標(biāo)層數(shù)  
int TreeKLevel(BTNode* root, int k) {  // 如果根節(jié)點(diǎn)為空，說明已經(jīng)遍歷到空樹或者子樹不存在  // 直接返回0，表示第k層沒有節(jié)點(diǎn)  if (root == NULL) {  return 0;  }  // 如果k等于1，說明當(dāng)前層就是第一層（根節(jié)點(diǎn)所在的層）  // 直接返回1，因?yàn)楦?jié)點(diǎn)是唯一一個(gè)在第1層的節(jié)點(diǎn)  if (k == 1) {  return 1;  }  // 如果k大于1，說明目標(biāo)層在根節(jié)點(diǎn)的下面  // 遞歸地調(diào)用TreeKLevel函數(shù)，分別傳入左子樹和右子樹的根節(jié)點(diǎn)，以及k-1作為新的層數(shù)  // 然后將兩個(gè)遞歸調(diào)用的結(jié)果相加，得到第k層的節(jié)點(diǎn)總數(shù)  // 注意這里k要減1，是因?yàn)橥乱粚舆f歸時(shí)，層數(shù)要相應(yīng)地減少  return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);  
}  

求二叉樹高度

該函數(shù)通過遞歸的方式計(jì)算二叉樹的高度。
遞歸的基準(zhǔn)情況是當(dāng)節(jié)點(diǎn)為空時(shí)，返回1（表示空樹或不存在的高度，加1是為了方便遞歸計(jì)算）。
/對(duì)于非空節(jié)點(diǎn)，函數(shù)會(huì)分別計(jì)算其左子樹和右子樹的高度，然后取兩者中的較大值，并加1作為當(dāng)前樹的高度。
返回值是整棵樹的高度。

// 定義函數(shù)TreeHigh，用于求二叉樹的高度  
// 參數(shù)root為二叉樹的根節(jié)點(diǎn)指針  
int TreeHigh(BTNode* root) {  // 如果根節(jié)點(diǎn)為空，說明當(dāng)前子樹不存在或?yàn)榭諛? // 按照常規(guī)定義，空樹的高度為0，但這里為了遞歸方便，返回1表示高度為0的層級(jí)上加1  // 注意：這種定義在遞歸的上下文中是合理的，但在實(shí)際應(yīng)用中可能需要調(diào)整，以確?？諛涓叨葹?  if (root == NULL) {  return 1;  }  // 遞歸調(diào)用TreeHigh函數(shù)，計(jì)算左子樹的高度  int leftHigh = TreeHigh(root->left);  // 遞歸調(diào)用TreeHigh函數(shù)，計(jì)算右子樹的高度  int rightHigh = TreeHigh(root->right);  // 使用三目運(yùn)算符比較左子樹和右子樹的高度  // 返回較高的一邊的高度，并加上1（加上根節(jié)點(diǎn)所在的這一層）  return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;  
}  

查找X所在的結(jié)點(diǎn)

TreeFind函數(shù)是一個(gè)遞歸函數(shù)，用于在二叉樹中查找值為x的節(jié)點(diǎn)。
它首先檢查根節(jié)點(diǎn)是否為空或者是否就是要找的節(jié)。如果根節(jié)點(diǎn)為空，則返回NULL表示未找到。如果根節(jié)點(diǎn)的值等于x，則返回根節(jié)點(diǎn)的指針。
否則，函數(shù)會(huì)遞歸地在左子樹和右子樹中查找，直到找到目標(biāo)節(jié)點(diǎn)或者遍歷完整棵樹。
如果在整棵樹中都沒有找到值為x的節(jié)點(diǎn)，則最終返回NULL。

// 定義函數(shù)TreeFind，用于在二叉樹中查找值為x的節(jié)點(diǎn)，并返回該節(jié)點(diǎn)的指針  
// 參數(shù)root為二叉樹的根節(jié)點(diǎn)指針，x為要查找的值  
BTNode* TreeFind(BTNode* root, int x) {  // 如果根節(jié)點(diǎn)為空，說明已經(jīng)遍歷到了空子樹或者樹本身為空  // 直接返回NULL，表示在當(dāng)前子樹中沒有找到值為x的節(jié)點(diǎn)  if (root == NULL) {  return NULL;  }  // 如果根節(jié)點(diǎn)的值等于x，說明找到了目標(biāo)節(jié)點(diǎn)  // 直接返回根節(jié)點(diǎn)的指針  if (root->val == x) {  return root;  }  // 遞歸調(diào)用TreeFind函數(shù)，在左子樹中查找值為x的節(jié)點(diǎn)  // 將返回的節(jié)點(diǎn)指針賦值給ret1  BTNode* ret1 = TreeFind(root->left, x);  // 如果ret1不為空，說明在左子樹中找到了值為x的節(jié)點(diǎn)  // 直接返回ret1，即找到了目標(biāo)節(jié)點(diǎn)的指針  if (ret1) {  return ret1;  }  // 如果左子樹中沒有找到，繼續(xù)遞歸調(diào)用TreeFind函數(shù)，在右子樹中查找值為x的節(jié)點(diǎn)  // 將返回的節(jié)點(diǎn)指針賦值給ret2  BTNode* ret2 = TreeFind(root->right, x);  // 如果ret2不為空，說明在右子樹中找到了值為x的節(jié)點(diǎn)  // 直接返回ret2，即找到了目標(biāo)節(jié)點(diǎn)的指針  if (ret2) {  return ret2;  }  // 如果左右子樹中都沒有找到值為x的節(jié)點(diǎn)，說明整個(gè)樹中都不存在該節(jié)點(diǎn)  // 返回NULL，表示沒有找到目標(biāo)節(jié)點(diǎn)  return NULL;  
}

查找指定節(jié)點(diǎn)在不在

// 參數(shù)：root 是指向二叉樹根節(jié)點(diǎn)的指針，x 是要查找的節(jié)點(diǎn)值  
// 返回值：bool 類型，如果找到指定節(jié)點(diǎn)則返回 true，否則返回 false，這個(gè)通常用于條件語句或者循環(huán)語句里，返回true時(shí)執(zhí)行，返回false時(shí)不執(zhí)行  
// 功能：在二叉樹中查找指定的節(jié)點(diǎn)值是否存在  
bool TreeFindExit(BTNode* root, int x) {  // 如果當(dāng)前節(jié)點(diǎn)為空（即已經(jīng)遍歷到葉子節(jié)點(diǎn)之后的位置），則返回 false  if (root == NULL) {  return false;  }  // 如果當(dāng)前節(jié)點(diǎn)的值等于要查找的值 x，則說明找到了指定的節(jié)點(diǎn)  // 直接返回 true  if (root->val == x) {  return true;  }  // 如果當(dāng)前節(jié)點(diǎn)的值不是要查找的值，則遞歸地在左子樹和右子樹中查找  // 使用邏輯或操作符 ||，表示如果左子樹或右子樹中任何一個(gè)找到了指定節(jié)點(diǎn)就返回 true  // 如果左右子樹都沒有找到，最終會(huì)返回 false  return TreeFindExit(root->left, x) || TreeFindExit(root->right, x);  
}

完整代碼

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>//二叉樹的定義
typedef struct BinTreeNode {struct BinTreeNode* left;struct BinTreeNode* right;int val;
}BTNode;//創(chuàng)建一棵樹并初始化
BTNode* BuyNode(int val) {BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL) {perror("malloc fail");return;//注意這里應(yīng)該是return NULL}newnode->left = NULL;newnode->right = NULL;newnode->val = val;//這里是valreturn newnode;//創(chuàng)建了就要返回
}//組裝二叉樹
BTNode* CreatNode() {BTNode* n1 = BuyNode(1);BTNode* n2 = BuyNode(2);BTNode* n3 = BuyNode(3);BTNode* n4 = BuyNode(4);BTNode* n5 = BuyNode(5);BTNode* n6 = BuyNode(6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return n1;//記得返回
}//前序遍歷
void PreOrder(BTNode* root) {if (root == NULL) {printf("N ");return;}printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);
}//中序遍歷
void InOrder(BTNode* root) {if (root == NULL) {printf("N ");return;}InOrder(root->left);printf("%d ",root->val);InOrder(root->right);
}//后序遍歷
void PostOrder(BTNode* root) {if (root == NULL) {printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ",root->val);
}//計(jì)算樹的結(jié)點(diǎn)個(gè)數(shù)
int TreeSize(BTNode* root) {return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}//求二叉樹第K層的結(jié)點(diǎn)個(gè)數(shù)
int TreeKLevel(BTNode* root,int k) {if (root == NULL) {return 0;}if (k == 1) {//k=1時(shí)不需要再往下求了return 1;}return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}
//求二叉樹高度
int TreeHigh(BTNode* root) {if (root== NULL) {return 1;}int leftHigh = TreeHigh(root->left);int rightHigh = TreeHigh(root->right);return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;
}//查找X所在的結(jié)點(diǎn)
BTNode*TreeFind(BTNode*root,int x){if (root == NULL) {return NULL;}if (root->val == x) {return root;}BTNode* ret1=TreeFind(root->left, x);if (ret1) {return ret1;}BTNode* ret2 = TreeFind(root->right, x);if (ret2) {return ret2;}return NULL;}//查找指定節(jié)點(diǎn)在不在
bool TreeFindExit(BTNode* root, int x) {if (root == NULL) {return false;}if (root->val == x) {return true;}return TreeFindExit(root->left, x) || TreeFindExit(root->right, x);
}int main() {BTNode* root = CreatNode();PreOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");int high = TreeHigh(root);printf("%d\n", high);int a= TreeKLevel(root,2);printf("%d\n", a);BTNode* b = TreeFind(root, 1);printf("%d\n", b->val);if (TreeFindExit(root, 2)) {printf("存在\n");}else {printf("不存在\n");}return 0;
}