这篇blog 前面是基础实验，后面二叉树详解，由红色字体加粗显示
包括各种遍历（递归与非递归）
以及已知两种序列求第三种序列
头文件
/********************************/
/*** 建立头文件bintree.h **/
/*******************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100
extern char *a; /*存放扩充二叉树的前序序列*/
typedef struct node /*二叉树结构定义*/
{
char data;
struct node *lchild,*rchild;
}binnode;
typedef binnode *bintree;
/*根据扩充二叉树的前序序列(字符串a)建立二叉树t的存储结构*/
bintree creatbintree()
{
char ch=*a++;
bintree t;
if(ch=='#')
t=NULL;
else
{
t=(bintree)malloc(sizeof(binnode));
t->data=ch;
t->lchild=creatbintree();
t->rchild=creatbintree();
}
return t;
}
void preorder(bintree t) /*前序递归遍历二叉树*/
{
if(t)
{
printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
void postorder(bintree t) /*后序递归遍历二叉树*/
{
if(t)
{
postorder(t->lchild);
postorder(t->rchild);
printf("%c",t->data);
}
}
/*顺序栈定义*/
typedef struct
{
bintree data[N];
int top;
}seqstack;
void init(seqstack *s) /*初始化空栈*/
{
s->top=-1;
}
int empty(seqstack *s) /*判断栈是否为空*/
{
if(s->top!=-1)
return 0;
else
return 1;
}
int full(seqstack *s) /*判断栈是否为满*/
{
if(s->top==N-1)
return 1;
else
return 0;
}
void push(seqstack *s,bintree x) /*进栈*/
{
if(!full(s))
s->data[++s->top]=x;
}
bintree pop(seqstack *s)/*出栈*/
{
if(!empty(s))
return s->data[s->top--];
}
/*
实现二叉树t的非递归前序遍历
*/
#include"bintree.h"
char *a="ABC##D#E##F##"; /*扩充二叉树序树t的前序序列*/
void preorder1(bintree t)
{
seqstack BiTree;
init(&BiTree);
bintree p=t;
while(p||!empty(&BiTree))
{
while(p)
{
push(&BiTree,p);
printf("%c ",p->data);
p=p->lchild;
}
p=pop(&BiTree);
p=p->rchild;
}
}
int main()
{
bintree t;
t=creatbintree(); /*建立二叉树t的存储结构*/
printf("二叉树的前序序列为：\n");
preorder1(t); /*前序非递归遍历二叉树*/
return 0;
}
层次遍历递归算法
/*
实现二叉树的层次遍历
*/
#include"bintree.h"
char *a="ABC##D#E##F##"; /*扩充二叉树序树t的前序序列*/
void levelbintree(bintree t,int level)
{
if(!t||level<0)
return ;
if(level==1){
printf("%c ",t->data);
return;
}
levelbintree(t->lchild,level-1);
levelbintree(t->rchild,level-1);
}
int main()
{
bintree t;
t=creatbintree(); /*建立二叉树t的存储结构*/
printf("二叉树的层次序列为：\n");
for(int i=1;i<=4;i++){
levelbintree(t,i); /*层次遍历二叉树*/
puts("");
}
return 0;
}
分别返回二叉树t在前序遍历的最后一个结点地址和后序遍历下的第一个结点地址
/*
分别返回二叉树t在前序遍历的最后一个结点地址
和后序遍历下的第一个结点地址
*/
#include"bintree.h"
char *a="ABC##D##EF#G###"; /*扩充二叉树序树t的前序序列*/
bintree prelast(bintree t)
{
seqstack BiTree;
init(&BiTree);
bintree p=t;
bintree ans;
while(p||!empty(&BiTree))
{
while(p)
{
push(&BiTree,p);
ans=p;
p=p->lchild;
}
p=pop(&BiTree);
p=p->rchild;
}
return ans;
}
bintree postfirst(bintree t)
{
bintree p=t;
bintree ans;
while(p)
{
ans=p;
p=p->lchild;
}
return ans;
}
int main()
{
bintree t,p,q;
t=creatbintree(); /*建立二叉树t的存储结构*/
p=prelast(t);
q=postfirst(t);
if(t!=NULL)
{
printf("前序遍历最后一个结点为：%c\n",p->data);
printf("后序遍历第一个结点为：%c\n",q->data);
}
else
printf("二叉树为空！");
return 0;
}
求某节点在二叉树中的层次
/*
二叉树采用链式方式存储，t为其根结点，求x的结点在二叉树中的层次
*/
#include"bintree.h"
char *a="ABC##D##EF#G###"; /*扩充二叉树序树t的前序序列*/
int visit[100];
int Depth(bintree t,char x)
{
seqstack seq;
init(&seq);
bintree p=t;
int ans=1;
while(p||!empty(&seq))
{
while(p)
{
visit[p->data-'A']=ans;
if(p->data==x)
return visit[p->data-'A'];
push(&seq,p);
p=p->lchild;
ans++;
}
p=pop(&seq);
ans=visit[p->data-'A'];
p=p->rchild;
if(p)
ans++;
}
return ans;
}
int main()
{
int k;
char x;
bintree root;
root=creatbintree();
printf("请输入树中的1个结点值:\n");
scanf("%c",&x);
printf("%c结点的层次为%d\n",x,Depth(root,x));
return 0;
}
将一棵给定二叉树中所有结点的左、右子女互换
/*
将一棵给定二叉树中所有结点的左、右子女互换
*/
#include"bintree.h"
char *a="ABC##D##EF#G###"; /*扩充二叉树序树t的前序序列*/
void change(bintree t)
{
bintree p=t;
seqstack seq;
init(&seq);
while(p||!empty(&seq))
{
while(p)
{
bintree temp=p->lchild;
p->lchild=p->rchild;
p->rchild=temp;
push(&seq,p);
p=p->lchild;
}
p=pop(&seq);
p=p->rchild;
}
}
int main()
{
bintree root;
root=creatbintree();
change(root);
preorder(root);
}
根据前序和中序求后序
（见本blog尾，有对此的解析）
/*
根据二叉树的前序序列pre、中序序列mid和序列长度length
构造二叉树的二叉链表存储结构
*/
#include"bintree.h"
#include<string.h>
char *a="";
char pre[100],mid[100];
/*
* i: 子树的前序序列字符串的首字符在pre[]中的下标
* j: 子树的中序序列字符串的首字符在mid[]中的下标
* len: 子树的字符串序列的长度
*/
void PreMidCreateTree(bintree &pn,int i,int j,int len)
{
if(len<=0){
pn=NULL;
return;
}
pn=(bintree)malloc(sizeof(binnode));
pn->data=pre[i];
int temp=strchr(mid,pre[i])-mid;///字符第一次出现在mid中的位置
PreMidCreateTree(pn->lchild,i+1,j,temp-j); ///temp-j为左子树字符串长度
PreMidCreateTree(pn->rchild,i+(temp-j)+1,temp+1,len-1-(temp-j)); ///len-1-(temp-j)为右子树字符串长度
}
int main()
{
freopen("in.txt","r",stdin);
puts("请输入前序序列:");
gets(pre);
puts("请输入中序序列:");
gets(mid);
bintree root;
PreMidCreateTree(root,0,0,strlen(pre));
puts("后序序列是:");
postorder(root);
}
二叉树详解：
下面部分借鉴别人而总结出比较好理解，个人觉得比较好运用的代码
遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
例如：求下面树的三种遍历
前序遍历：abdefgc
中序遍历：debgfac
后序遍历：edgfbca
储存结构：
顺序存储：
typedef char datatype;
typedef struct node{
datatype data;
int lchild,rchild;
int parent;
}Node;
链式存储：
typedef char datatype;
typedef struct BinNode{
datatype data;
struct BinNode* lchild;
struct BinNode* rchild;
}BinNode;
typedef BinNode* bintree; //bintree本身是个指向结点的指针
遍历：
递归遍历：
前序遍历
void PreOrder(BiTree T){
if(T){
//访问父亲
printf("%c",T->data);
//访问左子儿子
PreOrder(T->lchild);
//访问右儿子
PreOrder(T->rchild);
}
}
中序遍历
void InOrder(BiTree T){
if(T){
//访问左子结点
InOrder(T->lchild);
//访问父亲
printf("%c",T->data);
//访问友儿子
InOrder(T->rchild);
}
}
后序遍历
void PostOrder(BiTree T){
if(T){
//访问左儿子
PostOrder(T->lchild);
//访问右儿子
PostOrder(T->rchild);
//访问父亲
printf("%c",T->data);
}
}
非递归遍历：
前序遍历
思路：
访问T->data后，将T入栈
遍历左子树；
遍历完左子树返回时，栈顶元素应为T，
出栈，再先序遍历T的右子树
void PreOrder2(BiTree T){
stack<BiTree>stack;
BiTree p=T;
while(p||!stack.empty()){
while(p)
stack.push(p);
printf("%c ",p->data);
p=p->lchild;
}
p=stack.top();
stack.pop();
p=p->rchild;
}
}
思路：
中序遍历要求在遍历完左子树后
访问根，再遍历右子树
先将T入栈，遍历左子树；
遍历完左子树返回时，栈顶元素应为T，出栈，
访问T->data，再中序遍历T的右子树中序遍历
void InOrder2(BiTree T){
stack<BiTree> stack;
BiTree p=T;
while(p||!stack.empty()){
while(p){
stack.push(p);
p = p->lchild;
}
p=stack.top();
printf("%c ",p->data)
stack.pop();
p=p->rchild;
}
}
后序遍历
对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶
void postorder_dev(bintree t){
seqstack s;
s.top = -1;
if(!t){
printf("the tree is empty!\n");
}else{
while(t || s.top != -1){ //栈空了的同时t也为空。
while(t){
push(&s,t);
s.tag[s.top] = 0; //设置访问标记，0为第一次访问，1为第二次访问
t= t->lchild;
}
if(s.tag[s.top] == 0){ //第一次访问时，转向同层右结点
t= s.data[s.top]; //左走到底时t是为空的，必须有这步！
s.tag[s.top]=1;
t=t->rchild;
}else {
while (s.tag[s.top] == 1){ //找到栈中下一个第一次访问的结点，退出循环时并没有pop所以为其左子结点
t = pop(&s);
printf("%c ",t->data);
}
t = NULL; //必须将t置空。跳过向左走，直接向右走
}
}
}
}
另外有一个详细的版本
typedef struct
{
Node * p;
int rvisited;
}SNode； //Node 是二叉树的结点结构，rvisited==1代表p所指向的结点的右结点已被访问过。
lastOrderTraverse(BiTree bt){
//首先，从根节点开始，往左下方走，一直走到头，将路径上的每一个结点入栈。
p = bt;
while(bt){
push(bt, 0); //push到栈中两个信息，一是结点指针，一是其右结点是否被访问过
bt = bt.lchild;
}
//然后进入循环体
while(!Stack.empty()){ //只要栈非空
sn = Stack.getTop(); // sn是栈顶结点
//注意，任意一个结点N，只要他有左孩子，则在N入栈之后，N的左孩子必然也跟着入栈了(这个体现在算法的后半部分)，所以当我们拿到栈顶元素的时候，可以确信这个元素要么没有左孩子，要么其左孩子已经被访问过，所以此时我们就不关心它的左孩子了，我们只关心其右孩子。
//若其右孩子已经被访问过，或是该元素没有右孩子，则由后序遍历的定义，此时可以visit这个结点了。
if(!sn.p.rchild || sn.rvisited){
p = pop();
visit(p);
}
else //若它的右孩子存在且rvisited为0，说明以前还没有动过它的右孩子，于是就去处理一下其右孩子。
{
//此时我们要从其右孩子结点开始一直往左下方走，直至走到尽头，将这条路径上的所有结点都入栈。
//当然，入栈之前要先将该结点的rvisited设成1，因为其右孩子的入栈意味着它的右孩子必将先于它被访问(这很好理解，因为我们总是从栈顶取出元素来进行visit)。由此可知，下一次该元素再处于栈顶时，其右孩子必然已被visit过了，所以此处可以将rvisited设置为1。
sn.rvisited = 1;
//往左下方走到尽头，将路径上所有元素入栈
p = sn.p.rchild;
while(p != 0){
push(p, 0);
p = p.lchild;
}
}//这一轮循环已结束，刚刚入栈的那些结点我们不必管它了，下一轮循环会将这些结点照顾的很好。
}
}
已知两种序列求解第三种序列
注意：
已知先序和后序，不能求得中序，故不讨论
（一）：已知二叉树中序序列和后序序列，求先序序列
例：（白书P386第13题）二叉树中序序列为abcdefg,后序序列为bdcafge，求先序序列
1.找根结点：
后序序列顺序为左右头，它最后一个定为根结点，根结点就为后序序列的最后一个------e；
2.分左右孩子：
e为根结点，根据中序序列是左头右推出abcd是根结点的左孩子，fg为右孩子；
3.排左孩子：
中序序列为abcd，后序序列为bdca（递归到第一步）
（1）：找分支结点：
后序序列最后一个为分支结点，分支结点为a；
（2）：分左右孩子：
a为分支结点，根据中序序列是左头右推出没有左孩子，bcd为右孩子；
（3）：排左孩子：
无；
（4）：排右孩子：
（此处省略过程，还是递归）排序为b是c的左孩子，d是c的右孩子，c是a的右孩子；
4.排右孩子：
中序序列为fg，后序序列为fg（也是递归）
（1）：找分支结点：
后序序列最后一个为分支结点，分支结点为g；
（2）：分左右孩子：
g为分支节点，根据中序序列是左头右推出
f为左孩子，无右孩子；
（3）：排左孩子：
f为g的左孩子；
（4）：排右孩子：
无；
5.画二叉树：
e
/ \
a g
\ /
c f
/ \
b d
6.写先序序列：为eacbdgf。
（二）：已知二叉树先序序列和中序序列，求后序序列
例：（白书P386第18题）二叉树先序序列为EFHIGJK，中序序列为HFIEJKG，求后序序列
1.找根结点：
先序序列顺序为头左右，它第一个定为根结点，根结点就为先序序列的第一个------E；
2.分左右孩子：
E为根结点，根据中序序列是左头右推出HFI是根结点的左孩子，JKG为右孩子；
3.排左孩子：
中序序列为HFI，先序序列为FHI（递归到第一步）
（1）：找分支结点：
先序序列第一个为分支结点，分支结点为F；
（2）：分左右孩子：
F为分支结点，根据中序序列是左头右推出H为左孩子，I为右孩子；
（3）：排左孩子：
H是F的左孩子；
（4）：排右孩子：
I是F的右孩子；
4.排右孩子：
中序序列为JKG，先序序列为GJK（也是递归）
（1）：找分支结点：
先序序列第一个为分支结点，分支结点为G；
（2）：分左右孩子：
G为分支节点，根据中序序列是左头右推出
JK为左孩子，无右孩子；
（3）：排左孩子：
（此处省略过程，还是递归）K是J的右孩子，J是G的左孩子；
（4）：排右孩子：
无；
5.画二叉树：
E
/ \
F G
/ \ /
H I J
\
K
6.写后序序列：为HIFKJGE。
前序 ABDGHCEFI
中序 GDHBAECIF
后序 GHDBEIFCA
学习这个查找函数：
int temp=strchr(mid,pre[i])-mid;///字符第一次出现在mid中的位置
/*
根据二叉树的前序序列(或者后序)、中序序列和序列长度length
求后序或者前序的二叉树
注：不能由前序和后序得到中序序列
*/
#include"bintree.h"
#include<string.h>
char *a="";
char pre[100],mid[100],post[100];
/*
* i: 子树的前序序列字符串的首字符在pre[]中的下标
* j: 子树的中序序列字符串的首字符在mid[]中的下标
* len: 子树的字符串序列的长度
*/
void PreMidCreateTree(bintree &pn,int i,int j,int len)
{
if(len<=0){
pn=NULL;
return;
}
pn=(bintree)malloc(sizeof(binnode));
pn->data=pre[i];
int temp=strchr(mid,pre[i])-mid;///字符第一次出现在mid中的位置
PreMidCreateTree(pn->lchild,i+1,j,temp-j); ///temp-j为左子树字符串长度
PreMidCreateTree(pn->rchild,i+(temp-j)+1,temp+1,len-1-(temp-j)); ///len-1-(temp-j)为右子树字符串长度
}
/* 利用后序中序序列创建树
* i: 子树的后序序列字符串的尾字符在post[]中的下标
* j: 子树的中序序列字符串的首字符在mid[]中的下标
* len: 子树的字符串序列的长度
*/
void PostMidCreateTree(bintree &pn,int i,int j,int len)
{
if(len<=0){
pn=NULL;
return;
}
pn=(bintree)malloc(sizeof(binnode));
pn->data=post[i];
int m=strchr(mid,post[i])-mid;
PostMidCreateTree(pn->lchild,i-1-(len-1-(m-j)),j,m-j);
PostMidCreateTree(pn->rchild,i-1,m+1,len-1-(m-j));
}
int main()
{
freopen("in.txt","r",stdin);
puts("请输入前序序列:");
gets(pre);
puts("请输入中序序列:");
gets(mid);
puts("请输入后序序列:");
gets(post);
puts("**********华丽的分割线*********");
bintree root1;
PreMidCreateTree(root1,0,0,strlen(pre));
puts("后序序列是:");
postorder(root1);
puts("");
puts("**********华丽的分割线*********");
bintree root2;
PreMidCreateTree(root2,0,0,strlen(post));
puts("前序序列是:");
preorder(root2);
puts("");
}