本文目录一览：
- 1、Python 二叉树的创建和遍历、重建
- 2、编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历的各种递归和非递归算法，以及层次遍历的算法
- 3、层序遍历二叉树
- 4、求二叉树的层次遍历代码，求高手！！！
- 5、二叉树的层次遍历算法
Python 二叉树的创建和遍历、重建
几个有限元素的集合，该集合为空或者由一个根（Root）的元素及两不相交的（左子树和右子树）的二叉树组成，是有序树，当集合为空时，称为空二叉树，在二叉树中，一个元素也称为一个结点。
前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树
中序遍历：若树为空，则空操作返回，否则从根结点开始（不是先访问根结点），中序遍历根结点的左子树，然后访问根节点，最后中序遍历右子树。
后序遍历：若树为空，则空操作返回，否则从左到右先访问叶子结点后结点的方式遍历左右子树，最后访问根节点。
层序遍历：若树为空，则空操作返回，否则从树的每一层，即从根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
假设已知后序遍历和中序遍历结果，从后序遍历的结果可以等到最后一个访问的结点是根节点，对于最简单的二叉树，此时在中序遍历中找到根节点之后，可以分辨出左右子树，这样就可以重建出这个最简单的二叉树了。而对于更为复杂的二叉树，重建得到根结点和暂时混乱的左右结点，通过递归将左右结点依次重建为子二叉树，即可完成整个二叉树的重建。（在得到根结点之后，需要在中序遍历序列中寻找根结点的位置，并将中序序列拆分为左右部分，所以要求序列中不能有相同的数字，这是序列重建为二叉树的前提。）
Root =None
strs="abc##d##e##" #前序遍历扩展的二叉树序列
vals =list(strs)
Roots=Create_Tree(Root,vals)#Roots就是我们要的二叉树的根节点。
print(Roots)
inorderSearch = inOrderTraverse2(Roots)
print(inorderSearch)
编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历的各种递归和非递归算法，以及层次遍历的算法
文件 main.cpp 代码如下：
#includemalloc.h // malloc()等
#includestdio.h // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#includestdlib.h // atoi()，exit()
#includemath.h // 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree T)
{ // 操作结果：构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T-data=number; // 将值赋给T所指结点
CreateBiTree(T-lchild); // 递归构造左子树
CreateBiTree(T-rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T-lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T-rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T-data); // 先访问根结点
PreOrderTraverse(T-lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T-rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T-lchild,Visit); // 先中序遍历左子树
Visit(T-data); // 再访问根结点
InOrderTraverse(T-rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T-lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T-rchild,Visit); // 再后序遍历右子树
Visit(T-data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
这样可以么？
层序遍历二叉树
#includestdio.h
#includestdlib.h
#define m 100
typedef char etype;
typedef struct bitnode
{
etype data;
struct bitnode *lch,*rch;
}bitnode,*bitree;
bitree que[m];
int front=0,rear=0;
bitnode *creat_bt1();
bitnode *creat_bt2();
void preorder(bitnode *p);
void inorder(bitnode *p);
void postorder(bitnode *p);
void enqueue(bitree);
bitree delqueue();
void levorder(bitree);
int treedepth(bitree);
void prtbtree(bitree,int);
void exchange(bitree);
int leafcount(bitree);
void paintleaf(bitree);
bitnode *t;
int count=0;
void main()
{
char ch;int k;
do{
printf("\n\n\n");
printf("\n==========主菜单==============");
printf("\n 1.建立二叉树方法 1");
printf("\n 2.建立二叉树方法 2");
printf("\n 3.先序递归遍历二叉树");
printf("\n 4.中序递归遍历二叉树");
printf("\n 5.后序递归遍历二叉树");
printf("\n 6.层次遍历二叉树");
printf("\n 7.计算二叉树的高度");
printf("\n 8.计算二叉树中叶结点个数");
printf("\n 9.交换二叉树的左右子树");
printf("\n 10.打印二叉树");
printf("\n 0.结束程序运行");
printf("\n===============================");
printf("\n 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)");
scanf("%d",k);
switch(k)
{case 1:t=creat_bt1();break;
case 2:printf("\n请输入二叉树各节点的值：");fflush(stdin);
t=creat_bt2();break;
case 3:if(t)
{printf("先序遍历二叉树：");
preorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 4:if(t)
{printf("中序遍历二叉树：");
inorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 5:if(t)
{printf("后序遍历二叉树：");
postorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 6:if(t)
{printf("层次遍历二叉树：");
levorder(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 7:if(t)
{printf("二叉树的高度为：%d",treedepth(t));
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 8:if(t)
{printf("二叉树的叶子结点数为：%d\n",leafcount(t));
printf("二叉树的叶结点数为：");paintleaf(t);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 9:if(t)
{printf("二叉树的左右子树：\n");
exchange(t);
prtbtree(t,0);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 10:if(t)
{printf("逆时针旋转90度输出的二叉树：\n");
prtbtree(t,0);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case 0:exit(0);
}
}while(k=1k=10);
printf("\n再见! 按回车键，返回…\n");
ch=getchar();
}
bitnode *creat_bt1()
{
bitnode *t,*p,*v[20];int i,j;etype e;
printf("\n请输入二叉树各结点的编号和对应的值(如：1，a):");
scanf("%d,%c",i,e);
while(i!=0e!='#')
{
p=(bitnode *)malloc(sizeof(bitnode));
p-data=e;p-lch=NULL;p-rch=NULL;
v[i]=p;
if(i==1)t=p;
else
{j=i/2;
if(i%2==0) v[j]-lch=p;
else
v[j]-rch=p;
}
printf("\n 请继续输入二叉树各结点的编号和对应的值：");
scanf("%d,%c",i,e);
}
return(t);
}
bitnode *creat_bt2()
{
bitnode *t;etype e;
scanf("%c",e);
if(e=='#')
t=NULL;
else
{
t=(bitnode *)malloc(sizeof(bitnode));
t-data=e;
t-lch=creat_bt2();
t-rch=creat_bt2();
}
return(t);
}
void preorder(bitnode *p){
if(p)
{
printf("%3c",p-data);
preorder(p-lch);
preorder(p-rch);
}
}
void inorder(bitnode *p)
{
if(p){
inorder(p-lch);
printf("%3c",p-data);
inorder(p-rch);
}
}
void postorder(bitnode *p)
{
if(p)
{
postorder(p-lch);
postorder(p-rch);
printf("%3c",p-data);
}
}
void enqueue(bitree T)
{
if(front!=(rear+1)%m)
{rear=(rear+1)%m;
que[rear]=T;}
}
bitree delqueue()
{
if(front==rear)return NULL;
front=(front+1)%m;
return(que[front]);
}
void levorder(bitree T)
{
bitree p;
if(T)
{
enqueue(T);
while(front!=rear)
{
p=delqueue();
printf("%3c",p-data);
if(p-lch!=NULL)enqueue(p-lch);
if(p-rch!=NULL)enqueue(p-rch);
}
}
}
int treedepth(bitree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=treedepth(bt-lch);
hr=treedepth(bt-rch);
max=(hlhr)? hl:hr;
return(max+1);
}
else
return(0);
}
void prtbtree(bitree bt,int level)
{
int j;
if(bt){
prtbtree(bt-rch,level+1);
for(j=0;j=6*level+1;j++)printf(" ");
printf("%c\n",bt-data);
prtbtree(bt-lch,level+1);
}
}
void exchange(bitree bt)
{
bitree p;
if(bt)
{p=bt-lch;bt-lch=bt-rch;bt-rch=p;
exchange(bt-lch);exchange(bt-rch);
}
}
int leafcount(bitree bt)
{
if(bt!=NULL)
{
leafcount(bt-lch);
leafcount(bt-rch);
if((bt-lch==NULL)(bt-rch==NULL))
count++;
}
return(count);
}
void paintleaf(bitree bt)
{
if(bt!=NULL)
{
if(bt-lch==NULLbt-rch==NULL)
printf("%3c",bt-data);
paintleaf(bt-lch);
paintleaf(bt-rch);
}
}
求二叉树的层次遍历代码，求高手！！！
#include "stdio.h"typedef int Datatype#define MAXNODE 100
//二叉链表的存储typedef struct BiTNode { Datatype data; struct BiTNode *lchild,*rchild;//左右孩子指针}BiTreeNode,*BiTree;
//三叉链表的存储typedef struct BiTNode { Datatype data; struct BiTNode *lchild,*rchild,*parent;}BiTreeNode,*BiTree;
//算法3.1：二叉树的先序遍历递归算法void PreOrder(BiTree bt){ if(bt!=NULL){ visit(bt-data);//访问根结点 PreOrder(bt-lchild); PreOrder(bt-rchild); }}
//算法3.2：二叉树的中序遍历递归算法void InOrder(BiTree bt){ if(bt!=NULL){ InOrder(bt-lchild); visit(bt-data); InOrder(bt-rchild); }}
//算法3.3：二叉树的后序遍历递归算法void InOrder(BiTree bt){ if(bt!=NULL){ InOrder(bt-lchild); InOrder(bt-rchild); visit(bt-data); }}
//算法3.4：二叉树的层次遍历算法void LevelOrder(BiTree bt){ BiTreeNode Queue[MAXNODE]; //定义队列 int front,rear; if(bt==NULL) return //空二叉树，遍历结束 front=-1; rear=0; Queue[rear]=bt; //根结点入队 while(rear!=front){ //队列不空，继续遍历；否则，遍历结束 front++; //出队 visit(Queue[front]-data); //访问刚出队的元素 if(Queue[front]-lchild!=NULL){ //如果有左孩子，左孩子入队 rear++; Queue[rear]=Queue[front]-lchild; } if(Queue[front]-rchild!=NULL){ //如果有右孩子，右孩子入队 rear++; Queue[rear]=Queue[front]-rchild; } }}
//算法3.5：中序遍历的非递归算法void NRInOrder(BiTree bt){ BiTree S[MAXNODE],p=bt;//定义栈 int top=-1; if(bt==NULL) return;//空二叉树，遍历结束 while(!(p==NULLtop==0)){ while(p!=NULL){ if(topMAXNODE-1) S[top++]=p;//当前指针p入栈 else{printf("栈溢出\n");return;} p=p-lchild;//指针指向p的左孩子结点 } if(top==-1) return //栈空，结束 else{ p=S[--top];//弹出栈顶元素 visit(p-data);//访问结点的数据域 p=p-rchild;//指向p的右孩子结点 } }}
//算法3.6：根据先序与中序遍历结果建立二叉树void PreInOrd(char preord[],char inord[],int i,int j,int k,int h,BiTree *t)//先序序列从i到j,中序序列从k到h，建立一个二叉树放到t中{ int m; (*t)=new BTNode; (*t)-data=preord[i];//二叉树的根 m=k; while (i[m]!=preord[i])m++;//在中序序列中定位树根 /********递归调用建立左子树******/ if(m==k)(*t)-left=NULL; else PreInOrd(preord,inord,i+1,i+m-k,k,m-1,(*t)-left); /********递归调用建立左子树******/ if(m==k)(*t)-right=NULL; else PreInOrd(preord,inord,i+1,i+m-k,k,m-1,(*))-right);}BTree * createBT(char preord[],char inord[],int n,BTree root)//n为二叉树接点的个数，建立的二叉树放在root中{ if(n=0) root=NULL; else PreInOrd(preord,inord,1,n,1,n,root) return root;}
//算法3.7：统计二叉树的叶子结点算法int BitreeLeaf(BTree bt) if(bt==NULL) return 0; if(bt-left==NULL bt-right==NULL) return 1; return (BitreeLeaf(bt-left)+BirLeaf(bt-right));}
//算法3.8：求二叉树深度算法int BitreeDepth (BiTree bt){ if(bt==NULL) return 0; if(bt-lchild==NULL bt-rchild==NULL) return1; depthL=BitreeDepth(bt-lchild); depthR=BitreeDepth(bt-rchild); return 1+max(depthL,depthR);}
//算法3.12：二叉树的查找算法BiTree SearchBST(BiTree bt,KeyType key){ if(bt==NULL || key==bt-data.key) return bt; if(keybt-data.key) return SearchBST(bt-lchild,key); else return SearchBST(bt-rchild,key);}
//算法3.13：在二叉树中插入结点int InseartBST(BiTreeNode **bt,Datatype e){ BiTreeNode *qq=new BiTreeNode(),*pp=new BiTreeNode(); BiTreeNode **qq=qq,*s,**p=pp; *q=OxO; *p=OxO; if(SearchBST(*bt,e.key,p,q)==0)//待查结点是否在二叉排序树中 { s=new BiTreeNode(); s-data=e;s-lchild=s-rchild=OxO;//待查结点 if(!(*q)) *bt=s;//二叉树的根 else if(e.key(*q)-data.key) (*q)-lchild=s;//作为左儿子插入 else(*q)-rchild=s;//作为右儿子插入 return 1; } else return 0;}
//算法3.14：在二叉排序树中删除结点int DeleteNode(BitreeNode **t,int key){ BiTreeNode *pp=new BiTreeNode(),*ff=new BiTreeNode; BiTreeNode **p=pp,*s,*q,**f=ff; *p=OxO;*f=OxO; int flag=0; if(SearchBST(*t,key,f,p)!=0){ flag=1;//查找成功，置删除标记，待删除结点为p if(!((*p)-rchild)){//结点无右儿子，结点只有一个分支或为叶子结点 if((*f)-lchild==*p) (*f)-lchild=(*P)-lchild; else (*f)-rchild=(*p)-lchild; } else{//结点有右儿子 if(!((*p)-lchild)){//结点无左儿子，一个分支 if((*f)-lchild==*p) (*f)-lchild=(*P)-rchild; else (*f)-rchild=(*p)-rchild; } else {//结点有左二子，两个分支 q=*p; s=(*p)-lchild; while(s-rchild){q=s;s=s-rchild;}//在结点p的左分支上沿右指针域往下找，直到右指针域为空时为止 (*p)-data=s-data; if(q!=*p){(q)-rchild=s-lchild;} else(q)-lcild=s-lchild; } } } return flag;}
二叉树的层次遍历算法
二叉树的层次遍历算法有如下三种方法：
给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：
对此二叉树遍历的结果应该是：
1，
2 ， 3
4， 5， 6
7， 8
第一种方法，就是利用递归的方法，按层进行打印，我们把根节点当做第0层，之后层次依次增加，如果我们想打印第二层怎么办呢，利用递归的代码如下：
[cpp] view plaincopy
int print_at_level(Tree T, int level) {
if (!T || level 0)
return 0;
if (0 == level) {
cout T-data " ";
return 1;
}
return print_at_level(T-lchild, level - 1) + print_at_level(T-rchild, level - 1);
如果我们成功的打印了给定的层次，那么就返回非0的正值，如果失败返回0。有了这个思路，我们就可以应用一个循环，来打印这颗树的所有层的节点，但是有个问题就是我们不知道这棵二叉树的深度，怎么来控制循环使其结束呢，仔细看一下print_at_level，如果指定的Tree是空的，那么就直接返回0，当返回0的时候，我们就结束循环，说明没有节点可以打印了。
[cpp] view plaincopy
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout endl;
}
以上的方法可以很清楚的看出，存在重复访问的情况，就是第0层访问的次数最多，第1层次之。所以这个递归的方法不是很有效的方法。
第二种方法：我们可以设置两个队列，想象一下队列的特点，就是先进先出，首先把第0层保存在一个队列中，然后按节点访问，并把已经访问节点的左右孩子节点放在第二个队列中，当第一个队列中的所有节点都访问完成之后，交换两个节点。这样重复下去，知道所有层的节点都被访问，这样做的代价就是空间复杂度有点高。
[cpp] view plaincopy
void print_by_level_2(Tree T) {
dequetree_node_t* q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout temp-data " ";
if (temp-lchild)
q_second.push_back(temp-lchild);
if (temp-rchild)
q_second.push_back(temp-rchild);
}
cout endl;
q_first.swap(q_second);
}
}
第三种方法就是设置双指针，一个指向访问当层开始的节点，一个指向访问当层结束节点的下一个位置：
这是第一层访问的情况，当访问第0层之后的结构如下，把第0层的所有子节点加入之后：
访问完第1层之后：
之后大家就可以自己画图了，下面给出程序代码：
[cpp] view plaincopy
void print_by_level_3(Tree T) {
vectortree_node_t* vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur vec.size()) {
end = vec.size();
while (cur end) {
cout vec[cur]-data " ";
if (vec[cur]-lchild)
vec.push_back(vec[cur]-lchild);
if (vec[cur]-rchild)
vec.push_back(vec[cur]-rchild);
cur++;
}
cout endl;
}
}
最后给出完成代码的测试用例：124##57##8##3#6##
[cpp] view plaincopy
#includeiostream
#includevector
#includedeque
using namespace std;
typedef struct tree_node_s {
char data;
struct tree_node_s *lchild;
struct tree_node_s *rchild;
}tree_node_t, *Tree;
void create_tree(Tree *T) {
char c = getchar();
if (c == '#') {
*T = NULL;
} else {
*T = (tree_node_t*)malloc(sizeof(tree_node_t));
(*T)-data = c;
create_tree((*T)-lchild);
create_tree((*T)-rchild);
}
}
void print_tree(Tree T) {
if (T) {
cout T-data " ";
print_tree(T-lchild);
print_tree(T-rchild);
}
}
int print_at_level(Tree T, int level) {
if (!T || level 0)
return 0;
if (0 == level) {
cout T-data " ";
return 1;
}
return print_at_level(T-lchild, level - 1) + print_at_level(T-rchild, level - 1);
}
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout endl;
}
void print_by_level_2(Tree T) {
dequetree_node_t* q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout temp-data " ";
if (temp-lchild)
q_second.push_back(temp-lchild);
if (temp-rchild)
q_second.push_back(temp-rchild);
}
cout endl;
q_first.swap(q_second);
}
}
void print_by_level_3(Tree T) {
vectortree_node_t* vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur vec.size()) {
end = vec.size();
while (cur end) {
cout vec[cur]-data " ";
if (vec[cur]-lchild)
vec.push_back(vec[cur]-lchild);
if (vec[cur]-rchild)
vec.push_back(vec[cur]-rchild);
cur++;
}
cout endl;
}
}
int main(int argc, char *argv[]) {
Tree T = NULL;
create_tree(T);
print_tree(T);
cout endl;
print_by_level_3(T);
cin.get();
cin.get();
return 0;
}
