?🔥個人主頁:@草莓熊Lotso
🎬作者簡介:C++研發方向學習者
📖個人專欄:?《C語言》?《數據結構與算法》《C語言刷題集》《Leetcode刷題指南》
??人生格言:生活是默默的堅持,毅力是永久的享受。??
前言: 通過前面幾篇博客我們已經完成了前中后序的接口實現,我們現在開始需要進行其它二叉樹常用方法的實現,比如二叉樹節點個數,葉子節點個數等。還是和之前一樣分部分實現,最后再展示全部的代碼。
目錄
一.求二叉樹節點個數
代碼實現:?
test.c:?
二.求二叉樹葉子節點個數
代碼實現:
test.c:?
?三.求二叉樹第k層節點個數
代碼實現:?
test.c:?
?四.求二叉樹的深度/高度
?代碼實現:
test.c:?
?五.二叉樹查找值為x的節點
代碼實現:
test.c:
?六.二叉樹的銷毀?
代碼實現:
?七.代碼展現
Tree.h:
Tree.c:
test.c:
一.求二叉樹節點個數
--我們先來實現一個求二叉樹的節點個數的接口,在正式開始之前我們先把上次寫的代碼里的test.c中創建樹的代碼優化一下,這樣方便后續操作
#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍歷//PreOrder(root);//InOrder(root);//PostOrder(root);
}int main()
{test1();return 0;
}
--優化完之后,我們就可以開始實現求二叉樹節點個數的接口了?
- ?二叉樹結點個數=根節點+左子樹結點個數+右子樹結點個數
代碼實現:?
// 二叉樹結點個數=根節點+左子樹節點個數+右子樹節點個數
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
圖示如下:
test.c:?
#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍歷//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉樹結點個數printf("Size: %d\n", BinaryTreeSize(root));
}int main()
{test1();return 0;
}
--測試完成,打印出來沒有問題,退出碼為0?
二.求二叉樹葉子節點個數
--二叉樹的葉子節點就是左右孩子都為空的節點
- 二叉樹葉子節點個數=左子樹葉子節點個數+右子樹葉子節點個數
代碼實現:
// 二叉樹葉子結點個數=左子樹葉子節點個數+右子樹節點個數
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}//判斷是否為葉子節點(沒有左右孩子)if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
圖示如下:?
test.c:?
#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍歷//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉樹結點個數printf("Size: %d\n", BinaryTreeSize(root));//二叉樹葉子結點個數printf("LeafSize: %d\n", BinaryTreeLeafSize(root));
}int main()
{test1();return 0;
}
--測試完成,打印沒有問題,退出碼為0
?三.求二叉樹第k層節點個數
--當k==1時當前節點就是第k層節點
- 二叉樹第k層節點個數=左子樹第k-1層節點個數+右子樹第k-1層節點個數
代碼實現:?
// 二叉樹第k層節點個數=左子樹第K-1層節點個數+右子樹第k-1層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}//判斷是否為第k層if (k == 1){return 1;}//每次注意要k-1return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
圖示如下:?
test.c:?
#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍歷//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉樹結點個數printf("Size: %d\n", BinaryTreeSize(root));//二叉樹葉子結點個數printf("LeafSize: %d\n", BinaryTreeLeafSize(root));//第k層節點個數printf("K Size: %d\n", BinaryTreeLevelKSize(root,3));
}int main()
{test1();return 0;
}
--測試完成,打印沒有問題,退出碼為0
?四.求二叉樹的深度/高度
- 二叉樹的高度=根節點+max(左子樹的高度,右子樹的高度)
?代碼實現:
//二叉樹的深度/高度=根節點+max(左子樹高度,右子樹高度)
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftdepth = BinaryTreeDepth(root->left);int rightdepth = BinaryTreeDepth(root->right);return 1 + (leftdepth > rightdepth ? leftdepth : rightdepth);
}
圖示如下:
test.c:?
#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍歷//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉樹結點個數printf("Size: %d\n", BinaryTreeSize(root));//二叉樹葉子結點個數printf("LeafSize: %d\n", BinaryTreeLeafSize(root));//第k層節點個數printf("K Size: %d\n", BinaryTreeLevelKSize(root,3));//二叉樹的深度/高度printf("Depth: %d\n", BinaryTreeDepth(root));
}int main()
{test1();return 0;
}
--測試完成,打印沒有問題,退出碼為0
?五.二叉樹查找值為x的節點
--遞歸查找,找到了就返回當前節點,如果是在左子樹中找到就直接返回,沒找到繼續來到右子樹找,最好都沒找到就返回NULL
代碼實現:
// 二叉樹查找值為x的結點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode*leftroot = BinaryTreeFind(root->left, x);//如果leftroot不為空就是找到了直接返回if (leftroot){return leftroot;}//沒找到就繼續右子樹找BTNode* rightroot = BinaryTreeFind(root->right, x);if (rightroot){return rightroot;}//都沒找到就返回空return NULL;
}
圖示如下:?
test.c:
#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍歷//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉樹結點個數printf("Size: %d\n", BinaryTreeSize(root));//二叉樹葉子結點個數printf("LeafSize: %d\n", BinaryTreeLeafSize(root));//第k層節點個數printf("K Size: %d\n", BinaryTreeLevelKSize(root,3));//二叉樹的深度/高度printf("Depth: %d\n", BinaryTreeDepth(root));//二叉樹查找值為x的結點BTNode* pos = BinaryTreeFind(root, 'E');if (pos){printf("找到了\n");}else {printf("沒找到\n");}
}int main()
{test1();return 0;
}
--測試完成,找的到E,退出碼為0
?六.二叉樹的銷毀?
--由于提前釋放根節點無法找到其左右節點,所以我們得采用后續遍歷的思想,最后處理根節點,
還有這里得傳地址,后續的使用也需要注意一下寫法。
代碼實現:
// 二叉樹銷毀--采用后序遍歷的思想
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&(*root)->left);BinaryTreeDestory(&(*root)->right);free(*root);*root = NULL;
}
圖示如下:
?七.代碼展現
Tree.h:
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef char BTDataType;
typedef struct BinaryNode
{BTDataType data;struct BinaryNode* left;//左孩子struct BinaryNode* right;//右孩子
}BTNode;//前序遍歷
void PreOrder(BTNode* root);//中序遍歷
void InOrder(BTNode* root);//后序遍歷
void PostOrder(BTNode* root);// 二叉樹結點個數
int BinaryTreeSize(BTNode* root);// 二叉樹葉子結點個數
int BinaryTreeLeafSize(BTNode* root);// 二叉樹第k層結點個數
int BinaryTreeLevelKSize(BTNode* root, int k);//二叉樹的深度/高度
int BinaryTreeDepth(BTNode* root);// 二叉樹查找值為x的結點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root);
Tree.c:
#include"Tree.h"//前序遍歷
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//根左右printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍歷
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//左根右InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}//后序遍歷
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//左右根PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}// 二叉樹結點個數=根節點+左子樹節點個數+右子樹節點個數
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}// 二叉樹葉子結點個數=左子樹葉子節點個數+右子樹節點個數
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}//判斷是否為葉子節點(沒有左右孩子)if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}// 二叉樹第k層節點個數=左子樹第K-1層節點個數+右子樹第k-1層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}//判斷是否為第k層if (k == 1){return 1;}//每次注意要k-1return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}//二叉樹的深度/高度=根節點+max(左子樹高度,右子樹高度)
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftdepth = BinaryTreeDepth(root->left);int rightdepth = BinaryTreeDepth(root->right);return 1 + (leftdepth > rightdepth ? leftdepth : rightdepth);
}// 二叉樹查找值為x的結點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode*leftroot = BinaryTreeFind(root->left, x);//如果leftroot不為空就是找到了直接返回if (leftroot){return leftroot;}//沒找到就繼續右子樹找BTNode* rightroot = BinaryTreeFind(root->right, x);if (rightroot){return rightroot;}//都沒找到就返回空return NULL;
}// 二叉樹銷毀--采用后序遍歷的思想
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&(*root)->left);BinaryTreeDestory(&(*root)->right);free(*root);*root = NULL;
}
test.c:
#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}void test1()
{BTNode* root = CreateTree();//前中后序遍歷//PreOrder(root);//InOrder(root);//PostOrder(root);//二叉樹結點個數printf("Size: %d\n", BinaryTreeSize(root));//二叉樹葉子結點個數printf("LeafSize: %d\n", BinaryTreeLeafSize(root));//第k層節點個數printf("K Size: %d\n", BinaryTreeLevelKSize(root,3));//二叉樹的深度/高度printf("Depth: %d\n", BinaryTreeDepth(root));//二叉樹查找值為x的結點BTNode* pos = BinaryTreeFind(root, 'E');if (pos){printf("找到了\n");}else {printf("沒找到\n");}// 二叉樹銷毀BinaryTreeDestory(&root);
}int main()
{test1();return 0;
}
往期回顧:
【數據結構初階】--樹和二叉樹先導篇
【數據結構初階】--二叉樹(二)
【數據結構初階】--二叉樹(三)
【數據結構初階】--二叉樹(四)
結語:在這篇博客中我們一起實現了二叉樹的大部分常用接口,后面還有一個判斷是否為完全二叉樹和一個層序遍歷的實現。如果文章對你有幫助的話,歡迎評論,點贊,收藏加關注,感謝大家的支持。