C++實(shí)現(xiàn)二叉樹(shù)的創(chuàng)建以及四種遍歷方式（遞歸與非遞歸）
語(yǔ)言這個(gè)東西不用真的會(huì)忘携狭， 我記得前前后后C++的基本語(yǔ)法我也看了好幾遍了捆昏，一直沒(méi)有動(dòng)手寫(xiě)過(guò)什么東西米诉，所以一遍遍的看肛著，一遍遍的忘... ...
正好最近在看數(shù)據(jù)結(jié)構(gòu)藤肢，想著自己用C++來(lái)實(shí)現(xiàn)一下太闺，一方面是熟悉整個(gè)邏輯過(guò)程，加深對(duì)數(shù)據(jù)結(jié)構(gòu)的理解嘁圈，另一方面省骂，也熟悉一下C++。
下圖是我們要?jiǎng)?chuàng)建的二叉樹(shù)最住，其中的#代表空字符钞澳；
二叉樹(shù)
為了驗(yàn)證我們程序的正確性，現(xiàn)給出此二叉樹(shù)的四種遍歷結(jié)果：
前序遍歷（Preorder traversal）： A B C D E F G H I J
中序遍歷（Inorder traversal）： C D B F E A I H G J
后序遍歷（Postorder traversal）：D C F E B I H J G A
層序遍歷（Levelorder traversal）：A B G C E H J D F I
此二叉樹(shù)中温学，共有結(jié)點(diǎn)10個(gè)略贮；深度為4；葉子結(jié)點(diǎn)格式為4，分別為D,F,I,J.
二叉樹(shù)節(jié)點(diǎn)的結(jié)構(gòu)體定義
struct Node {
char data;
Node* lchild, * rchild;
Node() = default;
explicit Node(char data) : data(data) { lchild = nullptr; rchild = nullptr; }
Node(char data, Node* left, Node* right) : data(data), lchild(left), rchild(right) {}
};
using BiTree = Node*; //起別名
創(chuàng)建二叉樹(shù)（遞歸逃延，通過(guò)前序遍歷創(chuàng)建）
void create(BiTree& node) {
char ch;
cin >> ch;
if (ch == '#') // '#' => null character
node = nullptr;
else {
node = new Node;
node->data = ch;
create(node->lchild); //遞歸
create(node->rchild);
}
}
要?jiǎng)?chuàng)建上圖所示的二叉樹(shù)览妖，我們要輸入它的前序遍歷：ABC#D##EF###GHI###J##
前序遍歷、中序遍歷以及后序遍歷（遞歸實(shí)現(xiàn)）
// 遞歸：實(shí)現(xiàn)前序遍歷 DLR
void preTraversal(BiTree root) {
if (root == nullptr) {
return;
}
cout << root->data << " ";
preTraversal(root->lchild);
preTraversal(root->rchild);
}
// 遞歸：實(shí)現(xiàn)中序遍歷 LDR
void inTraversal(BiTree root) {
if (root == nullptr) {
return;
}
inTraversal(root->lchild);
cout << root->data << " ";
inTraversal(root->rchild);
}
// 遞歸：實(shí)現(xiàn)后序遍歷 LRD
void postTraversal(BiTree root) {
if (root == nullptr) {
return;
}
postTraversal(root->lchild);
postTraversal(root->rchild);
cout << root->data << " ";
}
層序遍歷
// 層序遍歷
void LevelorderTraversal(BiTree root) {
if (root == nullptr)
return;
queue<BiTree> que;
que.push(root);
while (!que.empty()) {
auto node = que.front();
que.pop();
cout << node->data << " "; ;
if (node->lchild != nullptr)
que.push(node->lchild);
if (node->rchild != nullptr)
que.push(node->rchild);
}
}
前序遍歷揽祥、中序遍歷以及后序遍歷（非遞歸實(shí)現(xiàn)）
//非遞歸：實(shí)現(xiàn)二叉樹(shù)的中序遍歷
void InOrderTranversal(BiTree root) {
BiTree cur = root;
stack<BiTree> cs;
while (cur || !cs.empty()) {
if (cur != nullptr) {
cs.push(cur);
cur = cur->lchild;
}
else {
cur = cs.top();
cs.pop();
cout << cur->data << " ";
cur = cur->rchild;
}
}
}
// 非遞歸：實(shí)現(xiàn)二叉樹(shù)的前序遍歷
void PreOrderTranversal(BiTree root) {
vector<char> result;
stack<BiTree> st;
if (root == nullptr)
return;
st.push(root);
while (!st.empty()) {
auto node = st.top(); //node類(lèi)型為BiTree,也就是Node*
st.pop();
result.push_back(node->data);
if (node->rchild != nullptr)
st.push(node->rchild);
if (node->lchild != nullptr)
st.push(node->lchild);
}
Print(result);
}
// 非遞歸：實(shí)現(xiàn)二叉樹(shù)的后序遍歷
void PostOrderTranversal(BiTree root) {
vector<char> result;
stack<BiTree> st;
if (root == nullptr)
return;
st.push(root);
while (!st.empty()) {
auto node = st.top();
st.pop();
result.push_back(node->data);
if (node->lchild != nullptr)
st.push(node->lchild);
if (node->rchild != nullptr)
st.push(node->rchild);
}
reverse(result.begin(), result.end());
Print(result);
}
計(jì)算二叉樹(shù)的深度
int getDepth(BiTree root) {
if (root == nullptr)
return 0;
return max(getDepth(root->lchild), getDepth(root->rchild)) + 1;
}
計(jì)算二叉樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)
int getNodeCount(BiTree root) {
if (root == nullptr) {
return 0;
}
int l = getNodeCount(root->lchild);
int r = getNodeCount(root->rchild);
int count = l + r + 1;
return count;
}
計(jì)算二叉樹(shù)葉子結(jié)點(diǎn)的個(gè)數(shù)
int getLeafNodeCount(BiTree root) {
if (root == nullptr)
return 0;
if (root->lchild == nullptr && root->rchild == nullptr)
return 1;
return getLeafNodeCount(root->lchild) + getLeafNodeCount(root->rchild);
}
測(cè)試代碼
/*
* Software:Visual Studio 2022 Community
* Created by xiaoxin_zh@foxmail.com
* Implementing Binary Tree with C++
*/
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
using std::cin;
using std::cout;
using std::endl;
using std::stack;
using std::vector;
using std::queue;
using std::max;
int main() {
BiTree T;
cout << "Please enter the data of the node, # stands for empty : "; //ABC#D##EF###GHI###J##
create(T);
cout << "Created successfully!" << endl;
cout << "===========Preorder traversal=========== " << endl;
preTraversal(T);
cout << endl;
cout << "===========Inorder traversal=========== " << endl;
inTraversal(T);
cout << endl;
cout << "===========Postorder traversal=========== " << endl;
postTraversal(T);
cout << endl;
cout << "************Preorder traversal************" << endl;
PreOrderTranversal(T);
cout << endl;
cout << "************Inorder traversal************" << endl;
InOrderTranversal(T);
cout << endl;
cout << "************Postorder traversal************" << endl;
PostOrderTranversal(T);
cout << endl;
cout << "************Leverlorder traversal************" << endl;
LevelorderTraversal(T);
cout << endl;
cout << "The number of nodes in the binary tree is " << getNodeCount(T) << "." << endl;
cout << "The depth of the binary tree is " << getDepth(T) << "." << endl;
cout << "The number of leaf nodes in the binary tree is " << getLeafNodeCount(T) << "." << endl;
return 0;
}
執(zhí)行結(jié)果
執(zhí)行結(jié)果
以上代碼均已通過(guò)測(cè)試讽膏，如果有問(wèn)題請(qǐng)大家指出，我及時(shí)修改拄丰，以免造成誤導(dǎo)~
by xiaoxin_zh
2022/5/23
