二叉树的非递归算法

递归算法"/>

二叉树的非递归算法

//按完全二叉树思想将输入的字符串生成二叉树
#define  max 30
#define NULL 0
#define MAXSIZE 100
#include <stdio.h>
#include <stdlib.h>
typedef struct BNode	
{ char  data;	/*数据域 */struct BNode  *lchild,*rchild;;	//指向左右子女  
}BinTree;
typedef struct{BinTree *data[MAXSIZE];int top;
}SeqStack,*PSeqStack;
//初始化空栈
void preorder(BinTree *t); //声明先根遍历函数
void inorder(BinTree *t);  //声明中根遍历函数
void postorder(BinTree *t);//声明后根遍历函数
int leafs(BinTree *b);      //声明求叶子数函数
int treedeep(BinTree *p);   //声明求树的深度函数
BinTree *swap(BinTree *p);  //声明交换二叉树的所有结点的左右子树的函数
PSeqStack Init_SeqStack(void);
int Empty_SeqStack(PSeqStack S);
int Push_SeqStack(PSeqStack S,int x);
int Pop_SeqStack(PSeqStack S,int *x);
//将字符串中的第i个字符开始的m个字符作为数据生成对应的二叉树
BinTree *cre_tree(char *str,int i,int m)
{				BinTree *p;if(i>=m)   //无效结点return NULL;p=(BinTree *)malloc(sizeof(BinTree));//生成新结点p->data=str[i];p->lchild=cre_tree(str,2*i+1,m);//创建新结点的左子树p->rchild=cre_tree(str,2*i+2,m);//创建新结点的右子树return p;
}
void main()
{int i,n;char str[max];BinTree *root;//根结点printf("请输入二叉树的结点数:");scanf("%d",&n);getchar();//输入数字printf("请输入长度为 %d 的字符串 :",n);for(i=0;i<n;i++)scanf("%c",&str[i]);	printf("\n");root=cre_tree(str,0,n);printf("二叉树已成功创建! 结点序列为：");for(i=0;i<n;i++)printf(" %c ",str[i]);printf("\n");//先根遍历printf("\n先根遍历结果:");preorder(root);printf("\n");//中根遍历printf("\n中根遍历结果:");inorder(root);printf("\n");//后根遍历printf("\n后根遍历结果:");postorder(root);printf("\n");printf("\n叶子数为：%d\n",leafs(root));printf("\n树的深度为：%d\n",treedeep(root));printf("\n交换左右子树后先序遍历序列为：");preorder(swap(root));printf("\n\n");
}
PSeqStack Init_SeqStack(void)
{PSeqStack S;S=(PSeqStack)malloc(sizeof(SeqStack));if(S)S->top=-1;return S;
}
//判断栈空
int Empty_SeqStack(PSeqStack S)
{if(S->top==-1)return 1;elsereturn 0;
}
//入栈
int Push_SeqStack(PSeqStack S,BinTree *x)
{if(S->top==MAXSIZE-1)return 0;else{S->top++;S->data[S->top]=x;return 1;}
}
//出栈
int Pop_SeqStack(PSeqStack S,BinTree **x)
{if(Empty_SeqStack(S))return 0;else{*x=S->data[S->top];S->top--;return 1;}
}
void preorder(BinTree *t)
{PSeqStack S;BinTree *p;p=t;S=Init_SeqStack();while(p||!Empty_SeqStack(S)){if(p){printf(" %c ",p->data);Push_SeqStack(S,p);p=p->lchild;}else{Pop_SeqStack(S,&p);p=p->rchild;}}
}
void inorder(BinTree *t)
{PSeqStack S;BinTree *p;p=t;S=Init_SeqStack();while(p||!Empty_SeqStack(S)){if(p){Push_SeqStack(S,p);p=p->lchild;}else{Pop_SeqStack(S,&p);printf(" %c ",p->data);p=p->rchild;}}
}void postorder(BinTree *t)
{PSeqStack S1;PSeqStack S2;BinTree *p;p=t;S1=Init_SeqStack();S2=Init_SeqStack();while(p||!Empty_SeqStack(S2)){if(p){Push_SeqStack(S1,p);Push_SeqStack(S2,p);p=p->rchild;}else{Pop_SeqStack(S2,&p);printf(" %c ",p->data);p=p->lchild;}}while(!Empty_SeqStack(S1)){Pop_SeqStack(S1,&p);printf(" %c ",p->data);		}
}int leafs(BinTree *b)//求叶子数 
{int num1,num2;if(b==NULL)  return (0);else if(b->lchild==NULL && b->rchild==NULL) return (1);else{num1=leafs(b->lchild);num2=leafs(b->rchild);return(num1+num2);}
}int treedeep(BinTree *p)//求树的深度
{int ldeep,rdeep,deep;if(p==NULL) deep=0;else{ldeep=treedeep(p->lchild);rdeep=treedeep(p->rchild);deep=(ldeep>rdeep?ldeep:rdeep)+1;}return deep;
}BinTree *swap(BinTree *p)//交换二叉树的所有结点的左右子树
{BinTree *stack[max];int k=0;stack[k]=NULL;if(p!=NULL){stack[++k]=p->lchild;p->lchild=p->rchild;p->rchild=stack[k];p->lchild=swap(p->lchild);p->rchild=swap(p->rchild);}return p;
}