一、前置說明
在學習二叉樹的基本操作前，需先要創(chuàng)建一棵二叉樹，然后才能學習其相關(guān)的基本操作。為了降低大家學習成本，此處手動快速創(chuàng)建一棵簡單的二叉樹，快速進入二叉樹操作學習。
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// 動態(tài)申請一個新節(jié)點
BTNode* BuyNode(BTDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
assert(newnode);
newnode->data = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}注意：上述代碼并不是創(chuàng)建二叉樹的方式。
二、構(gòu)建二叉樹
// 通過前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
if (*pi >= n)
{
return NULL;
}
char ch = a[*pi];
(*pi)++;
if (ch == '#')
{
return NULL;
}
BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
newNode->data = ch;
newNode->left = BinaryTreeCreate(a, n, pi);
newNode->right = BinaryTreeCreate(a, n, pi);
return newNode;
}
三、二叉樹的遍歷
學習二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂二叉樹遍歷 (Traversal) 是按照某種特定的規(guī)則，依次對二叉 樹中的節(jié)點進行相應(yīng)的操作，并且每個節(jié)點只操作一次。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎(chǔ)。
二叉樹的遍歷方式主要有四種，先介紹三種，最后再介紹第四種。（利用了分治的思想）
- 前序遍歷?(Preorder Traversal 亦稱先序遍歷)，方式為先遍歷根結(jié)點，左子樹，右子樹。
- 中序遍歷?(Inorder Traversal)，方式為先遍歷左子樹，根結(jié)點，右子樹。
- 后序遍歷?(Postorder Traversal)，方式為先遍歷左子樹，右子樹，根結(jié)點。
// 二叉樹前序遍歷
void PreOrder(BTNode* root);
// 二叉樹中序遍歷
void InOrder(BTNode* root);
// 二叉樹后序遍歷
void PostOrder(BTNode* root);其中這三種遍歷方式一般都用遞歸進行實現(xiàn)。
由于被訪問的結(jié)點必是某子樹的根，所以 N(Node）、L(Left subtree）和 R(Right subtree）又可解釋為 根、根的左子樹和根的右子樹。NLR、LNR 和 LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。
注意
：
- 深度優(yōu)先遍厲：前序遍厲、中序遍厲、后序遍厲，注意有些說法只認同前序遍厲。
- 廣度優(yōu)先遍厲：層序遍厲。
1、前序遍歷
按照前序遍歷的方式，我們應(yīng)該先遍歷根結(jié)點 A，然后再去遍歷左子樹。當進入左子樹后，我們需要再執(zhí)行前序遍歷方式，即遍歷 A 的左子樹中的根結(jié)點 B，然后再遍歷 B 的左子樹。當我們再進入左子樹，又是先遍歷根結(jié)點D，然后又遍歷左子樹，按照順序遍歷到 R，此時終于完成根結(jié)點，左子樹，接下來遍歷右子樹。進入右子樹后，又遍歷根結(jié)點T... ...，所以這種遍歷方式屬于遞歸性質(zhì)的。（遍歷順序為：A–>B–>D–>R–>T–>E–>Y–>C–>Q–>U–>W）
// 二叉樹前序遍歷
void BinaryTreePrevOrder(BTNode* root) // 根->左子樹->右子樹
{
if (root == NULL)
{
printf("# "); // 用#代表NULL
return;
}
printf("%c ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
【遞歸圖解】
2、中序遍歷
中序遍歷方式為左子樹，根結(jié)點，右子樹。仍以上面的圖為例，遍歷順序為：
R–>D–>T–>B–>E–>Y–>A–>Q–>U–>C–>W
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)// 左子樹->根->右子樹
{
if (root == NULL)
{
printf("# ");
return;
}
BinaryTreeInOrder(root->left);
printf("%c ", root->data);
BinaryTreeInOrder(root->right);
}3、后序遍歷
后序遍歷方式為?左子樹，右子樹，根結(jié)點。仍以上面的圖為例，遍歷順序應(yīng)該為：
R–>T–>D–>Y–>E–>B–>U–>Q–>W–>C–>A
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root) // 左子樹->右子樹->根
{
if (root == NULL)
{
printf("# ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}【總結(jié)】?
- 前序遍歷結(jié)果：1->2->3->4->5->6
- 中序遍歷結(jié)果：3->2->1->5->4->6
- 后序遍歷結(jié)果：3->2->5->6->4->1
4、層序遍歷
層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設(shè)二叉樹的根節(jié)點所在層數(shù)為 1，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點，然后從左到右訪問第 2 層上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點的過程就是層序遍歷。
// 層序遍歷
void LevelOrder(BTNode* root);注意：層序遍歷一般需要使用隊列。 （隊列內(nèi)容前面已經(jīng)詳細介紹過了）
【思路】先讓根入隊列，然后再讓根出隊列，當左子樹不為 NULL 時讓左子樹入隊列，當右子樹不為NULL時讓右子樹入隊列，然后不斷地迭代下去，直至隊列為空。記得出隊列前要保存當前值來訪問到該元素，Pop 到隊列當中的值是地址，通過該地址來訪問其中的 data。
層序遍歷結(jié)果為：?3->4->3->8->6->6->7
如何利用隊列實現(xiàn)呢？
- 判斷當前隊列是否為空。
- 隊列為空：結(jié)束；隊列非空：取出隊列第一個元素入隊列。
- 上一層出來后，再入下一層（即它的左右孩子節(jié)點）。
由于前面已經(jīng)對隊列的各種操作進行了詳解，這里就不展開講了。（直接運用之前寫的 Queue.c 和 Queue.h）
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root) // 樹的根節(jié)點root不為空 將根節(jié)點入隊列
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q); // 獲取隊列頭部元素
printf("%c ", front->data); // 打印節(jié)點值
QueuePop(&q); // 出隊列
// 如果當前樹根的左右孩子不為空 則分別入隊列
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestroy(&q);
}
?
四、二叉樹其它接口的實現(xiàn)
1、二叉樹的節(jié)點個數(shù)
按照遞歸的思想，計算二叉樹的節(jié)點數(shù)量，我們可以認為 二叉樹的節(jié)點個數(shù)?= 左子樹數(shù)量 + 右子樹數(shù)量 + 1，其中 1 是當前根節(jié)點數(shù)量（前提條件是存在根節(jié)點）。
【思想 1】
迭代，使用棧來模擬遞歸的過程，用全局變量 / 靜態(tài)局部變量來記錄節(jié)點個數(shù)，遍歷二叉樹的所有節(jié)點，并累加節(jié)點的個數(shù)。
【思想 2】
遞歸，利用分治的思想，函數(shù)使用帶返回值的方式，其內(nèi)部的遞歸本質(zhì)上是一個后序遍厲（左子樹->右子樹->根節(jié)點）。
// 二叉樹節(jié)點個數(shù)
int BinaryTreeSize(BTNode* root)
{
return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
?
2、二叉樹葉子節(jié)點個數(shù)
按照遞歸的思想，計算二叉樹的葉子節(jié)點數(shù)量，我們可以認為 葉子節(jié)點個數(shù) = 左子樹葉子節(jié)點個數(shù) + 右子樹葉子節(jié)點個數(shù) + 0，0 是因為當前根結(jié)點有子樹，說明根結(jié)點不是葉子結(jié)點。
【思想】
以 left 和 right 為標志，如果都為 NULL，則說明該節(jié)點是葉子節(jié)點。
// 二叉樹葉子節(jié)點個數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
// 先判斷當前訪問的節(jié)點是否為空
if (root == NULL)
{
return 0;
}
// 當前節(jié)點不為空，它的左右孩子都為空，說明該節(jié)點是葉子節(jié)點
if (root->left == NULL && root->right == NULL)
{
return 1;
}
// 當前節(jié)點不為空，左右孩子不都為空，則繼續(xù)往下遍歷
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
?
3、二叉樹第k層節(jié)點個數(shù)
【思想】
求當前樹的第 k 層節(jié)點個數(shù) = 左子樹的第 k-1 層節(jié)點個數(shù) + 右子樹的第 k-1 層節(jié)點個數(shù) (當 k=1 時，說明此層就是目標層)
?
// 二叉樹第k層節(jié)點個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
assert(k >= 1);
if (root == NULL) // 先判斷當前訪問的節(jié)點是否為空
{
return 0;
}
if (k == 1) // 當前節(jié)點不為空，而k已經(jīng)減到1了，說明遍歷到了第k層，說明該節(jié)點是第k層的
{
return 1;
}
// 還沒有遍歷到第k層，我們就繼續(xù)往下遍歷
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}如何知道這個節(jié)點是不是第 k 層的？
求二叉樹第 k 層的節(jié)點個數(shù)，我們從根節(jié)點開始往下遍歷（按根->左->右的順序），每遍歷一次 k 就減 1一次，當 k==1 時，說明我們遍歷到了第 k 層，此時訪問該層的節(jié)點。如果它不為空，則二叉樹第 k 層的節(jié)點個數(shù)就要 +1。
4、二叉樹查找值為x的節(jié)點
【思想】
按照遞歸思想，先判斷當前結(jié)點是否是目標節(jié)點，然后查找左子樹，再查找右子樹。
如果左右子樹都沒有找到，就返回NULL。
// 二叉樹查找值為x的節(jié)點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL) // 先判斷當前訪問的節(jié)點是否為空
{
return NULL;
}
if (root->data == x) // 判斷要找的x值節(jié)點是不是當前節(jié)點
{
return root;
}
// 不是當前節(jié)點，則繼續(xù)去該節(jié)點的左子樹中找
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1)
{
return ret1;
}
// 還沒找到，再繼續(xù)去該節(jié)點的右子樹中找
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
{
return ret2;
}
return NULL; // 當前節(jié)點及其左右子樹中都沒找到，返回NULL
}5、銷毀二叉樹
// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root)
{
// 如果使用前中序遍歷銷毀，節(jié)點會先被銷毀，變成隨機值，就不知道它的左右子樹位置了 所以采用后序遍歷銷毀
if (*root == NULL)
{
return;
}
BinaryTreeDestory(&((*root)->left));
BinaryTreeDestory(&((*root)->right));
free(*root);
*root = NULL; // 將根節(jié)點設(shè)置為NULL 防止野指針
}
注意：如果這里使用前序遍歷或中序遍歷進行銷毀，節(jié)點會先被銷毀，變成隨機值，就不知道它的左右子樹位置了，所以應(yīng)該采用后序遍歷來銷毀二叉樹。
如果這里傳進來的是一級指針，由于要在函數(shù)內(nèi)改變形參的值，無法改變外部實參的值，所以我們需要在函數(shù)外置頭節(jié)點指針為NULL。
6、判斷二叉樹是否是完全二叉樹
【思想】
層序遍歷時，把空節(jié)點也入隊列。
- 完全二叉樹中，非空節(jié)點是連續(xù)的，則空節(jié)點是連續(xù)的。
- 非完全二叉樹中，非空節(jié)點不是連續(xù)的，則空節(jié)點不是連續(xù)的。
所以在出隊時，判斷一下，出到第一個空節(jié)點時，跳出循環(huán)；
在下面重新寫一個循環(huán)繼續(xù)出隊，并檢查出隊元素：
- 如果第一個空節(jié)點后面的全是空節(jié)點，說明是完全二叉樹。
- 如果第一個空節(jié)點后面的有非空節(jié)點，說明是非完全二叉樹。
?
// 判斷二叉樹是否是完全二叉樹（利用層序遍歷的思想來判斷）
int BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root) // 樹的根節(jié)點root不為空 將根節(jié)點入隊列
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q); // 獲取隊列頭部元素
QueuePop(&q); //出隊列
if (front)
{
// 不管當前樹根的左右孩子是否為空，都分別入隊列
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
else
{
break; //遇到空后，跳出層序遍歷
}
}
// 如果后面全是空，則是完全二叉樹，否則不是完全二叉樹
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true; // 出隊的節(jié)點中，如果沒有出現(xiàn)非空節(jié)點，說明是完全二叉樹出隊的節(jié)點中，如果沒有出現(xiàn)非空節(jié)點，說明是完全二叉樹
}
文章來源：http://www.zghlxwxcb.cn/news/detail-663639.html
五、代碼整合
1、Queue.h
// Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);2、Queue.c
// Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
{
pq->tail = NULL;
}
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
int n = 0;
QNode* cur = pq->head;
while (cur)
{
++n;
cur = cur->next;
}
return n;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}3、test.c
// test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//動態(tài)申請一個新節(jié)點
BTNode* BuyNode(BTDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
assert(newnode);
newnode->data = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
// 通過前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
if (*pi >= n)
{
return NULL;
}
char ch = a[*pi];
(*pi)++;
if (ch == '#')
{
return NULL;
}
BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
newNode->data = ch;
newNode->left = BinaryTreeCreate(a, n, pi);
newNode->right = BinaryTreeCreate(a, n, pi);
return newNode;
}
// 二叉樹節(jié)點個數(shù)
int BinaryTreeSize(BTNode* root)
{
return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉樹葉子節(jié)點個數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
// 先判斷當前訪問的節(jié)點是否為空
if (root == NULL)
{
return 0;
}
// 當前節(jié)點不為空，它的左右孩子都為空，說明該節(jié)點是葉子節(jié)點
if (root->left == NULL && root->right == NULL)
{
return 1;
}
// 當前節(jié)點不為空，左右孩子不都為空，則繼續(xù)往下遍歷
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉樹第k層節(jié)點個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
assert(k >= 1);
if (root == NULL) // 先判斷當前訪問的節(jié)點是否為空
{
return 0;
}
if (k == 1) // 當前節(jié)點不為空，而k已經(jīng)減到1了，說明遍歷到了第k層，說明該節(jié)點是第k層的
{
return 1;
}
// 還沒有遍歷到第k層，我們就繼續(xù)往下遍歷
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉樹查找值為x的節(jié)點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL) // 先判斷當前訪問的節(jié)點是否為空
{
return NULL;
}
if (root->data == x) // 判斷要找的x值節(jié)點是不是當前節(jié)點
{
return root;
}
// 不是當前節(jié)點，則繼續(xù)去該節(jié)點的左子樹中找
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1)
{
return ret1;
}
// 還沒找到，再繼續(xù)去該節(jié)點的右子樹中找
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
{
return ret2;
}
return NULL; // 當前節(jié)點及其左右子樹中都沒找到，返回NULL
}
// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root)
{
// 如果使用前中序遍歷銷毀，節(jié)點會先被銷毀，變成隨機值，就不知道它的左右子樹位置了 所以采用后序遍歷銷毀
if (*root == NULL)
{
return;
}
BinaryTreeDestory(&((*root)->left));
BinaryTreeDestory(&((*root)->right));
free(*root);
*root = NULL; // 將根節(jié)點設(shè)置為NULL 防止野指針
}
// 二叉樹前序遍歷
void BinaryTreePrevOrder(BTNode* root) // 根->左子樹->右子樹
{
if (root == NULL)
{
printf("# "); // 用#代表NULL
return;
}
printf("%c ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)// 左子樹->根->右子樹
{
if (root == NULL)
{
printf("# ");
return;
}
BinaryTreeInOrder(root->left);
printf("%c ", root->data);
BinaryTreeInOrder(root->right);
}
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root) // 左子樹->右子樹->根
{
if (root == NULL)
{
printf("# ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root) // 樹的根節(jié)點root不為空 將根節(jié)點入隊列
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q); // 獲取隊列頭部元素
printf("%c ", front->data); // 打印節(jié)點值
QueuePop(&q); // 出隊列
// 如果當前樹根的左右孩子不為空 則分別入隊列
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestroy(&q);
}
// 判斷二叉樹是否是完全二叉樹（利用層序遍歷的思想來判斷）
int BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root) // 樹的根節(jié)點root不為空 將根節(jié)點入隊列
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q); // 獲取隊列頭部元素
QueuePop(&q); //出隊列
if (front)
{
// 不管當前樹根的左右孩子是否為空，都分別入隊列
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
else
{
break; //遇到空后，跳出層序遍歷
}
}
// 如果后面全是空，則是完全二叉樹，否則不是完全二叉樹
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true; // 出隊的節(jié)點中，如果沒有出現(xiàn)非空節(jié)點，說明是完全二叉樹出隊的節(jié)點中，如果沒有出現(xiàn)非空節(jié)點，說明是完全二叉樹
}
int main()
{
BTDataType a[] = { 'A', 'B', 'D', '#', '#', 'E', '#', 'H', '#', '#', 'C', 'F', '#', '#', 'G', '#', '#' };
int n = sizeof(a) / sizeof(a[0]) - 1; // 減去末尾的'\0'
int pos = 0;
BTNode* root = BinaryTreeCreate(a, n, &pos); // 構(gòu)建二叉樹
printf("TreeSize:%d\n", BinaryTreeSize(root)); // 二叉樹節(jié)點個數(shù)
printf("TreeLeafSize:%d\n", BinaryTreeLeafSize(root)); // 二叉樹葉子節(jié)點個數(shù)
printf("Tree2LevelSize:%d\n", BinaryTreeLevelKSize(root, 2)); // 二叉樹第k層節(jié)點個數(shù)
printf("TreeFindB:%p\n", BinaryTreeFind(root, 'B')); // 二叉樹查找值為x的節(jié)點
// 前序遍歷
BinaryTreePrevOrder(root);
printf("\n");
// 中序遍歷
BinaryTreeInOrder(root);
printf("\n");
// 后序遍歷
BinaryTreePostOrder(root);
printf("\n");
BinaryTreeLevelOrder(root); // 層序遍歷
printf("TreeComplete:%d\n", BinaryTreeComplete(root)); // 判斷二叉樹是否是完全二叉樹
BinaryTreeDestory(&root);// 二叉樹銷毀
printf("二叉樹已銷毀\n");
return 0;
}六、程序運行整體效果
文章來源地址http://www.zghlxwxcb.cn/news/detail-663639.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉樹的鏈式結(jié)構(gòu)的實現(xiàn) -- 詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
