二叉树的存储结构（C++）
遍历：先序遍历，中序遍历，后序遍历
附上代码：//二叉树的存储和遍历，创建二叉树，后序的直接加上函数和算法
#include<iostream>
usingnamespace std;
typedefstruct Node{
char data;
struct Node *lchild,*rchild;
}*Bitree;
//创建二叉树
voidCreatBtree(Bitree &T)
{
//先序次序输入二叉树节点的值
char ch;
cin>>ch;
if(ch=='#')
{
T = NULL ;//树的值为空，用于返回上一层，递归结束点。
}
else{
T=new Node;
T->data = ch ;
//递归
CreatBtree(T->lchild);
CreatBtree(T->rchild);
}
}
//遍历二叉树
voidTravel(Bitree T)
{
if(T)
{
cout<<T->data;
Travel(T->lchild);
Travel(T->rchild);
}
}
int main(void)
{
Bitree T;
CreatBtree(T);
/*字符的输入 ABC##DE#G##F###*/
Travel(T);
return 0;
}
#代表值为NULL，返回上一层，撸多了没用，看图说话
算法:复制二叉树，计算二叉树的深度，统计二叉树节点的个数
//复制二叉树；
void CopyTree(Bitree T , Bitree &T1)
{
if(T== NULL)
{
T1= NULL;
return;
}
else{
T1 =new Node;
T1->data = T->data;
//递归
CopyTree(T->lchild,T1->lchild);
CopyTree(T->rchild,T1->rchild);
}
}
//深度计算层数//5
intDepth(Bitree T){
intm,n;
if(T==NULL)
{
return0;
}
else{
m= Depth(T->lchild)+1;
n= Depth(T->rchild)+1;
if(m>=n)
{
return m;
}
else{
return n;
}
}
}
//统计二叉树节点的个数
intCountTree(Bitree T){
if(T == NULL)
{
return0;
}
else{
return CountTree(T->lchild)+CountTree(T->rchild)+1;
}
}
//对于递归的理解，二叉树本身递归情况的分类就是空树和一个单独的节点，每一个节点，递归就是子树，我们只需要找到空树与一个节点的关系就可以很正确的理解递归。
#include<iostream>
using namespace std;
typedef struct Node{
char data;
struct Node *lchild,*rchild;
}*Bitree;
//创建二叉树
void CreatBtree(Bitree &T)
{
//先序次序输入二叉树节点的值
char ch;
cin>>ch;
if(ch=='#')
{
T = NULL ;//树的值为空，用于返回上一层，递归结束点。
}
else{
T=new Node;
T->data = ch ;
//递归
CreatBtree(T->lchild);
CreatBtree(T->rchild);
}
}
//遍历二叉树
void Travel(Bitree T)
{
if(T)
{
cout<<T->data;
Travel(T->lchild);
Travel(T->rchild);
}
}
//复制二叉树；
void CopyTree(Bitree T , Bitree &T1)
{
if(T == NULL)
{
T1 = NULL;
return ;
}
else{
T1 =new Node;
T1->data = T->data;
//递归
CopyTree(T->lchild,T1->lchild);
CopyTree(T->rchild,T1->rchild);
}
}
//二叉树的深度;
int Depth(Bitree T){
int m,n;
if(T==NULL)
{
return 0;
}
else{
m = Depth(T->lchild)+1;
n = Depth(T->rchild)+1;
if(m>=n)
{
return m;
}
else{
return n;
}
}
}
//统计二叉树的节点个数
int CountTree(Bitree T){
if(T == NULL)
{
return 0;
}
else{
return CountTree(T->lchild)+CountTree(T->rchild)+1;
}
}
int main(void)
{
Bitree T,T1;
CreatBtree(T);
/*字符的输入 ABC##DE#G##F###*/
Travel(T);
cout<<endl;
CopyTree(T ,T1);
Travel(T1);
cout<<endl;
cout<<Depth(T);//5
cout<<endl;
cout<<CountTree(T);
return 0;
}