目錄
- 前言
- 構建一顆二叉樹
- 宣告
- 實作
- 二叉樹的遍歷
- 求一顆二叉樹的結點個數
- 求二叉樹葉子結點的個數
- 求二叉樹第K層結點的個數
- 查找
- 數的層序遍歷廣度優先
- 銷毀
- 判斷完全二叉樹
- oj練習
前言
由于二叉樹是資料結構中偏難的一塊，這里我們先熟悉二叉樹的結構，再具體來實作一顆二叉樹，采用手動構建二叉樹的方式，幫助大家進一步理解
構建一顆二叉樹
呈現的是一個樹型結構
BTNode *BinaryTreeCreate(char ch)
{
BTNode *newNode = (BTNode *)malloc(sizeof(BTNode));
newNode->data = ch;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void func()
{
BTNode* A = BinaryTreeCreate('A');
BTNode* B = BinaryTreeCreate('B');
BTNode* C = BinaryTreeCreate('C');
BTNode* D = BinaryTreeCreate('D');
BTNode* E = BinaryTreeCreate('E');
BTNode* F = BinaryTreeCreate('F');
A->left = B;
A->right = C;
B->left = D;
C->left = E;
C->right = F;
}
構建了結點與結點之間的父子關系，從代碼中可以看到A的左右子樹是B和C，B的左子樹是D，C的左右子樹是E和F，剩余的默認給NULL值，在創建結點的時候就已經初始化好了，那如果想要呈現出遍歷順序呢，
宣告
#pragma once
#include<memory.h>
#include<stdbool.h>
#include<stdlib.h>
#include<stdio.h>
#include"Queue.h"
typedef char BTDataType;
typedef struct BTNode
{
struct BTNode *left;
struct BTNode *right;
BTDataType data;
}BTNode;
//創建結點
BTNode *BinaryTreeCreate(char ch);
//后序遍歷
void PrevOrder(BTNode *root);
//中序遍歷
void Inorder(BTNode *root);
//后序遍歷
void Postorder(BTNode *root);
//樹結點的個數
int BinaryTreeSize(BTNode *root);
//求葉子結點的個數
int BinaryleafSize(BTNode* root);
//求二叉樹的第k層結點個數
int BinaryKSize(BTNode* root,int k);
//查找值為val的結點
BTNode* BinaryFind(BTNode* root,char ch);
//廣度優先遍歷二叉樹
void TreeLevelorder(BTNode* root);
//二叉樹的銷毀
void BinaryTreeDestroy(BTNode* root);
//判斷一顆樹是不是完全二叉樹
bool BinaryTreecomp(BTNode* root);
實作
#include"BinaryTree.h"
BTNode *BinaryTreeCreate(char ch)
{
BTNode *newNode = (BTNode *)malloc(sizeof(BTNode));
assert(newNode);
newNode->data = ch;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
//后序遍歷
void PrevOrder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
PrevOrder(root->left);
PrevOrder(root->right);
printf("%c ",root->data);
}
}
//中序遍歷
void Inorder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
PrevOrder(root->left);
printf("%c ", root->data);
PrevOrder(root->right);
}
}
//后序遍歷
void Postorder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
printf("%c ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
}
//樹結點的個數
int BinaryTreeSize(BTNode *root)
{
return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
//求葉子結點的個數
int BinaryleafSize(BTNode *root)
{
if (root == NULL)
{
return 0;
}
else if(!root->left && !root->right)
{
return 1;
}
else
{
return BinaryleafSize(root->left) + BinaryleafSize(root->right);
}
}
//求二叉樹的第k層結點個數
int BinaryKSize(BTNode* root,int k)
{
if (!root)
{
return 0;
}
else if (k == 1)
{
return 1;
}
else
{
return BinaryKSize(root->left, k - 1)
+ BinaryKSize(root->right, k - 1);
}
}
//查找值為val的結點
BTNode* BinaryFind(BTNode* root,char ch)
{
if (!root)
{
return NULL;
}
if (root->data == ch)
{
return root;
}
BTNode* leftNode = BinaryFind(root->left,ch);
BTNode* rightNode = BinaryFind(root->right, ch);
if (leftNode != NULL)
{
return leftNode;
}
else
{
return rightNode;
}
return NULL;
}
void TreeLevelorder(BTNode* root)
{
assert(root);
Queue q;
QueueInit(&q);
QueuePush(&q,root);
while (!QueueEmpty(&q))
{
//取出隊頭的資料
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c ",front->data);
//接著入，出一層父親結點，帶進去子節點
if (front->left != NULL)
{
QueuePush(&q, front->left);
}
if (front->right != NULL)
{
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestroy(&q);
}
//二叉樹的銷毀
void BinaryTreeDestroy(BTNode* root)
{
if (!root)
{
return;
}
BinaryTreeDestroy(root->left);
BinaryTreeDestroy(root->right);
free(root);
}
//判斷一顆樹是不是完全二叉樹
bool BinaryTreecomp(BTNode* root)
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (!front)
{
break;
}
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
if (front)
{
return false;
}
}
return true;
}
二叉樹的遍歷
我們知道二叉樹有三種遍歷方式，為了遍歷前面構建出來的樹型結構這三種遍歷方式我們都采用
按照規則，二叉樹的遍歷有：前序/中序/后序的遞回結構遍歷：
- 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點的操作發生在遍歷其左右子樹之前，
- 中序遍歷(Inorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之中（間），
- 后序遍歷(Postorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之后，由于被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹，NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷，
總結：
- 前序遍歷
根 --> 左子樹 -->右子樹 - 中序遍歷
左子樹 --> 根 --> 右子樹 - 后序遍歷
左子樹 --> 右子樹 --> 根
//后序遍歷
void PrevOrder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
PrevOrder(root->left);
PrevOrder(root->right);
printf("%d ",root->data);
}
}
//中序遍歷
void Inorder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
PrevOrder(root->left);
printf("%d ", root->data);
PrevOrder(root->right);
}
}
//前序遍歷
void Postorder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
}
求一顆二叉樹的結點個數
int BinaryTreeSize(BTNode *root)
{
return root == NULL ? 0 : BinaryTreeSize(root->left)
+ BinaryTreeSize(root->right) + 1;
}
后序思想，遞回左右子樹，如果該結點為空就回傳0，不為空就回傳左右子樹的結點個數相加的和值 + 1，這里的+ 1 操作是用作計數根結點的(每一個真實結點)，其實看作是一個二叉樹的后序遍歷也不為過
求二叉樹葉子結點的個數
//求葉子結點的個數
int BinaryleafSize(BTNode *root)
{
if (root == NULL)
{
return 0;
}
else if(!root->left && !root->right)
{
return 1;
}
else
{
return BinaryleafSize(root->left)
+ BinaryleafSize(root->right);
}
}
葉子結點表示的是沒有孩子的結點，當遍歷一顆樹不斷的往下遞回，總會遇到度為0的結點，而這個結點的就是作為這顆樹的葉子結點，在這里可以將一顆大樹看成是多顆小樹，計算出多顆小樹的葉子結點個數就是整個大樹的葉子結點
求二叉樹第K層結點的個數
//求二叉樹的第k層結點個數
int BinaryKSize(BTNode* root,int k)
{
if (!root)
{
return 0;
}
else if (k == 1)
{
return 1;
}
else
{
return BinaryKSize(root->left, k - 1)
+ BinaryKSize(root->right, k - 1);
}
}
想求出第k層的結點的個數只需要將這一層的結點相加得到的結果就是這一層的結點個數
查找
BTNode* BinaryFind(BTNode* root,char ch)
{
if (!root)
{
return NULL;
}
if (root->data == ch)
{
return root;
}
BTNode* leftNode = BinaryFind(root->left,ch);
BTNode* rightNode = BinaryFind(root->right, ch);
if (leftNode != NULL)
{
return leftNode;
}
else
{
return rightNode;
}
return NULL;
}
到樹的左右子樹中去查找該結點如果找到就回傳該節點，否則繼續查找，直到走到NULL的位置，那就回傳NULL
數的層序遍歷廣度優先
英文縮寫為BFS即Breadth FirstSearch，其程序檢驗來說是對每一層節點依次訪問，訪問完一層進入下一層，而且每個節點只能訪問一次，這里用佇列來實作這個遍歷方式，還是由于佇列先進先出的特性，
實作思路：
先將根入佇列，將父親pop出去后再入孩子，列印父親的值，那么這一層就已經遍歷完了，緊接著就可以繼續入下一層，父親每次pop出去的時讓父親的孩子入隊，
void TreeLevelorder(BTNode* root)
{
assert(root);
Queue q;
QueueInit(&q);
QueuePush(&q,root);
while (!QueueEmpty(&q))
{
//取出隊頭的資料
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c ",front->data);
//接著入，出一層父親結點，帶進去子節點
if (front->left != NULL)
{
QueuePush(&q, front->left);
}
if (front->right != NULL)
{
QueuePush(&q, front->right);
}
}
QueueDestroy(&q);
}
銷毀
實作思路：后序遍歷，從最后一個NULL位置開始邊回退，回傳它的上一層，釋放這個結點
//二叉樹的銷毀
void BinaryTreeDestroy(BTNode* root)
{
if (!root)
{
return;
}
BinaryTreeDestroy(root->left);
BinaryTreeDestroy(root->right);
free(root);
}
判斷完全二叉樹
首先我們得有完全二叉樹的概念，完全二叉樹的最后一層結點個數可以不滿，但是必須是從左到右連續的，那么看上面的圖，你覺得他會是完全二叉樹嗎，左邊是，右邊不是，原因不是連續的，如果接著采用層序遍歷的思路搞定這個，還是比較簡單的，
//判斷一顆樹是不是完全二叉樹
bool BinaryTreecomp(BTNode* root)
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (!front)
{
break;
}
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
//檢查佇列中是否還有剩余，如果有表示從左到右并不是連續的
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
if (front)
{
return false;
}
}
return true;
}
oj練習
- 單值二叉樹
鏈接: link.
題目描述：
如果二叉樹每個節點都具有相同的值，那么該二叉樹就是單值二叉樹，只有給定的樹是單值二叉樹時，才回傳 true；否則回傳 false
實作思路：
如果左孩子跟右孩子的值都與父親的值相等，那么他就是單值二叉樹，再往下遞回的程序中只需要將值不等就直接回傳false，否則就繼續遞回下去直到整個樹遍歷完了，那么就是單值二叉樹
bool isUnivalTree(struct TreeNode* root){
if(!root)
{
return true;
}
//判斷左孩子跟父親是否相等，不等回傳false
if(root->left && root->left->val != root->val)
{
return false;
}
//判斷右孩子是否和父親相等，不等回傳false
else if(root->right && root->right->val != root->val)
{
return false;
}
//相等繼續往下遞回，
else
{
return isUnivalTree(root->left)
&& isUnivalTree(root->right);
}
}
- 二叉樹的前序遍歷
鏈接: link.
原題描述：
給你二叉樹的根節點 root ，回傳它節點值的 前序 遍歷，
實作介面
int* preorderTraversal(struct TreeNode* root,
int* returnSize)
{
}
實作思路：
前序遍歷這顆二叉樹，將二叉樹每個結點的值存放進陣列中，最后回傳該陣列，值得注意的是這個介面的引數，*returnsize，到底需要開辟多大的空間來存放二叉樹的值，可以通過遍歷二叉樹求出它的結點個數，malloc出等大的陣列出來，存放結點的值
//計算結點的個數
int TreeSize(struct TreeNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//以前序遍歷的方式，將樹的值存放到陣列中
void _preoder(struct TreeNode* root,int *retArr, int *pi)
{
if(!root)
{
return;
}
else
{
retArr[(*pi)++] = root->val;
_preoder(root->left,retArr,pi);
_preoder(root->right,retArr,pi);
}
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize = TreeSize(root);
int *retArr = (int *)malloc(sizeof(int) * (* returnSize));
int i = 0;
_preoder(root,retArr,&i);
return retArr;
}
- 相同的樹
鏈接: link.
題目描述：
給你兩棵二叉樹的根節點 p 和 q ，撰寫一個函式來檢驗這兩棵樹是否相同，如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的，
實作思路：
能先想到的就是這兩顆樹都是空樹，那么他們就是相同的，還有一種情況就是一個樹的結點多，一個樹的結點少，少的先被遍歷完，所以他們肯定不相同，剩下的就是判斷值了，比較兩顆樹的左右子樹的值是否是相等的
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p == NULL && q == NULL)
{
return true;
}
if(p == NULL || q == NULL)
{
return false;
}
else if(p->val != q->val)
{
return false;
}
else
{
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
}
- 對稱二叉樹
鏈接: link.
題目描述：
給定一個二叉樹，檢查它是否是鏡像對稱的，
實作思路：
從樹的第二層開始，將每一層的根劃分出兩顆左右子樹,比較根再分別將兩顆子樹的左孩子和右孩子比較，右孩子和左孩子比較，如果相同就回傳true
bool _issymmetry(struct TreeNode *Treeleft, struct TreeNode* Treeright)
{
if(!Treeleft && !Treeright)
{
return true;
}
if(!Treeleft || !Treeright)
{
return false;
}
else if(Treeleft->val != Treeright->val)
{
return false;
}
return _issymmetry(Treeleft->left,Treeright->right)
&& _issymmetry(Treeleft->right,Treeright->left) ;
}
bool isSymmetric(struct TreeNode* root){
if(!root)
{
return true;
}
return _issymmetry(root->left,root->right);
}
- 翻轉二叉樹
鏈接: link.
題目描述：
翻轉一棵二叉樹，
實作思路：
遞回到最后一層開始再往回返的程序，備份根的左右孩子，回退到根的時候交換左右孩子的位置
struct TreeNode* invertTree(struct TreeNode* root){
if(!root)
return NULL;
struct TreeNode* left = invertTree(root->left);
struct TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
- 另一棵樹的子樹
鏈接: link.
給你兩棵二叉樹 root 和 subRoot ，檢驗 root 中是否包含和 subRoot 具有相同結構和節點值的子樹，如果存在，回傳 true ；否則，回傳 false，
二叉樹 tree 的一棵子樹包括 tree 的某個節點和這個節點的所有后代節點，tree 也可以看做它自身的一棵子樹，
實作思路：
從root中選出每一個根看作一顆子樹去和subroot這顆子樹比較，如果他們，左右子樹都相等了就回傳true，如果不相等繼續從root中找下一個根
bool _issymmetry(struct TreeNode *root,
struct TreeNode* subRoot)
{
if(!root && !subRoot)
return true;
if(!root || !subRoot)
return false;
else if(root->val != subRoot->val)
return false;
return _issymmetry(root->left,subRoot->left)
&& _issymmetry(root->right,subRoot->right);
}
bool isSubtree(struct TreeNode* root,
struct TreeNode* subRoot){
if(!root)
return false;
if(_issymmetry(root,subRoot))
return true;
//尋找下一個根比較是否與subRoot相等
return isSubtree(root->left,subRoot)
|| isSubtree(root->right,subRoot);
}
- 平衡二叉樹
鏈接: link.
給定一個二叉樹，判斷它是否是高度平衡的二叉樹，
題目描述：
本題中，一棵高度平衡二叉樹定義為：一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 ，
實作思路：
大問題化成小問題的思路，要想判斷是不是平衡二叉樹，就得把整個樹拆分成多顆子樹，去判斷左右子樹的高度差是否 < 2,分別求出n顆左右子樹的深度，如果他們的差距 < 2 就滿足，直到把整個樹遍歷完就回傳true，這里采用的遍歷方式是后序遍歷
bool isbalance(struct TreeNode* root, int *pi)
{
if(!root)
{
*pi = 0;
return true;
}
int leftheight = 0;
if(isbalance(root->left,&leftheight) == false)
return false;
int rightheight = 0;
if(isbalance(root->right,&rightheight) == false)
return false;
*pi = fmax(leftheight,rightheight) + 1;
return abs(leftheight - rightheight) < 2;
}
bool isBalanced(struct TreeNode* root){
if(!root)
return true;
int i = 0;
return isbalance(root,&i);
}
KY11 二叉樹遍歷
鏈接: link.
原題描述：
編一個程式，讀入用戶輸入的一串先序遍歷字串，根據此字串建立一個二叉樹（以指標方式存盤）， 例如如下的先序遍歷字串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空樹，建立起此二叉樹以后，再對二叉樹進行中序遍歷，輸出遍歷結果，
根據題意手動還原出來的二叉樹應該是這樣的，滿足先序遍歷的結構
實作思路：
把字串存放進一個陣列中，每次遍歷這個陣列，取出一個字符創建結點，從上往下遞回，不斷創建左右孩子，當遇到#的時候就表示這個結點是葉子，那就回傳它的上一層，它的上一層就是根，把葉子當作根的孩子，往上回傳，不斷創建父子關系，當左子樹遞回完了就去遞回右子樹，直到整個樹創建出來，
#include<stdio.h>
typedef char BTNodeType;
typedef struct BTNode
{
struct BTNode *left;
struct BTNode *right;
BTNodeType data;
}BTNode;
BTNode *BTNodecreate(char *str,int *pi)
{
if(str[*pi] == '#')
{
(*pi)++;
return NULL;
}
//取字符創建結點
BTNode* root = (BTNode *)malloc(sizeof(BTNode));
root->data = str[(*pi)++];
//創建左右孩子
root->left = BTNodecreate(str, pi);
root->right = BTNodecreate(str, pi);
return root;
}
//中序遍歷
void inorder(BTNode *root)
{
if(!root)
{
return ;
}
inorder(root->left);
printf("%c ",root->data);
inorder(root->right);
}
int main()
{
int i = 0;
char arr[100] = {0};
scanf("%s",arr);
BTNode *root = BTNodecreate(arr,&i);
inorder(root);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/330377.html
標籤：其他
上一篇：程式員相親 滿屏尷尬