前言
- 《數(shù)據(jù)結(jié)構(gòu)系列首頁》是數(shù)據(jù)結(jié)構(gòu)系列文章的首頁，其中會逐步更新各種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，有興趣的選手可以一看。
- 首頁中不僅有各種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，還有學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)必備的基礎(chǔ)知識，如果有選手覺得自己的基礎(chǔ)不太牢固，可以先將搞定基礎(chǔ)知識，之后再攻克數(shù)據(jù)結(jié)構(gòu)這一部分的內(nèi)容。
- 由于我也是剛開始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程，所以如果發(fā)現(xiàn)文章中存在錯誤，希望大家可以直接指出，我將第一時間修改。
- 更多數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)請見《數(shù)據(jù)結(jié)構(gòu)系列文章》，我會在學(xué)習(xí)完新的數(shù)據(jù)結(jié)構(gòu)后不斷更新其中的內(nèi)容。
一、開場白
樹是一種比起線性表更加復(fù)雜的存儲結(jié)構(gòu)，其是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，樹結(jié)構(gòu)在客觀世界中普遍存在，其中二叉樹的運用最為廣泛。本篇文章主要介紹了二叉樹的鏈式存儲結(jié)構(gòu)（即二叉鏈表）的創(chuàng)建與遍歷，這將為以后對二叉樹的研究起到至關(guān)重要的作用。
二、二叉樹結(jié)點的設(shè)計
考慮到二叉樹中的每個結(jié)點最多可以指向兩個結(jié)點，所以為二叉樹的結(jié)點設(shè)置一個數(shù)據(jù)域和兩個指針域是非常自然的想法。
typedef char TreeElemType; // 定義二叉樹的元素類型為字符類型
// 定義二叉樹結(jié)點
typedef struct TreeNode
{
TreeElemType data; // 數(shù)據(jù)域
struct TreeNode* leftchild; // 左指針域
struct TreeNode* rightchild; // 右指針域
}TreeNode, * TREE; // TREE 等同于 struct TreeNode *
二叉樹結(jié)點結(jié)構(gòu)如下圖所示：
三、二叉樹的遍歷
先序遍歷
- 先序遍歷規(guī)則
若二叉樹為空，則不進行遍歷；否則先訪問根結(jié)點，然后前序遍歷左子樹，再前序遍歷右子樹。如下圖所示，先序遍歷的結(jié)果為ABDGHCEIF。由遍歷結(jié)果可知，先序遍歷屬于深度優(yōu)先遍歷，即優(yōu)先向樹的最深處探索。
- 先序遍歷遞歸算法
void pre_order_traverse(TREE T)
{
if (T) // T為空是遞歸結(jié)束的條件
{
putchar(T->data); // 打印根結(jié)點的數(shù)據(jù)
pre_order_traverse(T->leftchild); // 先序遍歷左子樹
pre_order_traverse(T->rightchild); // 先序遍歷右子樹
}
}
中序遍歷
- 中序遍歷規(guī)則
若二叉樹為空，則不進行遍歷；否則先中序遍歷左子樹，然后訪問根結(jié)點，再中序遍歷右子樹。如下圖所示，中序遍歷的順序為GDHBAEICF。
在寫二叉樹的中序遍歷結(jié)果時，有個更加快捷的方法：從樹根向下將二叉樹一腳踩扁，之后按照踩扁后的樹，從左至右依次寫出各結(jié)點的數(shù)據(jù)即可。以上圖中的樹為例，踩扁之后就變成了下圖：
根據(jù)結(jié)點從左到右出現(xiàn)的次序，想象所有的結(jié)點都在一條線上，這樣寫出各結(jié)點的數(shù)據(jù)后得到的便是該樹的中序遍歷結(jié)果，即GDHBAEICF。文章來源：http://www.zghlxwxcb.cn/news/detail-445621.html
- 中序遍歷遞歸算法
void in_order_traverse(TREE T)
{
if (T) // T為空是遞歸結(jié)束的條件
{
in_order_traverse(T->leftchild); // 中序遍歷左子樹
putchar(T->data); // 打印根結(jié)點的數(shù)據(jù)
in_order_traverse(T->rightchild); // 中序遍歷右子樹
}
}
- 中序遍歷非遞歸算法
中序遍歷非遞歸算法用到了鏈棧的部分知識，，詳細內(nèi)容可以參見《鏈棧的實現(xiàn)》這篇文章。文章來源地址http://www.zghlxwxcb.cn/news/detail-445621.html
- 鏈棧結(jié)構(gòu)的設(shè)計
typedef TREE StackElemType; // 定義棧的元素類型為樹結(jié)點的指針
// 定義棧的結(jié)點
typedef struct StackNode
{
StackElemType data; // 數(shù)據(jù)域
struct StackNode* next; // 指針域
}StackNode, * STACK; // STACK 等同于 struct StackNode *
// 定義鏈棧結(jié)構(gòu)
typedef struct LinkedStack
{
STACK top; // 棧頂指針
int length; // 當(dāng)前棧中元素的個數(shù)
}LinkedStack;
- 鏈棧操作函數(shù)的聲明
void init_stack(LinkedStack&);
void push_stack(LinkedStack&, StackElemType);
bool stack_is_empty(LinkedStack&);
bool pop_stack(LinkedStack&, StackElemType&);
void destroy_stack(LinkedStack&);
- 鏈棧操作函數(shù)
// 初始化鏈棧S到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉樹的創(chuàng)建和四種遍歷（附帶詳細注釋）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
