數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)
前言：
前篇學(xué)習(xí)了 數(shù)據(jù)結(jié)構(gòu)之樹(shù)和二叉樹(shù)的基本概念知識(shí)，那么這篇繼續(xù)完善二叉樹(shù)的相關(guān)知識(shí)并完成實(shí)現(xiàn)二叉樹(shù)的構(gòu)建和遍歷的內(nèi)容。
/知識(shí)點(diǎn)匯總/
1、二叉樹(shù)的概念和結(jié)構(gòu)
因?yàn)榍捌呀?jīng)非常詳細(xì)的單獨(dú)學(xué)習(xí)了數(shù)和二叉樹(shù)的基本知識(shí)概念，那么這里就簡(jiǎn)單回顧一下即可。
概念：
二叉樹(shù)（Binary Tree）是樹(shù)形結(jié)構(gòu)的一個(gè)重要類型。每個(gè)節(jié)點(diǎn)最多只能有兩棵子樹(shù)，且有左右之分。
它的定義可以概括為：一個(gè)n個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根的元素及兩個(gè)不相交的、被分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。
形象一點(diǎn)就是：
(1)空二叉樹(shù)——(a)；
(2)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)——(b)；
(3)只有左子樹(shù)——?；
(4)只有右子樹(shù)——(d)；
(5)完全二叉樹(shù)——(e)
1.1、回顧二叉樹(shù)的重要性質(zhì)
1.二叉樹(shù)第i層上的結(jié)點(diǎn)數(shù)目最多為2^(i-1) (i≥1)。
2.深度為k的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn)(k≥1)。
3.包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度至少為log2(n+1)。
4.在任意一棵二叉樹(shù)中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。
5.如果有一顆n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（其深度為?log2n?+1）的結(jié)點(diǎn)按層序編號(hào)（從第一層到最后一層，每層從左到右），對(duì)任一結(jié)點(diǎn)i（1≤i≤n）：
1)如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>1，則其雙親是結(jié)點(diǎn)?i/2?。
2)如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左孩子LCHILD(i)是結(jié)點(diǎn)2i。
3)如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子，否則其右孩子RCHILD(i)是結(jié)點(diǎn)2i+1。
1.2、回顧二叉樹(shù)的主要分類
1.滿二叉樹(shù)：如果一棵二叉樹(shù)只有度為0的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)，并且度為0的結(jié)點(diǎn)在同一層上，那么這棵二叉樹(shù)就被稱為滿二叉樹(shù)。
2.完全二叉樹(shù)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)，因此不存在度大于2的結(jié)點(diǎn)。左子樹(shù)和右子樹(shù)是有順序的，次序不能任意顛倒。
3.二叉搜索樹(shù)（二叉排序樹(shù)）：可以為空樹(shù)，或者是具備如下性質(zhì)：若它的左子樹(shù)不空，則左子樹(shù)上的所有結(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值；若它的右子樹(shù)不空，則右子樹(shù)上的所有結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值，左右子樹(shù)分別為二叉排序樹(shù)。
4.平衡二叉樹(shù)：這是一種概念，是二叉查找樹(shù)的一個(gè)進(jìn)化體，它有幾種實(shí)現(xiàn)方式：紅黑樹(shù)、AVL樹(shù)。平衡二叉樹(shù)的特點(diǎn)是任意節(jié)點(diǎn)的子樹(shù)的高度差都小于等于1。
1.1、如何實(shí)現(xiàn)二叉樹(shù)？
二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)分類
1.二叉樹(shù)的數(shù)組存儲(chǔ)結(jié)構(gòu)：
一般使用數(shù)組只適合表示完全二叉樹(shù)，因?yàn)椴皇峭耆鏄?shù)會(huì)有空間的浪費(fèi)等問(wèn)題。
并且實(shí)際應(yīng)用中，也只有堆會(huì)用數(shù)組的形式存儲(chǔ)。因?yàn)槎褲M足完全二叉樹(shù)。
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
2、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：
常用鏈表來(lái)指示元素的邏輯關(guān)系。
通常，以鏈表中的每一個(gè)結(jié)點(diǎn)，三個(gè)域組成，分別是數(shù)據(jù)域、左指針域和右指針域，左指針指向左孩子，右指針指向右孩子。
鏈?zhǔn)浇Y(jié)構(gòu)也分為二叉鏈和三叉鏈，一般是二叉鏈。高階數(shù)據(jù)結(jié)構(gòu)涉及三叉鏈。
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}TreeNode;
2、二叉樹(shù)的實(shí)現(xiàn)
2.1、二叉樹(shù)的BinaryTree.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType Val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// 通過(guò)前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹(shù)
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉樹(shù)銷(xiāo)毀
void BinaryTreeDestory(BTNode** root);
// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root);
// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹(shù)的高度/深度
int BinaryTreeHeight(BTNode* root);
// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹(shù)查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉樹(shù)前序遍歷
void BinaryTreePrevOrder(BTNode* root);
// 二叉樹(shù)中序遍歷
void BinaryTreeInOrder(BTNode* root);
// 二叉樹(shù)后序遍歷
void BinaryTreePostOrder(BTNode* root);
//創(chuàng)建隊(duì)列結(jié)構(gòu)體成員與變量
typedef struct BinaryTreeNode* QDatetype;//注意這里的返回類型和參數(shù)與二叉樹(shù)的接口類型要對(duì)應(yīng)
typedef struct QueueNode
{
QDatetype val;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//隊(duì)列初始化
void QueueInit(Queue* pq);
//隊(duì)列銷(xiāo)毀
void QueueDestory(Queue* pq);
//元素入隊(duì)
void QueuePush(Queue* pq, QDatetype x);
//元素出隊(duì)
void QueuePop(Queue* pq);
//獲取隊(duì)頭元素
QDatetype QueueFront(Queue* pq);
//獲取隊(duì)尾元素
QDatetype QueueBack(Queue* pq);
//獲取隊(duì)列元素個(gè)數(shù)或隊(duì)列大小
int QueueSize(Queue* pq);
//隊(duì)列判斷空
bool QueueEmpty(Queue* pq);
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root);
// 判斷二叉樹(shù)是否是完全二叉樹(shù)
bool BinaryTreeComplete(BTNode* root);
//寫(xiě)法2：
//int BinaryTreeComplete2(BTNode* root);
2.2、二叉樹(shù)的BinaryTree.c
2.2.1、二叉樹(shù)的構(gòu)建
// 通過(guò)前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹(shù)
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
assert(a);
if (a[*pi] == '#' || *pi >= n)
{
++(*pi);
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (root == NULL)
{
perror("malloc fail");
exit(-1);
}
root->Val = a[*pi];
++(*pi);
root->left = BinaryTreeCreate(a, n, pi);
root->right = BinaryTreeCreate(a, n, pi);
return root;
}
2.2.2、二叉樹(shù)銷(xiāo)毀
// 二叉樹(shù)銷(xiāo)毀
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)
{
return;
}
BinaryTreeDestory(&(*root)->left);
BinaryTreeDestory(&(*root)->right);
free(*root);
*root = NULL;
}
2.2.3、二叉樹(shù)前序、中序、后序遍歷操作
// 二叉樹(shù)前序遍歷
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
//printf("# ");
return;
}
printf("%c ", root->Val);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
// 二叉樹(shù)中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
//printf("# ");
return;
}
BinaryTreeInOrder(root->left);
printf("%c ", root->Val);
BinaryTreeInOrder(root->right);
}
// 二叉樹(shù)后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
//printf("# ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->Val);
}
2.2.4、二叉樹(shù)取結(jié)點(diǎn)個(gè)數(shù)操作
// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root)
{
return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
2.2.5、二叉樹(shù)取葉子結(jié)點(diǎn)個(gè)數(shù)操作
// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
//為空返回0，不能assert,否則遞歸走不動(dòng)
if (root == NULL)
{
return 0;
}
//只有根節(jié)點(diǎn)或葉子節(jié)點(diǎn)，則返回1
if (root->left == NULL && root->right == NULL)
{
return 1;
}
//其余情況的葉子節(jié)點(diǎn)=左子樹(shù)葉子節(jié)點(diǎn)+右子樹(shù)葉子節(jié)點(diǎn)
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
2.2.6、取二叉樹(shù)的高度/深度操作
int BinaryTreeHeight(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return fmax(BinaryTreeHeight(root->left), BinaryTreeHeight(root->right)) + 1;
}
2.2.7、二叉樹(shù)取第k層結(jié)點(diǎn)個(gè)數(shù)操作
// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
assert(k > 0);
//為空
if (root == NULL)
return 0;
//根節(jié)點(diǎn)
if (k == 1)
return 1;
//其余層，遞歸k-1
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
2.2.8、二叉樹(shù)取查找值為x的節(jié)點(diǎn)操作
// 二叉樹(shù)查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
//參數(shù)為空
if (root == NULL)
{
return NULL;
}
//根節(jié)點(diǎn)匹配，則返回空節(jié)點(diǎn)
if (root->Val == x)
{
return root;
}
//遍歷左右子樹(shù)，找匹配值
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1)
{
return ret1;
}
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
{
return ret2;
}
//遍歷結(jié)束都沒(méi)有匹配，則返回空
return NULL;
}
2.2.9、二叉樹(shù)層序遍歷操作
//隊(duì)列初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
//隊(duì)列銷(xiāo)毀
void QueueDestory(Queue* pq)
{
assert(pq);
//工作指針，遍歷銷(xiāo)毀
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
//元素入隊(duì)
void QueuePush(Queue* pq, QDatetype x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->next = NULL;
newnode->val = x;
//空隊(duì)列的處理
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
//尾指針后移
pq->ptail = newnode;
}
pq->size++;
}
//元素出隊(duì)
void QueuePop(Queue* pq)
{
assert(pq);
//判空，空隊(duì)列不能出隊(duì)
assert(pq->phead);
//兼容只有一個(gè)節(jié)點(diǎn)的情況
//delfront保存當(dāng)前頭指針地址，以便free掉，并防止內(nèi)存泄漏
QNode* delfront = pq->phead;
//首元素出隊(duì),頭指針直接后移即可
pq->phead = pq->phead->next;
free(delfront);
delfront = NULL;
//只有一個(gè)節(jié)點(diǎn)時(shí)，出隊(duì)后，為空，那么尾指針也得置空
if (pq->phead == NULL)
{
pq->ptail = NULL;
}
pq->size--;
}
//獲取隊(duì)頭元素
QDatetype QueueFront(Queue* pq)
{
assert(pq);
//判空，為空沒(méi)有元素取
assert(pq->phead);
return pq->phead->val;
}
//獲取隊(duì)尾元素
QDatetype QueueBack(Queue* pq)
{
assert(pq);
//判空，為空沒(méi)有元素取
assert(pq->phead);
return pq->ptail->val;
}
//獲取隊(duì)列元素個(gè)數(shù)或隊(duì)列大小
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
//隊(duì)列判斷空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
assert(root);
//創(chuàng)建隊(duì)列
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
printf("%c ", front->Val);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
QueuePop(&q);
}
printf("\n");
QueueDestory(&q);
}
2.2.10、二叉樹(shù)判斷是否為完全二叉樹(shù)操作
判斷完全二叉樹(shù)的思路1;
1.如果樹(shù)為空，直接返回錯(cuò)誤；
2.如果樹(shù)非空，層序遍歷二叉樹(shù)；
3.如果一個(gè)結(jié)點(diǎn)左右孩子均Not NULL時(shí)，則pop該結(jié)點(diǎn)，將其左右孩子入隊(duì)列；
4.如果遇到一個(gè)結(jié)點(diǎn)，左孩子為空，而右孩子非空，則一定不為完全二叉樹(shù)；
5.如果遇到一個(gè)結(jié)點(diǎn)，左孩子不為空，而右孩子為空；或者是左右孩子均為空，則結(jié)點(diǎn)之后的隊(duì)列的結(jié)點(diǎn)都為葉子結(jié)點(diǎn)；
滿足以上條件則為完全二叉樹(shù)，否則不是完全二叉樹(shù)。
核心思想：類似于層序一層層的節(jié)點(diǎn)構(gòu)造而成，即最后一層的節(jié)點(diǎn)上面的層節(jié)點(diǎn)都是滿的。前提是最后一層不是根節(jié)點(diǎn)，即第一層.
所以遍歷不連續(xù)就不是完全二叉樹(shù)，并且隊(duì)列比棧適用于判斷的重要原因之一就是，第一個(gè)NULL出隊(duì)列時(shí)，所有的非空節(jié)點(diǎn)一定會(huì)進(jìn)隊(duì)列。
// 判斷二叉樹(shù)是否是完全二叉樹(shù)
bool BinaryTreeComplete(BTNode* root)
{
assert(root);
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//遇見(jiàn)空就結(jié)束
if (front == NULL)
{
break;
}
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
//因?yàn)槌龅娇眨顺鲅h(huán)后，再寫(xiě)一個(gè)循環(huán)判斷隊(duì)列里是否還有非空
//若有非空，則false,若沒(méi)有非空或不進(jìn)入循環(huán)，則true
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//遇見(jiàn)空就結(jié)束
if (front)
{
QueueDestory(&q);
return false;
}
}
QueueDestory(&q);
return true;
}
2.2.11、二叉樹(shù)的判空
//二叉樹(shù)判空
bool BinaryTreeEmpty(BTNode* root)
{
return root == NULL;
}
2.3、二叉樹(shù)的main.c
#include "BinaryTree.h"
int main()
{
char str[] = "ABC##DE#G##F###";// ABC##DE#G##F###
//char str2[] = "ABCDEGF";
int len = strlen(str);
int NodeNum = 0;
BTNode* tree = BinaryTreeCreate(str, len, &NodeNum);
printf("前序遍歷：");
// 二叉樹(shù)前序遍歷
BinaryTreePrevOrder(tree);
printf("\n");
printf("中序遍歷：");
// 二叉樹(shù)中序遍歷
BinaryTreeInOrder(tree);
printf("\n");
printf("后序遍歷：");
// 二叉樹(shù)后序遍歷
BinaryTreePostOrder(tree);
printf("\n");
// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)
printf("節(jié)點(diǎn)個(gè)數(shù)：%d\n", BinaryTreeSize(tree));
printf("層序遍歷：");
// 層序遍歷
BinaryTreeLevelOrder(tree);
printf("\n");
//二叉樹(shù)判空
if (BinaryTreeEmpty(tree))
{
printf("空樹(shù)\n");
}
else
{
printf("非空樹(shù)\n");
}
// 判斷二叉樹(shù)是否是完全二叉樹(shù)
if (BinaryTreeComplete(tree))
{
printf("是完全二叉樹(shù)\n");
}
else
{
printf("非完全二叉樹(shù)\n");
}
// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)
printf("葉子節(jié)點(diǎn)：%d\n", BinaryTreeLeafSize(tree));
//計(jì)算二叉樹(shù)的高度
printf("二叉樹(shù)的高度：%d\n", BinaryTreeHeight(tree));
// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)
printf("第k層葉子節(jié)點(diǎn)：%d\n", BinaryTreeLevelKSize(tree, 3));
// 二叉樹(shù)查找值為x的節(jié)點(diǎn)
printf("第k層葉子節(jié)點(diǎn)：%c\n", BinaryTreeFind(tree, 'E')->Val);
// 二叉樹(shù)銷(xiāo)毀
BinaryTreeDestory(&tree);
return 0;
}
運(yùn)行結(jié)果，如圖所示：
3、二叉樹(shù)OJ鞏固練習(xí)
3.1、練習(xí)題1：二叉樹(shù)的深度
核心思想就是取左右子樹(shù)葉子節(jié)點(diǎn)的高度，將比較大的值+根節(jié)點(diǎn)的第一層即可。因?yàn)橛?jì)算是以0計(jì)算所以需要把第一層加回來(lái)。或者+1也可以理解為（考慮只有根節(jié)點(diǎn)），加自己本身這層，就像數(shù)數(shù)需要加上自己。
方法1：fmax調(diào)用庫(kù)函數(shù)更方便，fmax用于比較出較大值并返回較大值。頭文件：<math.h>
方法2：通過(guò)變量保存，遞歸的值，最后比較大小之后加回第一層。
//方法1：fmax函數(shù)
/**/
int calculateDepth(struct TreeNode* root)
{
if (root == NULL)
{
return 0;
}
return fmax(calculateDepth(root->left), calculateDepth(root->right)) + 1;
}
//方法2：保存變量
/**/
int calculateDepth(struct TreeNode* root)
{
if (root == NULL)
{
return 0;
}
int left = calculateDepth(root->left);
int right = calculateDepth(root->right);
return left > right ? left + 1 : right + 1;
}
3.2、練習(xí)題2：?jiǎn)沃刀鏄?shù)
單值二叉樹(shù)(每個(gè)節(jié)點(diǎn)都具有相同的值) — 給定的二叉樹(shù)是單值二叉樹(shù)就返回true,否則就返回false
思路：排除法和分治法，檢查每個(gè)節(jié)點(diǎn)和他的孩子的值是否匹配。
bool isUnivaTree(struct TreeNode* root)
{
if (root == NULL)
{
return true;
}
//排除法，排除左孩子值與其父節(jié)點(diǎn)值不等
if (root->left && root->lefd->val != root->val)
{
return false;
}
//排除法，排除右孩子值與其父節(jié)點(diǎn)值不等
if (root->right && root->right->val != root->val)
{
return false;
}
//執(zhí)行遞歸，返回結(jié)果，若是不滿足上述排除的情況，說(shuō)明滿足單值二叉樹(shù)
return isUnivaTree(root->left) && isUnivaTree(root->right);
}
3.3、練習(xí)題3：相同的樹(shù)
相同的樹(shù) — 給你兩棵二叉樹(shù)的根節(jié)點(diǎn)p和q，編寫(xiě)一個(gè)函數(shù)來(lái)檢驗(yàn)這兩棵樹(shù)是否相同（如果這兩棵樹(shù)的結(jié)構(gòu)和節(jié)點(diǎn)值相同，則認(rèn)為是相同的）
思路：排除法和分治法，自己比，左子樹(shù)比，右子樹(shù)比
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
//都為空
if (p == NULL && q == NULL)
return true;
//其中一個(gè)為空
if (p == NULL || q == NULL)
return false;
//都不為空且不相等
if (p->val != q->val)
return false;
//遞歸遍歷完，都不滿足上述排除的情況，則滿足相同的樹(shù)。
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
3.4、練習(xí)題4：二叉樹(shù)的前序遍歷 存入數(shù)組
這道題的關(guān)鍵在于獲取結(jié)點(diǎn)個(gè)數(shù)開(kāi)辟數(shù)組，并涉及前序遍歷的參數(shù)設(shè)計(jì)細(xì)節(jié)問(wèn)題。
方法1：遞歸法
方法2：全局變量法（不推薦）
方法3：指針?lè)?/p>
int TreeSize(struct TreeNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void preorder(struct TreeNode* root, int* a, int i)
{
if (root == NULL)
return;
a[i++] = root->val;
preorder(root->left,a,i);
preorder(root->right,a,i);
}
//全局變量法
//int i = 0;
//void preorder(struct TreeNode* root, int* a)
//{
// if (root == NULL)
// return;
// a[i++] = root->val;
// preorder(root->left, a);
// preorder(root->right, a);
//}
//指針?lè)?/span>
void preorder(struct TreeNode* root, int* a, int* pi)
{
if (root == NULL)
return;
a[(*pi)++] = root->val;
preorder(root->left, a, pi);
preorder(root->right, a, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
int n = TreeSize(root);
int* a = (int*)malloc(sizeof(int) * n);
*returnSize = n;
//方法1：遞歸法
preorder(root, a, 0);
//方法2：全局變量法（不推薦）
//i= 0; --- 必須置0
//preorder(root, a); -- 全局變量法，但盡量不用
//方法3：指針?lè)?/span>
//int i = 0;
//preorder(root, a, &i);
return a;
}
3.5、練習(xí)題5：對(duì)稱二叉樹(shù)
對(duì)稱（鏡像）二叉樹(shù) — 給你一個(gè)二叉樹(shù)的根結(jié)點(diǎn)root,檢查它是否軸對(duì)稱。
思路：設(shè)計(jì)一個(gè)復(fù)用函數(shù)，繼續(xù)利用排除法和遞歸遍歷，排除不成立的結(jié)果，能成功返回的對(duì)稱二叉樹(shù)。
bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2)
{
if (root1 == NULL && root2 == NULL)
{
return true;
}
//一個(gè)為空，另一個(gè)不為空
if (root1 == NULL || root2 == NULL)
{
return false;
}
//都不為空
if (root1->val != root2->val)
{
return false;
}
return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
}
bool isSymmetric(struct TreeNode* root)
{
return _isSymmetric(root->left, root->right);
}
3.6、練習(xí)題6：另一棵樹(shù)的子樹(shù)
另一棵樹(shù)的子樹(shù)：給兩顆二叉樹(shù)，檢驗(yàn)一棵樹(shù)是否包含另一棵樹(shù)的子樹(shù)。
思路：結(jié)合上面相同的樹(shù)的方法，去匹配子樹(shù)文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-832574.html
//相同的樹(shù)
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
//都為空
if (p == NULL && q == NULL)
return true;
//其中一個(gè)為空
if (p == NULL || q == NULL)
return false;
//都不為空且不相等
if (p->val != q->val)
return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
//另一棵樹(shù)的子樹(shù)
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
//為空沒(méi)有子樹(shù)，匹配失敗
if (root == NULL)
return false;
//根節(jié)點(diǎn)匹配，調(diào)用相同的樹(shù)方法，去匹配
if (root->val == subRoot->val)
return isSameTree(root, subRoot);
//遞歸前序遍歷匹配
return isSameTree(root, subRoot) ||
isSameTree(root->left, subRoot) ||
isSameTree(root->right, subRoot);
}
3.7、練習(xí)題7：計(jì)算左葉子節(jié)點(diǎn)個(gè)數(shù)
計(jì)算二叉樹(shù)中左葉子節(jié)點(diǎn)的個(gè)數(shù)。
思路：遞歸遍歷左右子樹(shù)，累計(jì)左葉子節(jié)點(diǎn)個(gè)數(shù)即可。
1.判斷是否為空
2.判斷是否為左葉子節(jié)點(diǎn)
3.遞歸累加。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-832574.html
// 二叉樹(shù)左葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeftLeafSize(BTNode* root)
{
//為空返回0
if (root == NULL)
{
return 0;
}
//判斷有左孩子，并是左葉子節(jié)點(diǎn)
if (root->left && root->left->left == NULL && root->left->right == NULL)
{
return 1;
}
//其余情況的左葉子節(jié)點(diǎn)=左子樹(shù)葉子節(jié)點(diǎn)+右子樹(shù)葉子節(jié)點(diǎn)
return BinaryTreeLeftLeafSize(root->left) + BinaryTreeLeftLeafSize(root->right);
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的構(gòu)建和遍歷】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
