二叉树建立与遍历递归操作c++实现

爱被打了一巴掌 2022-09-19 04:13 133阅读 0赞

\#include <iostream>  
\#include <cstdio>  
\#include <string>  
  
  
using namespace std;  
  
  
//二叉树的数据类型  
typedef char BiTType;  
  
  
//二叉树结构体  
typedef struct BiTNode  
\{  
BiTType data;  
BiTNode \*lChild,\*rChild;  
\}BiTNode,\*BiTree;  
  
  
//二叉树的类，可以进行二叉树的操作  
class BTree  
\{  
private:  
//先序遍历的字符串  
string Create;  
//线序遍历时候指向字符的下标  
int index;  
BiTNode \*root;  
public:  
//建立空二叉树  
BTree();  
//根据先序遍历的字符串建立二叉树  
BTree(string &c);  
BTree(char \*S);  
//递归函数  
void CreateBiTree(BiTree &T);  
//先序遍历  
void PreOrderTraverse();  
void Pre(BiTNode \*T);  
//中序遍历  
void InOrderTraverse();  
void In(BiTNode \*T);  
//后序遍历  
void PostOrderTraverse();  
void Post(BiTNode \*T);  
\};  
  
  
BTree::BTree()  
\{  
this->root = NULL;  
\}  
  
  
BTree::BTree(string &c)  
\{  
this->Create = c;  
this->index = 0;  
this->CreateBiTree(this->root);  
\}  
  
  
BTree::BTree(char \*S)  
\{  
this->Create = S;  
this->index = 0;  
this->CreateBiTree(this->root);  
\}  
  
  
void BTree::CreateBiTree(BiTree &T)  
\{  
BiTType temp;  
if((temp = this->Create\[this->index++\]) == '\#')  
\{  
T = NULL;  
\}  
else  
\{  
T = new BiTNode;  
T->data = temp;  
CreateBiTree(T->lChild);  
CreateBiTree(T->rChild);  
\}  
\}  
  
  
//先序遍历  
void BTree::PreOrderTraverse()  
\{  
this->Pre(this->root);  
\}  
void BTree::Pre(BiTNode \*T)  
\{  
if(T)  
\{  
cout<<T->data;  
Pre(T->lChild);  
Pre(T->rChild);  
\}  
\}  
//中序遍历  
void BTree::InOrderTraverse()  
\{  
this->In(this->root);  
\}  
void BTree::In(BiTNode \*T)  
\{  
if(T)  
\{  
In(T->lChild);  
cout<<T->data;  
In(T->rChild);  
\}  
\}  
//后序遍历  
void BTree::PostOrderTraverse()  
\{  
this->Post(this->root);  
\}  
void BTree::Post(BiTNode \*T)  
\{  
if(T)  
\{  
Post(T->lChild);  
Post(T->rChild);  
cout<<T->data;  
\}  
\}  
  
  
int main()  
\{  
cout<<"二叉树演示"<<endl;  
//建立二叉树  
BTree BT("abc\#\#de\#\#\#f\#g\#h\#\#");  
cout<<"二叉树先序遍历"<<endl;  
BT.PreOrderTraverse();  
cout<<endl;  
cout<<"二叉树中序遍历"<<endl;  
BT.InOrderTraverse();  
cout<<endl;  
cout<<"二叉树后序遍历"<<endl;  
BT.PostOrderTraverse();  
cout<<endl;  
return 0;  
\}