数据结构-二叉树与遍历

（1）二叉树的顺序存储结构是比较浪费空间的，所以不推崇，也不做代码演示

（2）比较推崇的是链式存储结构

【1】前序遍历

#include<bits/stdc++.h>
using namespace std;
typedef char ElemType;
struct TreeNode{
	ElemType data;
	TreeNode *lchild;
	TreeNode *rchild;
};
typedef TreeNode* BiTree;
string str="ABDH#K###E##CFI###G#J##";//前序遍历创建的树 
int indx=0;
void createTree(BiTree *T)
{
	ElemType ch;
	ch=str[indx++];
	if(ch=='#')
	{
		*T=NULL;
	}
	else
	{
		*T=new TreeNode;
		(*T)->data=ch;
		createTree(&(*T)->lchild);
		createTree(&(*T)->rchild);
	}
}
void preOrder(BiTree T)
{
	if(T==NULL)
	{
		return;
	}
	cout<<T->data;
	preOrder(T->lchild);
	preOrder(T->rchild);
}

int main()
{
	BiTree T;
	createTree(&T);
	preOrder(T);
	cout<<endl;
}

【2】中序遍历

#include<bits/stdc++.h>
using namespace std;
typedef char ElemType;
struct TreeNode{
	ElemType data;
	TreeNode *lchild;
	TreeNode *rchild;
};
typedef TreeNode* BiTree;
string str="ABDH#K###E##CFI###G#J##";//前序遍历创建的树 
int indx=0;
void createTree(BiTree *T)
{
	ElemType ch;
	ch=str[indx++];
	if(ch=='#')
	{
		*T=NULL;
	}
	else
	{
		*T=new TreeNode;
		(*T)->data=ch;
		createTree(&(*T)->lchild);
		createTree(&(*T)->rchild);
	}
}
void inOrder(BiTree T)
{
	if(T==NULL)
	{
		return;
	}
	inOrder(T->lchild);
	cout<<T->data;
	inOrder(T->rchild);//就是前序遍历换一下位置 
}

int main()
{
	BiTree T;
	createTree(&T);
	inOrder(T);
	cout<<endl;
}

【3】后序遍历

#include<bits/stdc++.h>
using namespace std;
typedef char ElemType;
struct TreeNode{
	ElemType data;
	TreeNode *lchild;
	TreeNode *rchild;
};
typedef TreeNode* BiTree;
string str="ABDH#K###E##CFI###G#J##";//前序遍历创建的树 
int indx=0;
void createTree(BiTree *T)
{
	ElemType ch;
	ch=str[indx++];
	if(ch=='#')
	{
		*T=NULL;
	}
	else
	{
		*T=new TreeNode;
		(*T)->data=ch;
		createTree(&(*T)->lchild);
		createTree(&(*T)->rchild);
	}
}
void postOrder(BiTree T)
{
	if(T==NULL)
	{
		return;
	}
	postOrder(T->lchild);
	postOrder(T->rchild);//就是前序遍历换一下位置 
	cout<<T->data;
}

int main()
{
	BiTree T;
	createTree(&T);
	postOrder(T);
	cout<<endl;
}