#include "stdio.h"
#include <iostream>
#include <queue>
#include <stack>
#include "malloc.h"
#include "math.h"
#define OK 1
#define error 0
#define fuyi -1
//#define OVERFLOW -2
#define maxqsize 100 // 最大队列长度(对于循环队列，最大队列长度要减1)
#define stacksize2 100 // 存储空间初始分配量
#define stackadd 10 // 存储空间分配增量
//typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
//typedef int ElemType;
using namespace std;
typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;
int create(BiTree &T, int n)
{
int i, e, loop=1;
BiTree s1, s2;
for (i = 1; i <= n; i++){
loop = 1;
scanf("%d",&e);
if (!(s1 = (BiTNode*)malloc(sizeof (BiTNode))))//分配
return error;
s1->data = e; s1->lchild = NULL; s1->rchild = NULL;//设置左右子树为空
s2 = T;
if (s2 == NULL){//第一次进入
T = s1;
}
else
while(loop){//构建排序二叉树
if (s1->data< s2->data){//小于现在节点，进入左子树
if (s2->lchild==NULL){
s2->lchild = s1;//左子树为空，则定位；
loop = 0;
}
else
s2 = s2 ->lchild;//左子树不为空，则继续比较
}
else if (s2->rchild == NULL){//大于等于现节点，进入右子树，右子树为空，则定位
s2->rchild = s1;
loop = 0;
}
else
s2 = s2->rchild;//不为空，继续比较；
}
}
return OK;
}
int Insert(BiTree T)
{
BiTree S1, S2;
int e;
scanf("%d",&e);
if(!(S2 = (BiTNode *)malloc(sizeof(BiTNode))))
return error;
S2->data = e;
S2->lchild = NULL;
S2->rchild = NULL;
S1 = T;
while (T){
if (S1->data<=S2->data)
if(!S1 -> rchild)
{S1 -> rchild = S2;return OK;}
else S1 = S1->rchild;
else
if(!S1 -> lchild)
{S1 -> lchild = S2;return OK;}
else S1 = S1->lchild;
}
T = S2;
return OK;
}
int Search(BiTree T, int e)
{
BiTree S;
S = T;
while(S){
if (S->data < e){
S = S->rchild;
}
else if (S->data >e){
S = S->lchild;
}
else return OK;
}
return error;
}
int Visit(int e)
{
printf("%d ",e);
return OK;
}
int pre( BiTree T, int(*Visit)(int) ) {
if(T)
{
if(Visit(T->data))
if(pre(T->lchild , Visit))
if(pre(T->rchild , Visit))
return OK;
return error;
}
else return OK;
}
int in( BiTree T, int(*Visit)(int) ) {
if(T)
{
if(in(T->lchild , Visit))
if(Visit(T->data))
if(in(T->rchild , Visit))
return OK;
return error;
}
else return OK;
}
int post( BiTree T, int(*Visit)(int) ) {
if(T)
{if(post(T->lchild , Visit))
if(post(T->rchild , Visit))
if(Visit(T->data))
return OK;
return error;
}
else return OK;
}
int NewInOrder(BiTree T)
{
BiTree S1;
stack<BiTree> s;
S1 = T;
while (S1||!s.empty()){
while (S1!=NULL){//如果不为空，一直往左子树走；
s.push(S1);
S1 = S1->lchild;
}
if (!s.empty()){
S1 = s.top();
s.pop();
cout<<S1->data<<" ";
S1 = S1->rchild;
}
}
return OK;
}
int Level(BiTree T)
{
BiTree S1;
S1 = T;
queue<BiTree> q;
q.push(S1);
while(!q.empty()){
cout << q.front()->data << " ";//遍历对头节点
if (q.front()->lchild != NULL)//如果对头节点有左孩子，将左孩子入队
q.push(q.front()->lchild);
if (q.front()->rchild != NULL)//如果对头节点有右孩子，将右孩子入队
q.push(q.front()->rchild);
q.pop();//将已经遍历过的节点出队
}
return OK;
}
int main() //主函数
{
BiTree T=NULL;
int n;
int e;
scanf("%d", &n);
if(!create(T,n))
return error;
pre( T, Visit );
printf("\n");
in( T, Visit);
printf("\n");
post( T, Visit );
printf("\n");
scanf("%d",&e);
printf("%d\n",Search(T,e));
scanf("%d",&e);
printf("%d\n",Search(T,e));
Insert(T);
pre( T, Visit );
printf("\n");
in( T, Visit);
printf("\n");
post( T, Visit );
printf("\n");
NewInOrder( T );
printf("\n");
Level( T );
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-667226.html
