中序遍历c算法
1. c语言 关于二叉树的创建和遍历(中序遍历)
这个还是我学《数据结构》时做的有关二叉树的练习呢，本来是全的，包括树的初始化，建立，遍历（中序、前序、后序和层次），还有输出，复制，删除节点，求深度，树的删除等等，看你只问了有关创建和中序遍历的，所以选了一部分给你，供你参考吧！
#include <stdio.h>
#include <malloc.h>
#define MaxSize 10
#define Number 30
struct BiTNode{//定义数据结构
char data;
BiTNode *lchild,*rchild;
};
void InitBtree(BiTNode * &BT){//初始化二叉树
BT=NULL;
}
void CreateBiTree(BiTNode *&BT,char *str){//建立二叉树
BiTNode *s[MaxSize];//这里定义了一个数组用作堆栈方便检查输入和操作
int top=-1;
BT=NULL;
BiTNode *p=NULL;
int k, j=0;
char ch;
ch=str[j];
while(ch!='\0'){
switch(ch){
case '(':
top++;
s[top]=p;
k=1;
break;
case ')':
top--;
break;
case ',':
k=2;
break;
default:
p=(struct BiTNode *) malloc(sizeof(struct BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(BT==NULL)
BT=p;
else{
if(k==1)
s[top]->lchild=p;
else
s[top]->rchild=p;
}
}
j++;
ch=str[j];
}
}
void inorder(BiTNode *BT){//中序遍历二叉树——递归形式
if(BT!=NULL){
inorder(BT->lchild );
printf("%c ",BT->data);
inorder(BT->rchild );
}
}
void main(){
BiTNode *BT;
printf("以广义表形式表示输入的二叉数 （如A(B(C,D),E(,F))的形式）\n\n");
char string[Number]="A(B(,C),D(E(F),G(,H)))";
//如果想要自己输入，可以将下边的注释去掉，然后自己按照广义表形式输入，
//（如上例的形式）此处为了方便查看，用了默认的数值
//这里之所以用此种形式（广义表形式输入）是为了保证输入的数组成的二叉树完全符合你所定义的树的形状
/*char string[Number],ch;
int i=0;
ch=getchar();
while(ch!='\n' && i<Number){
string[i]=ch;
i++;
ch=getchar();
}
string[i]='\0';
*/
InitBtree(BT);//初始化二叉树
CreateBiTree(BT,string);//创建二叉树
printf("\n中序遍历二叉树顺序为： ");
inorder(BT);//中序遍历二叉树
printf("\n");
}
程序不复杂，所以只是加了必要和最简单的注释，相信你看看应该完全可以理解的，祝你进步！
2. 二叉树中序遍历非递归算法(c语言实现）
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define null 0
struct node
{
char data;
struct node *lchild;
struct node *rchild;
};
//先序，中序 建树
struct node *create(char *pre,char *ord,int n)
{
struct node * head;
int ordsit;
head=null;
if(n<=0)
{
return null;
}
else
{
head=(struct node *)malloc(sizeof(struct node));
head->data=*pre;
head->lchild=head->rchild=null;
ordsit=0;
while(ord[ordsit]!=*pre)
{
ordsit++;
}
head->lchild=create(pre+1,ord,ordsit);
head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);
return head;
}
}
//中序递归遍历
void inorder(struct node *head)
{
if(!head)
return;
else
{
inorder(head->lchild );
printf("%c",head->data );
inorder(head->rchild );
}
}
//中序非递归遍历
void inorder1(struct node *head)
{
struct node *p;
struct node *stack[20];
int top=0;
p=head;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p->lchild ;
}
p=stack[--top];
printf("%c ",p->data );
p=p->rchild ;
}
}
//主函数
int main()
{
struct node * head;
char pre[30],ord[30];
int n;
gets(pre);
gets(ord);
n=strlen(pre);
head=create(pre,ord,n);
inorder(head);
printf("\n");
inorder1(head);
printf("\n");
}
//测试事例；
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/
几个月前自己编写，原版
vc++ 6.0实验通过
怎么样，老板，第一次上网络知道，好激动
给点面子
给分！给分啊
3. 关于c语言中二叉树前，中，后序遍历，没看懂，请问该如何理解比如中序遍历:左，根，右。那么拿到一个
以你的图为准，不管是先序遍历，中序遍历，还是后序遍历，都以根为主，也就是你看根就可以了。就那中序遍历来说，按规则来，顺序是左根右，根就是F，对于根的左就是F左边的一大堆，右就是F右边的那一堆，就可以写成 （）F（），对左来说，根就是C，C的左右和上边的确定方法一样，对右来说，根就是E，E的有是有的，但E的左是空，写成（（）C（））F（E（）），这样依次写下来就是ACBDFEG。当然写的时候不需要写括号，只是为了说明方便，先序遍历和后序遍历一样。
4. c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法
#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.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
}
5. C语言中，到底先序遍历、中序遍历、后续遍历怎么看的...真的快疯掉了！求高人指点指点...泪目
先序遍历就是“根左右”，不管你现在在哪个节点，都是按这种规则。上面的题目：根是A，左是B，右是C，所以是A-》B，在当前根节点B，还是按上述规则，那么接下来到D，D之后没有子节点，返回B，遍历E-》X，X之后没有子节点，返回E，E的子节点都遍历完了，返回B，B的子节点都遍历完了，返回A，接下来遍历右子树，规则同上。
中序遍历就是“左根右”，对于A来说，先遍历B，对于B来说，先遍历D，对于D来说，已经没有左子树，所以遍历D，D没有右子树,返回B，遍历B，B有右子树E，对于E来说，先遍历X，完了返回E，E完了返回B，B完了返回A，遍历A，遍历右子树，规则同上。
后序遍历就是跟先序遍历相反的，先遍历右子树，再左子树，最后才是根。
好好思考一下。
6. 二叉树编程 先序建立 中序遍历
理论分析
数据结构的基础知识中重要的一点就是能否根据两种不同遍历序列的组合（有三种：先序+中序，先序+后序，中序+后序），唯一的确定一棵二叉树。然后就是根据二叉树的不同遍历序列（先序、中序、后序），重构二叉树。显然，这三种组合并不是都能唯一确定二叉树的，其中先序+后序就不能唯一确定一棵二叉树，下面是关于该问题的证明与结论。
①给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。
证明：因为先序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（假设有L个元素）表示左子树，若左边无元素，则说明左子树为空；右边（假设有R个元素）是右子树，若为空，则右子树为空。根据前序遍历中"根-左子树-右子树"的顺序，则由从先序序列的第二元素开始的L个结点序列和中序序列根左边的L个结点序列构造左子树，由先序序列最后R个元素序列与中序序列根右边的R个元素序列构造右子树。
②由中序序列和先序序列能唯一确定一棵二叉树，但是由先序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。
反例：任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。
这两棵二叉树的先序遍历序列都为2-1-3，后序遍历序列都为3-1-2。但是显然它们是不同的二叉树，所以根据先序序列和后序序列并不能唯一确定二叉树。
③已经说明由二叉树的先序序列和中序序列可以确定一棵二叉树，现在来证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
证明：
当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。
设当n=m-1时结论成立，即结点数目为m-1时，中序序列和后序序列可以唯一确定二叉树。现证明当n=m时结论成立。
设中序序列为S1,S2,…,Sm,后序序列是P1,P2,…,Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1,S2,…,Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。
若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2,S3,…,Sm}和{P1,P2,…,Pm-1}可以唯一确定右子树，从而也确定了二叉树。
若i=m，则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1,S2,…,Sm-1}和{P1,P2,…,Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当1<i<m时，Si把中序序列分成{S1,S2,…,Si-1}和{Si+1,Si+2,…,Sm}。由于后序遍历是"左子树-右子树-根结点"，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1,S2,…,Si-1}和{P1,P2,…,Pi-1}可唯一确定二叉树的左子树，由{Si+1,Si+2,…,Sm}和{Pi,Pi+1,…,Pm-1}可唯一确定二叉树的右子树。
3、构造思路
1）根据先序遍历序列和中序遍历序列构建二叉树
假定已知二叉树如下：
___7___
/ \
10 2
/ \ /
4 3 8
\ /
1 11
那么它的先序遍历和中序遍历的结果如下：
preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}
需要关注的几个要点：
1）先序遍历的第一个结点总是根结点。如上图中的二叉树，根结点为7，也是先序遍历的第一个值。先序遍历时父亲结点总是在孩子结点之前遍历。
2）可以观察到在中序遍历中，7是第4个值（从0开始算起）。由于中序遍历顺序为：左子树，根结点，右子树。所以7左边的{4,10,3,1} 这四个结点属于左子树，而根结点7右边的{11,8,2}属于右子树。
3）可以从上面的结论很轻松的得到递归式。在构建了根结点7后，我们可以根据中序遍历{4, 10, 3, 1} 和{11,8,2}分别构建它的左子树和右子树。我们同时需要相应的先序遍历结果用于发现规律。我们可以由先序遍历知道左右子树的先序遍历分别是{10，4, 3, 1}和{2， 8， 11}。左右子树也分别为二叉树，由此可以递归来解决问题。
4）关于如何得到根结点在中序遍历中的位置问题还没有细讲，如果使用线性扫描查找位置，则每次查找需要O（N）的时间，如果二叉树平衡的话，则整个算法需要O（NlgN）的时间。如果二叉树不平衡，则最坏情况需要O（N^2）时间。为了提高效率，我们可以考虑使用哈希表来存储与查找根结点在中序遍历中的位置，每次查找只需要O（1）的时间，这样构建整棵树只需要O（N）的时间。 这里为了方便，只是用了一个数组用于标记位置，要是用哈希表也会很方便。需要注意的是，这里的二叉树结点值不能有相同的值。
代码：
// 输入：先序和中序的第一个指针和最后一个指针，
// 递归调用，每次确定当前结点
BinaryTreeNode* ConstructCore(int* startPerorder, int* endPreorder, int* startInorder, int* endInorder)
{
//先序第一个为根节点
int rootValue = startPerorder[0];
BinaryTreeNode* root = new BinaryTreeNode;
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = NULL;
//递归退出条件
if ( startPerorder==endPreorder )
{
if ( startInorder==endInorder && *startPerorder==*endInorder )
return root;
else
throw std::exception("Invalid input."); //异常处理
}
// 在中序遍历中找到根节点的值
int* rootInorder = startInorder;
while(rootInorder<=endInorder && *rootInorder!=rootValue)
++rootInorder;
//异常处理
if ( rootInorder==endInorder && *rootInorder!=rootValue)
throw std::exception("Invalid input.");
int leftLength = rootInorder - startInorder;
int* leftPreorderEnd = startPerorder+leftLength;
if ( leftLength > 0 )
{
//构建左子树
root->m_pLeft=ConstructCore(startPerorder+1,leftPreorderEnd,startInorder, rootInorder-1);
}
if ( leftLength < endPreorder-startPerorder )
{
//构建右子树
root->m_pRight= ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder);
}
return root;
}
//根据先序和中序构建二叉树
BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
{
if(preorder==NULL || inorder==NULL || length <=0)
return NULL;
return ConstructCore(preorder, preorder+length-1, inorder,inorder+length-1);
}
void TraverseTreePostorder(BinaryTreeNode* proot)
{
if ( proot == NULL )
return;
if ( proot->m_pLeft != NULL )
TraverseTreePostorder(proot->m_pLeft);
if ( proot->m_pRight != NULL )
TraverseTreePostorder(proot->m_pRight);
cout << proot->m_nValue << " ";
}
主函数测试代码：
int main()
{
int preorder[] = {7,10,4,3,1,2,8,11};
int inorder[] = {4,10,3,1,7,11,8,2};
BinaryTreeNode* pRoot = Construct(preorder,inorder,8);
TraverseTreePostorder(pRoot);
cout <<endl;
return 0;
}
2）根据中序遍历序列和后序序遍历序列构建二叉树
原理和上述原理基本一致，任然沿用上述例子
___7___
/ \
10 2
/ \ /
4 3 8
\ /
1 11
那么它的中序遍历和后序序遍历的结果如下：
inorder = {4,10,3,1,7,11,8,2}
postorder = {7,10,4,3,1,2,8,11}
代码：
// 输入：中序和后序的第一个指针和最后一个指针，
// 递归调用，每次确定当前结点
BinaryTreeNode* ConstructCore_in_post(int* startInorder, int* endInorder, int* startPostorder, int* endPostorder)
{
//后序最后一个结点为根结点
int rootValue = *endPostorder;
BinaryTreeNode* root = new BinaryTreeNode;
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = NULL;
//递归退出条件
if ( startInorder==endInorder )
{
if ( startPostorder==endPostorder && *startInorder==*endPostorder )
return root;
else
throw std::exception("Invalid input."); //异常处理
}
//在中序中找到当前根节点
int* rootInorder = startInorder;
while(rootInorder<=endInorder && *rootInorder != rootValue )
++rootInorder;
int leftLength = rootInorder - startInorder;
int* leftInorderEnd = startInorder+leftLength-1;
if ( leftLength > 0 )
{
//构建左子树
root->m_pLeft=ConstructCore_in_post(startInorder,leftInorderEnd,startPostorder, startPostorder+leftLength-1);
}
if ( leftLength < endInorder-startInorder )
{
//构建右子树
root->m_pRight= ConstructCore_in_post(rootInorder+1,endInorder,startPostorder+leftLength,endPostorder-1);
}
return root;
}
//根据先序和中序构建二叉树
BinaryTreeNode* Construct(int* inorder, int* postorder, int length)
{
if(inorder==NULL || postorder==NULL || length <=0)
return NULL;
return ConstructCore_in_post(inorder, inorder+length-1, postorder, postorder+length-1);
}
void TraverseTreePreorder(BinaryTreeNode* proot)
{
if ( proot == NULL )
return;
cout << proot->m_nValue << " ";
if ( proot->m_pLeft != NULL )
TraverseTreePreorder(proot->m_pLeft);
if ( proot->m_pRight != NULL )
TraverseTreePreorder(proot->m_pRight);
}
主函数测试：
int main()
{
int inorder[] = {4,10,3,1,7,11,8,2};
int postorder[] = {4,1,3,10,11,8,2,7};
BinaryTreeNode* pRoot = Construct(inorder,postorder,8);
TraverseTreePreorder(pRoot);
cout <<endl;
return 0;
}
7. 用c或c++实现遍历二叉树的中序算法，急求
#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;
void CreateBTNode(BTNode *&b,char *str)
{
BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case'(':top++;St[top]=p;k=1;break;
case')':top--;break;
case',':k=2;break;
default:p=p=(BTNode * )malloc(sizeof(BTNode));
p->data=ch;p->lchild=p->rchild=NULL;
if(b==NULL)
b=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
void DispBTNode(BTNode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
DispBTNode(b->lchild);
if(b->rchild!=NULL)
printf(",");
DispBTNode(b->rchild);
printf(")");
}
}
}
extern void CreateBTNode(BTNode *&b,char *str);
extern void DispBTNode(BTNode *b);
void PreOrder(BTNode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}
void PreOrder1(BTNode *b)
{
BTNode *St[MaxSize],*p;
int top=-1;
if(b!=NULL)
{
top++;
St[top]=b;
while(top>-1)
{
p=St[top];
top--;
printf("%c",p->data);
if(p->rchild!=NULL)
{
top++;
St[top]=p->rchild;
}
if(p->lchild!=NULL)
{
top++;
St[top]=p->lchild;
}
}
printf("\n");
}
}
void InOrder(BTNode *b)
{
if(b!=NULL)
{
InOrder(b->lchild);
printf("%c",b->data);
InOrder(b->rchild);
}
}
void InOrder1(BTNode *b)
{
BTNode *St[MaxSize],*p;
int top=-1;
if(b!=NULL)
{
p=b;
while(top>-1||p!=NULL)
{
while(p!=NULL)
{
top++;
St[top]=p;
p=p->lchild;
}
if(top>-1)
{
p=St[top];
top--;
printf("%c",p->data);
p=p->rchild;
}
}
printf("\n");
}
}
void PostOrder(BTNode *b)
{
if(b!=NULL)
{
PostOrder(b->lchild);
PostOrder(b->rchild);
printf("%c",b->data);
}
}
void PostOrder1(BTNode *b)
{
BTNode *St[MaxSize];
BTNode *p;
int flag,top=-1;
if(b!=NULL)
{
do
{
while(b!=NULL)
{
top++;
St[top]=b;
b=b->lchild;
}
p=NULL;
flag=1;
while(top!=-1&&flag)
{
b=St[top];
if(b->rchild==p)
{
printf("%c",b->data);
top--;
p=b;
}
else
{
b=b->rchild;
flag=0;
}
}
}
while(top!=-1);
printf("\n");
}
}
void TravLevel(BTNode *b)
{
BTNode *Qu[MaxSize];
int front,rear;
front=rear=0;
if(b!=NULL)
printf("%c",b->data);
rear++;
Qu[rear]=b;
while(rear!=front)
{
front=(front+1)%MaxSize;
b=Qu[front];
if(b->lchild!=NULL)
{
printf("%c",b->lchild->data);
rear=(rear+1)%MaxSize;
Qu[rear]=b->lchild;
}
if(b->rchild!=NULL)
{
printf("%c",b->rchild->data);
rear=(rear+1)%MaxSize;
Qu[rear]=b->rchild;
}
}
printf("\n");
}
void main()
{
BTNode *b;
CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("二叉树b:");DispBTNode(b);printf("\n\n");
printf("层次遍历序列:");
TravLevel(b);
printf("\n");
printf("先序遍历序列:\n");
printf("递归算法:");PreOrder(b);printf("\n");
printf("非递归算法:");PreOrder1(b);printf("\n");
printf("先序遍历序列:\n");
printf("递归算法:");InOrder(b);printf("\n");
printf("非递归算法:");InOrder1(b);printf("\n");
printf("后续遍历算法:\n");
printf("递归算法:");PostOrder(b);printf("\n");
printf("非递归算法:");PostOrder1(b);printf("\n");
}
8. 二叉树的建立、中序遍历（用C语言实现）
#include "iostream.h"
//#include "exception.h"
//树节点类
int count=0,mode=0,data=0;
class BinaryTreeNode
{
friend class BinaryTree;
public :
BinaryTreeNode()
{
LeftChild = RightChild = 0;
}
BinaryTreeNode(const int& e)
{
data = e;
LeftChild = RightChild = 0;
}
BinaryTreeNode(const int& e, BinaryTreeNode *l,BinaryTreeNode *r)
{
data = e;
LeftChild = l;
RightChild = r;
}
private :
int data;
BinaryTreeNode *LeftChild, //左子树
*RightChild; // 右子树
} ;
class BinaryTree
{
friend class BinaryTreeNode;
public :
BinaryTree( )
{
root = 0;
}
~ BinaryTree( ) { }
bool IsEmpty( ) const
{
return ((root) ? false : true);
}
bool Root(int& x) const
{// 取根节点的d a t a域，放入x
// 如果没有根节点，则返回f a l s e
if (root)
{
x = root->data;
return true;
}
else return false; // 没有根节点
}
void MakeTree(const int& element)
{
root = new BinaryTreeNode (element);
}
void MakeTree(const int& element,BinaryTree& left,BinaryTree& right)
{// 将left, right和element 合并成一棵新树
// left, right和this必须是不同的树
// 创建新树
root = new BinaryTreeNode (element, left.root, right.root);
// 阻止访问l e f t和r i g h t
left.root = right.root = 0;
}
void Inorder(void (*Visit) (BinaryTreeNode *u))
{
InOrder ( Visit,root ) ;
}
void Delete( )
{
PostOrder (Free,root);
root = 0;
}
private :
BinaryTreeNode *root; // 根节点指针
static void Free(BinaryTreeNode *t)
{
delete t;
}
void InOrder(void(*Visit) (BinaryTreeNode *u),BinaryTreeNode *t)
{// 中序遍历
if (t)
{
InOrder(Visit, t->LeftChild);
Visit( t ) ;
InOrder( Visit, t->RightChild);
}
}
9. c语言中序遍历怎么做
求采纳
10. C语言的二叉树中序遍历问题。
#include <stdio.h>
#include <stdlib.h>
#define STACK_MAX_SIZE 30
#define QUEUE_MAX_SIZE 30
#ifndef elemType
typedef char elemType;
#endif
/************************************************************************/
/* 以下是关于二叉树操作的11个简单算法 */
/************************************************************************/
struct BTreeNode{
elemType data;
struct BTreeNode *left;
struct BTreeNode *right;
};
/* 1.初始化二叉树 */
void initBTree(struct BTreeNode* *bt)
{
*bt = NULL;
return;
}
/* 2.建立二叉树(根据a所指向的二叉树广义表字符串建立) */
void createBTree(struct BTreeNode* *bt, char *a)
{
struct BTreeNode *p;
struct BTreeNode *s[STACK_MAX_SIZE];/* 定义s数组为存储根结点指针的栈使用 */
int top = -1; /* 定义top作为s栈的栈顶指针，初值为-1,表示空栈 */
int k; /* 用k作为处理结点的左子树和右子树，k = 1处理左子树，k = 2处理右子树 */
int i = 0; /* 用i扫描数组a中存储的二叉树广义表字符串，初值为0 */
*bt = NULL; /* 把树根指针置为空，即从空树开始建立二叉树 */
/* 每循环一次处理一个字符，直到扫描到字符串结束符\0为止 */
while(a[i] != '\0'){
switch(a[i]){
case ' ':
break; /* 对空格不作任何处理 */
case '(':
if(top == STACK_MAX_SIZE - 1){
printf("栈空间太小！\n");
exit(1);
}
top++;
s[top] = p;
k = 1;
break;
case ')':
if(top == -1){
printf("二叉树广义表字符串错误!\n");
exit(1);
}
top--;
break;
case ',':
k = 2;
break;
default:
p = malloc(sizeof(struct BTreeNode));
p->data = a[i];
p->left = p->right = NULL;
if(*bt == NULL){
*bt = p;
}else{
if( k == 1){
s[top]->left = p;
}else{
s[top]->right = p;
}
}
}
i++; /* 为扫描下一个字符修改i值 */
}
return;
}
/* 3.检查二叉树是否为空，为空则返回1,否则返回0 */
int emptyBTree(struct BTreeNode *bt)
{
if(bt == NULL){
return 1;
}else{
return 0;
}
}
/* 4.求二叉树深度 */
int BTreeDepth(struct BTreeNode *bt)
{
if(bt == NULL){
return 0; /* 对于空树，返回0结束递归 */
}else{
int dep1 = BTreeDepth(bt->left); /* 计算左子树的深度 */
int dep2 = BTreeDepth(bt->right); /* 计算右子树的深度 */
if(dep1 > dep2){
return dep1 + 1;
}else{
return dep2 + 1;
}
}
}
/* 5.从二叉树中查找值为x的结点，若存在则返回元素存储位置，否则返回空值 */
elemType *findBTree(struct BTreeNode *bt, elemType x)
{
if(bt == NULL){
return NULL;
}else{
if(bt->data == x){
return &(bt->data);
}else{ /* 分别向左右子树递归查找 */
elemType *p;
if(p = findBTree(bt->left, x)){
return p;
}
if(p = findBTree(bt->right, x)){
return p;
}
return NULL;
}
}
}
/* 6.输出二叉树(前序遍历) */
void printBTree(struct BTreeNode *bt)
{
/* 树为空时结束递归，否则执行如下操作 */
if(bt != NULL){
printf("%c", bt->data); /* 输出根结点的值 */
if(bt->left != NULL || bt->right != NULL){
printf("(");
printBTree(bt->left);
if(bt->right != NULL){
printf(",");
}
printBTree(bt->right);
printf(")");
}
}
return;
}
/* 7.清除二叉树，使之变为一棵空树 */
void clearBTree(struct BTreeNode* *bt)
{
if(*bt != NULL){
clearBTree(&((*bt)->left));
clearBTree(&((*bt)->right));
free(*bt);
*bt = NULL;
}
return;
}
/* 8.前序遍历 */
void preOrder(struct BTreeNode *bt)
{
if(bt != NULL){
printf("%c ", bt->data); /* 访问根结点 */
preOrder(bt->left); /* 前序遍历左子树 */
preOrder(bt->right); /* 前序遍历右子树 */
}
return;
}
/* 9.前序遍历 */
void inOrder(struct BTreeNode *bt)
{
if(bt != NULL){
inOrder(bt->left); /* 中序遍历左子树 */
printf("%c ", bt->data); /* 访问根结点 */
inOrder(bt->right); /* 中序遍历右子树 */
}
return;
}
/* 10.后序遍历 */
void postOrder(struct BTreeNode *bt)
{
if(bt != NULL){
postOrder(bt->left); /* 后序遍历左子树 */
postOrder(bt->right); /* 后序遍历右子树 */
printf("%c ", bt->data); /* 访问根结点 */
}
return;
}
/* 11.按层遍历 */
void levelOrder(struct BTreeNode *bt)
{
struct BTreeNode *p;
struct BTreeNode *q[QUEUE_MAX_SIZE];
int front = 0, rear = 0;
/* 将树根指针进队 */
if(bt != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = bt;
}
while(front != rear){ /* 队列非空 */
front = (front + 1) % QUEUE_MAX_SIZE; /* 使队首指针指向队首元素 */
p = q[front];
printf("%c ", p->data);
/* 若结点存在左孩子，则左孩子结点指针进队 */
if(p->left != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->left;
}
/* 若结点存在右孩子，则右孩子结点指针进队 */
if(p->right != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->right;
}
}
return;
}
/************************************************************************/
/*
int main(int argc, char *argv[])
{
struct BTreeNode *bt; /* 指向二叉树根结点的指针 */
char *b; /* 用于存入二叉树广义表的字符串 */
elemType x, *px;
initBTree(&bt);
printf("输入二叉树广义表的字符串：\n");
/* scanf("%s", b); */
b = "a(b(c), d(e(f, g), h(, i)))";
createBTree(&bt, b);
if(bt != NULL)
printf(" %c ", bt->data);
printf("以广义表的形式输出：\n");
printBTree(bt); /* 以广义表的形式输出二叉树 */
printf("\n");
printf("前序："); /* 前序遍历 */
preOrder(bt);
printf("\n");
printf("中序："); /* 中序遍历 */
inOrder(bt);
printf("\n");
printf("后序："); /* 后序遍历 */
postOrder(bt);
printf("\n");
printf("按层："); /* 按层遍历 */
levelOrder(bt);
printf("\n");
/* 从二叉树中查找一个元素结点 */
printf("输入一个待查找的字符：\n");
scanf(" %c", &x); /* 格式串中的空格跳过空白字符 */
px = findBTree(bt, x);
if(px){
printf("查找成功：%c\n", *px);
}else{
printf("查找失败！\n");
}
printf("二叉树的深度为：");
printf("%d\n", BTreeDepth(bt));
clearBTree(&bt);
return 0;
}