柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)——二叉樹的層序遍歷

http://yzkb.51969.com/

?? 前言

hello hello~ ，這里是大耳朵土土垚~?? ，歡迎大家點(diǎn)贊拾拾關(guān)注??收藏???

?個人主頁：大耳朵土土垚的博客 ? 所屬專欄：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記 、C語言系列函數(shù)實(shí)現(xiàn) ?對于數(shù)據(jù)結(jié)構(gòu)順序表、鏈表、堆有疑問的都可以在上面數(shù)據(jù)結(jié)構(gòu)的專欄進(jìn)行學(xué)習(xí)哦~ 有問題可以寫在評論區(qū)或者私信我哦~

前面我們學(xué)習(xí)了二叉樹的三種遍歷前序、中序、后序，大家都還記得嗎？ 不記得的伙伴可以點(diǎn)擊這里二叉樹前、中、后序遍歷進(jìn)行查看哦~ 拾拾今天我們將學(xué)習(xí)另外一種遍歷——層序遍歷。

層序遍歷需要借助我們之前講過的隊(duì)列來實(shí)現(xiàn)，對隊(duì)列有疑問的可以點(diǎn)擊這里數(shù)據(jù)結(jié)構(gòu)——lesson5棧和隊(duì)列詳解進(jìn)行查看哦~

1.什么是層序遍歷？

除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點(diǎn)出發(fā)，首先訪問第一層的樹根節(jié)點(diǎn)，然后從左到右訪問第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷。

2.層序遍歷的實(shí)現(xiàn)

// 層序遍歷

void LevelOrder(BTNode* root);

實(shí)現(xiàn)之前我們還是簡單創(chuàng)造一顆符合我們心意的二叉樹：

BTNode* BuyNode(BTDataType x)

{

BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));

if (newnode == NULL)

{

perror("malloc fail");

return NULL;

}

newnode->right = NULL;

newnode->data = x;

newnode->left = 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;

}

二叉樹形狀如下：

//層序遍歷

void LevelOrder(BTNode* root)

{

Queue qt;//創(chuàng)建隊(duì)列

QueueInit(&qt);//隊(duì)列初始化

if (root)//判斷節(jié)點(diǎn)是否為空

QueuePush(&qt, root);//不為空入隊(duì)列

while (!QueueEmpty(&qt))//判斷隊(duì)列是否為空

{

BTNode* front = QueueFront(&qt);//不為空取隊(duì)頭值

printf("%d\n", front->data);//打印隊(duì)頭值

QueuePop(&qt);//刪除隊(duì)頭值

if (front->left)//接著將左右子樹的節(jié)點(diǎn)依次入隊(duì)列

QueuePush(&qt, front->left);

if (front->right)

QueuePush(&qt, front->right);

}

QueueDestroy(&qt);//銷毀隊(duì)列

}

層序遍歷利用隊(duì)列先進(jìn)先出的特點(diǎn)達(dá)到遍歷的效果，以上就是實(shí)現(xiàn)層序遍歷的函數(shù)啦~拾拾拾 運(yùn)行結(jié)果如下：

??隊(duì)列的實(shí)現(xiàn)在這里，記得使用前要聲明哦~ 也可以查看土土的博客二叉樹前、中、后序遍歷進(jìn)行詳細(xì)的學(xué)習(xí)。

typedef int BTDataType;

typedef struct BinaryTreeNode

{

BTDataType data;

struct BinaryTreeNode* left;

struct BinaryTreeNode* right;

}BTNode;

typedef BTNode* QDataType;

typedef struct QListNode

{

struct QListNode* pNext;

QDataType data;

}QNode;

// 隊(duì)列的結(jié)構(gòu)

typedef struct Queue

{

QNode* front;

QNode* rear;

}Queue;

// 初始化隊(duì)列

void QueueInit(Queue* q)

{

assert(q);

q->front = NULL;

q->rear = NULL;

}

// 隊(duì)尾入隊(duì)列

void QueuePush(Queue* q, QDataType data)

{

assert(q);

QNode* newnode = (QNode*)malloc(sizeof(QNode));//創(chuàng)建新節(jié)點(diǎn)

if (newnode == NULL)

{

perror("malloc fail");

return;

}

newnode->data = data;

newnode->pNext = NULL;

//隊(duì)列為空的情況入隊(duì)列

if (QueueEmpty(q))

{

q->front = newnode;

q->rear = newnode;

return;

}

//隊(duì)列不為空的情況入隊(duì)列

else

{

q->rear->pNext = newnode;

q->rear = newnode;

return;

}

}

// 隊(duì)頭出隊(duì)列

void QueuePop(Queue* q)

{

assert(q);

assert(!QueueEmpty(q));//判斷隊(duì)列非空

QNode* tmp = q->front;//先保存隊(duì)頭指針

q->front = tmp->pNext;

free(tmp);

}

// 獲取隊(duì)列頭部元素

QDataType QueueFront(Queue* q)

{

assert(q);

assert(!QueueEmpty(q));//判斷隊(duì)列非空

return q->front->data;

}

// 獲取隊(duì)列隊(duì)尾元素

QDataType QueueBack(Queue* q)

{

assert(q);

assert(!QueueEmpty(q));//判斷隊(duì)列非空

return q->rear->data;

}

// 獲取隊(duì)列中有效元素個數(shù)

int QueueSize(Queue* q)

{

assert(q);

assert(!QueueEmpty(q));//判斷隊(duì)列非空

int count = 0;//記錄元素個數(shù)

QNode* cur = q->front;

while (cur)

{

cur = cur->pNext;

count++;

}

return count;

}

// 檢測隊(duì)列是否為空，如果為空返回true,非空返回false

bool QueueEmpty(Queue* q)

{

assert(q);

return q->front == NULL;

}

// 銷毀隊(duì)列

void QueueDestroy(Queue* q)

{

assert(q);

//assert(!QueueEmpty(q));//判斷隊(duì)列非空

while (q->front)

{

QueuePop(q);

}

}

//隊(duì)列的特點(diǎn)是先進(jìn)先出

3.結(jié)語

層序遍歷關(guān)鍵點(diǎn)在于它對于隊(duì)列的使用與理解，拾拾大家都學(xué)廢了嗎完結(jié)撒花~ ???

柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)——二叉樹的層序遍歷

http://yzkb.51969.com/

文章鏈接