溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
本篇文章為大家展示了c++中怎么構(gòu)建一個先序二叉樹，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。
第一、定義BinaryTreeNode 類
#include <iostream>
#include <string>
#include <queue>
using namespace std;
template<typename T >class BinaryTree;
template <typename T> class BinaryTreeNode {
public:
friend class BinaryTree<T>;
BinaryTreeNode() {
data = NULL;
lChild = rChild = NULL;
}
BinaryTreeNode(T newdata) {
this->data = newdata;
lChild = rChild = NULL;
}
T getData() {
return data;
}
BinaryTreeNode<T> * getLeftNode() {
return lChild;
}
BinaryTreeNode<T> * getRightNode() {
return rChild;
}
T data;
BinaryTreeNode<T>* lChild;
BinaryTreeNode<T>* rChild;
private:
};View Code
第二、定義BinaryTree 類
template <typename T> class BinaryTree {
public:
BinaryTreeNode<T> *root;
char* p;
BinaryTree() { root = NULL; }
BinaryTree(T data) {
root = new BinaryTreeNode<T>(data);
root->lChild = NULL;
root->rChild = NULL;
}
~BinaryTree() {
delete root;
}
//構(gòu)建二叉樹并返回
BinaryTreeNode<T>* CreateTree() {
BinaryTreeNode<int>* bt = NULL;
char t;
cin >> t;
if (t == '#')
{
return NULL;
}
else {
int num = t - '0';
bt = new BinaryTreeNode<T>(num);
bt->lChild = CreateTree();
bt->rChild = CreateTree();
}
return bt;
}
//先序構(gòu)建二叉樹
BinaryTreeNode<T>* PreCreateTree() {
BinaryTreeNode<int>* bt = NULL;
if (this->root == NULL)
{
cout << "請輸入根節(jié)點（#代表空樹）:";
}
else {
cout << "請輸入節(jié)點（#代表空樹）:";
}
char t;
cin >> t;
if (t == '#')
{
return NULL;
}
else {
int num = t - '0';
bt = new BinaryTreeNode<T>(num);
if (this->root == NULL)
{
this->root = bt;
}
cout << bt->data << "的左孩子";
bt->lChild = PreCreateTree();
cout << bt->data << "的右邊孩子";
bt->rChild = PreCreateTree();
}
return bt;
}
void preOderTraversal(BinaryTreeNode<T> *bt); //先序遍歷
void inOrderTraversal(BinaryTreeNode<T> *bt); //中序遍歷
void postOrderTraversal(BinaryTreeNode<T> *bt);//后序遍歷
void levelTraversal(BinaryTreeNode<T> *bt); //逐層遍歷
private:
};
template <typename T>
void BinaryTree<T>::preOderTraversal(BinaryTreeNode<T> *bt) {
if (bt)
{
cout << bt->data;
BinaryTree<T>::preOderTraversal(bt->getLeftNode());
BinaryTree<T>::preOderTraversal(bt->getRightNode());
}
}
template <typename T>
void BinaryTree<T>::inOrderTraversal(BinaryTreeNode<T> *bt) {
if (bt)
{
BinaryTree<T>::inOrderTraversal(bt->getLeftNode());
cout << bt->data;
BinaryTree<T>::inOrderTraversal(bt->getRightNode());
}
}
template <typename T>
void BinaryTree<T>::postOrderTraversal(BinaryTreeNode<T> *bt) {
if (bt)
{
BinaryTree<T>::postOrderTraversal(bt->getLeftNode());
BinaryTree<T>::postOrderTraversal(bt->getRightNode());
cout << bt->data;
}
}
template <typename T>
void BinaryTree<T>::levelTraversal(BinaryTreeNode<T> *bt) {
queue<BinaryTreeNode<T>*> que;
que.push(bt);
while (!que.empty())
{
BinaryTreeNode<T>* proot = que.front();
que.pop();
cout << proot->data;
if (proot->lChild != NULL)
{
que.push(proot->lChild);//左孩子入隊
}
if (proot->rChild != NULL)
{
que.push(proot->rChild);//右孩子入隊
}
}
}View Code
第三、主程序運行
#include "pch.h"
#include <iostream>
#include "BinaryTree.h"
int main()
{
//場景測試2
BinaryTree<int> btree;
btree.PreCreateTree();//先序構(gòu)建二叉樹
cout << "先序遍歷:";
btree.preOderTraversal(btree.root); cout << endl;//先序遍歷
cout << "中序遍歷:";
btree.inOrderTraversal(btree.root); cout << endl;//中序遍歷
cout << "后序遍歷:";
btree.postOrderTraversal(btree.root); cout << endl;//后序遍歷
cout << "逐層序遍歷:";
btree.levelTraversal(btree.root);
}View Code
最終測試運行截圖
上述內(nèi)容就是c++中怎么構(gòu)建一個先序二叉樹，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼