運用C++實作二叉樹遍歷、確定二叉樹等重點知識
- 前序中序串、中序后序串建立二叉樹（前序后序無法確定一顆樹）
- 二叉樹遍歷
- 深度優先遍歷
- 遞回：前序、中序、后序
- 非遞回（較難）: 前序、中序、后序
- 廣度優先遍歷：從最高層（或最底層）開始，向下（向上）逐層訪問每一個節點，每一層自左向右訪問，
以下是代碼實作（附加注釋講解）：
#編譯環境：用的codeblocks，可以跑出來
- 深度優先遍歷
#include <iostream>
#include <string>
//#include <stack>
#include <queue>
using namespace std;
//建立一個自制的堆疊，也可以用庫中的stack堆疊
template<class T>
class node {
public:
T data;
node<T>* next;
node(T a) :data(a) { next = NULL; }
};
template<class T>
class Stack {
node<T>* tail;
public:
Stack() { tail = NULL; }
void pop() {
if (isempty())
cout << "is empty." << endl;
else {
node<T>* tem = tail;
tail = tail->next;
delete tem;
}
}
bool isempty() { return tail == NULL; }
T returntail() {
if (isempty()) {
cout << "is empty." << endl;
}
else {
return tail->data;
}
}
void push(T a) {
node<T>* tem = new node<T>(a);
if (isempty())
tail = tem;
else {
tem->next = tail;
tail = tem;
}
}
};
//建立二叉樹資料結點
template <class T>
class BinaryTreeNode {
private:
T data;
int count;
BinaryTreeNode<T> * lchild;
BinaryTreeNode<T> * rchild;
public:
BinaryTreeNode(T data) {
lchild = NULL;
rchild = NULL;
this->data = data;
}
BinaryTreeNode(const T &data, BinaryTreeNode<T> * l, BinaryTreeNode<T> *r) {
data = this->data; l = this->lchild; r = this->rchild;
}
BinaryTreeNode<T> * &getLchild() { return lchild; }
BinaryTreeNode<T> * &getRchild() { return rchild; }
void setLchild(BinaryTreeNode<T> *l) { l = this->lchild; }
void setRchild(BinaryTreeNode<T> *r) { r = this->rchild; }
T getData() const { return data; }
void visit() { cout << this->getData() << endl; }
void setData(const T&d) { d = this->data; }
bool isLeaf() const {
if (this->lchild == NULL && this->rchild == NULL) {
return true;
}
else {
return false;
}
}
};
//建立二叉樹
template <class T>
class BinaryTree {
private:
BinaryTreeNode<T> *root;
Stack<BinaryTreeNode<T> *>nodeStack;
queue<BinaryTreeNode<T> *>nodeQueue;
public:
BinaryTree<T>() {//默認構造了一顆簡單的二叉樹
root = new BinaryTreeNode<T>('a');
root->getLchild() = new BinaryTreeNode<T>('b');
root->getRchild() = new BinaryTreeNode<T>('c');
root->getLchild()->getLchild() = new BinaryTreeNode<T>('d');
root->getLchild()->getRchild() = new BinaryTreeNode<T>('e');
root->getRchild()->getLchild() = new BinaryTreeNode<T>('f');
}
BinaryTree<T>(BinaryTreeNode<T> *node):root(node){}
~BinaryTree<T>() {}
bool isEmpty() const {
if (this->root == NULL) {
return true;
}
else {
return false;
}
}
BinaryTreeNode<T> *getRoot() { return this->root; }
//前序遞回遍歷
void preOrder(BinaryTreeNode<T> *root) {
if (root != NULL) {
root->visit();
preOrder(root->getLchild());
preOrder(root->getRchild());
}
}
//中序遞回遍歷
void inOrder(BinaryTreeNode<T> *root) {
if (root != NULL) {
inOrder(root->getLchild());
root->visit();
inOrder(root->getRchild());
}
}
//后序遞回遍歷
void nextOrder(BinaryTreeNode<T> *root){
if(root!=NULL){
nextOrder(root->getLchild());
nextOrder(root->getRchild());
root->visit();
}
}
//前序非遞回遍歷
void preOrderWithoutRe(BinaryTreeNode<T> *root) {
BinaryTreeNode<T> *p = root;//保存根節點
while (!nodeStack.isempty() || p) {
if (p != NULL) {
p->visit();
if (p->getRchild() != NULL) {
nodeStack.push(p->getRchild());//當前節點的右子樹根節點入堆疊
}
p = p->getLchild();//轉向訪問左子樹
}
else {//左子樹訪問完畢，訪問右子樹
p = nodeStack.returntail();
nodeStack.pop();
}
}
}
//中序非遞回遍歷
void inOrderWithoutRe(BinaryTreeNode<T> *root) {
BinaryTreeNode<T>*p = root;
while (!nodeStack.isempty() || p) {
if (p != NULL) {
nodeStack.push(p);
p = p->getLchild();
}
else {
p = nodeStack.returntail();
p->visit();
p = p->getRchild();
nodeStack.pop();
}
}
}
//后序非遞回遍歷
void nextOrderWithoutRe(BinaryTreeNode<T> *root){
BinaryTreeNode<T> p = root;
//每次訪問根節點，都需要判斷左右孩子是否存在，需要訪問兩次根節點，用count記錄訪問次數
while(!nodeStack.isempty()||p){
while(p != NULL){
p.count=1;
nodeStack.push(p);
p = p->getLchild();
}
if(!nodeStack.isempty()){
p=nodeStack.returntail();
if(p.count==1){
p.count=2;
p=p.getRchild();
}
}else{
if(p.count==2){
p.visit();
nodeStack.pop(p);
}
}
}
}
//廣度優先遍歷
void FromToptoButtom(BinaryTreeNode<T> *node){
BinaryTreeNode<T> *p=node;
if(p==NULL){
return;
}
nodeQueue.push(p);
while(!nodeQueue.empty()){
p=nodeQueue.front();
p->visit();
nodeQueue.pop();
if(p->getLchild()!=NULL){
nodeQueue.push(p->getLchild());
}
if(p->getRchild()!=NULL){
nodeQueue.push(p->getRchild());
}
}
}
};
//前序中序確定二叉樹
int FindRoot1(char* b, int n, char v)
{
int pos = -1;
for (int i = 0; i < n; i++)
{
if (b[i] == v)
{
pos = i;
break;
}
}
return pos;
}
template<class T>
BinaryTreeNode<T> * BuildTree1(T *a, T *b, int len) {
BinaryTreeNode<T> *root = NULL;
if (len > 0) {
root = new BinaryTreeNode<T>(a[0]);
int pos = FindRoot1(b, len, a[0]);
if (pos == -1)
exit(1);//例外退出
root->getLchild() = BuildTree1(a + 1, b, pos);//遞回建立左子樹
root->getRchild() = BuildTree1(a + pos + 1, b + 1 + pos, len - pos - 1);//遞回建立右子樹
}
return root;
}
//中序后序確定二叉樹
int FindRoot2(char* b, int n, char v){
int pos = -1;
for (int i = n-1 ; i >= 0 ; i--)
{
if (b[i] == v)
{
pos = i;
break;
}
}
return pos;
}
template<class T>
BinaryTreeNode<T> *BuildTree2(T *c, T *b ,int len){
BinaryTreeNode<T> *root = NULL;
if(len>0){
root = new BinaryTreeNode<T>(c[len-1]);
int pos = FindRoot2(b,len,c[len-1]);
if(pos == -1)
exit(1);
root->getLchild()=BuildTree2(c,b,pos);
root->getRchild()=BuildTree2(c+pos,b+pos+1,len-pos-1);
}
return root;
}
int main() {
char a[10] = {'A','B','D','G','C','E','F'};
char b[10] = {'D','G','B','A','E','C','F'};
char c[10] = {'G','D','B','E','F','C','A'};
BinaryTree<char> tree1(BuildTree1(a, b, 10));
cout<<"前序中序構建二叉樹"<<endl;
preOrder(tree1.getRoot());
cout<<"中序后序構建二叉樹"<<endl;
BinaryTree<char> tree3(BuildTree2(c,b,7));
tree3.preOrder(tree3.getRoot());
BinaryTree<char> tree2;
cout<<"廣度優先遍歷"<<endl;
tree2.FromToptoButtom(tree2.getRoot());
cout<<"前序遞回遍歷"<<endl;
tree2.preOrder(tree2.getRoot());
cout<<"中序遞回遍歷"<<endl;
tree2.inOrder(tree2.getRoot());
cout<<"后序遞回遍歷"<<endl;
tree2.nextOrder(tree2.getRoot());
cout<<"前序非遞回遍歷"<<endl;
tree2.preOrderWithoutRe(tree2.getRoot());
cout<<"中序非遞回遍歷"<<endl;
tree2.inOrderWithoutRe(tree2.getRoot());
cout<<"后序非遞回遍歷"<<endl;
tree2.nextOrder(tree2.getRoot());
}
在csdn上發的第一篇原創文章！紀念一下！
后續會繼續更新資料結構、安卓、大資料等相關內容（包括但不限于此）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/357050.html
標籤：其他
下一篇：圖解電動汽車：電動汽車簡介