二叉樹遍歷

• • 前言
  • 前序遍歷（Preorder Traversal）
  • 中序遍歷歷(Inorder Traversal)
  • 后序遍歷(Postorder Traversal)
  • 層序遍歷

創(chuàng)新互聯(lián)建站是一家集網(wǎng)站建設(shè),岳陽企業(yè)網(wǎng)站建設(shè),岳陽品牌網(wǎng)站建設(shè),網(wǎng)站定制,岳陽網(wǎng)站建設(shè)報價,網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,岳陽網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。前言

二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷以及層序遍歷。遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。

---

前序遍歷（Preorder Traversal）

深度優(yōu)先搜索（DFS)通常指的就是前序遍歷（也叫先序遍歷）；
遍歷順序：當(dāng)前結(jié)點（根節(jié)點 ）, 左子樹, 右子樹 即訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之前

代碼實現(xiàn)：

typedef struct BTNode
{char _data;
    struct BTNode* _left;
    struct BTNode* _right;
}BTNode;

// 二叉樹前序遍歷
void Preorder(BTNode* root)
{if (root == NULL) //如果為空，直接返回  后兩個遍歷簡化此過程
		return;
	printf("%d", root->_data);
	Preorder(root->_left);
	Preorder(root->_right);
}

圖解：

中序遍歷歷(Inorder Traversal)

遍歷順序：左子樹，根節(jié)點，右子樹 訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間）。

代碼實現(xiàn)：

typedef struct BTNode
{char _data;
    struct BTNode* _left;
    struct BTNode* _right;
}BTNode;

//二叉樹中序遍歷
void Inorder(BTNode* root)
{if(root)
    {Inorder(root->_left);
        printf("%c ", root->_data);
        Inorder(root->_right);
    }
}

后序遍歷(Postorder Traversal)

遍歷順序：左子樹，右子樹，根節(jié)點 訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之后。

代碼實現(xiàn)：

typedef struct BTNode
{char _data;
    struct BTNode* _left;
    struct BTNode* _right;
}BTNode;

// 二叉樹后序遍歷
void PostOrder(BTNode* root)
{if (root)
	{PostOrder(root->_left);
		PostOrder(root->_right);
		printf("%c", root->_data);
	}
}

由于被訪問的結(jié)點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為
根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

層序遍歷

也叫廣度優(yōu)先搜索(BFS）。遍歷順序：從所在二叉樹的根節(jié)點出發(fā)，從上到下按層遍歷，每層從左到右遍歷

代碼實現(xiàn)：

這里我們利用隊列其先進(jìn)先出的性質(zhì)，實現(xiàn)層序遍歷

隊列：

// Queue.h
#pragma once
 
#include#include#include 
#include// 前置聲明
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 QueueDestory(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);



//Queue.c
#include "Queue.h"
 
void QueueInit(Queue* pq)
{assert(pq);
	pq->head = pq->tail = NULL;
}
 
void QueueDestory(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));
	if (newnode == NULL)
	{printf("malloc fail\n");
		exit(-1);
	}
 
	newnode->data = x;
	newnode->next = NULL;
 
	if (pq->tail == NULL)
	{pq->head = pq->tail = newnode;
	}
	else
	{pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
 
// 隊頭出
void QueuePop(Queue* pq)
{assert(pq);
	assert(pq->head);
 
	// 1、一個
	// 2、多個
	if (pq->head->next == NULL)
	{free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
 
 
QDataType QueueFront(Queue* pq)
{assert(pq);
	assert(pq->head);
 
	return pq->head->data;
}
 
QDataType QueueBack(Queue* pq)
{assert(pq);
	assert(pq->head);
 
	return pq->tail->data;
}
 
int QueueSize(Queue* pq)
{assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{++size;
		cur = cur->next;
	}
 
	return size;
}
 
bool QueueEmpty(Queue* pq)
{assert(pq);
	return pq->head == NULL;
}

層序遍歷:

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

void LevelOrder(BTNode* root)
{Queue q;
	QueueInit(&q);
	if (root != NULL)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))  //隊列不為空則繼續(xù)
	{BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c", front->data);

		if (front->left) //if左邊不為空
		{	QueuePush(&q, front->left);
		}
		if (front->right)
		{	QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestory(&q);
}


int main()
{BTNode* root;
	LevelOrder(root);
}

---

本節(jié)完

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁標(biāo)題：二叉樹遍歷簡析【前序中序后序?qū)有虮闅v】-創(chuàng)新互聯(lián)
URL地址：http://weahome.cn/article/cehoss.html