📄 新建 文本文档.txt
字号:
// 07.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdlib.h"
#include "iostream.h"
#define STACKSIZE 100
#define stack_size 10
#define MAXQSIZE 100
typedef struct BiTNode
{
char data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
typedef struct
{
BiTree *base;
BiTree *top;
int len;
}SqStack;//栈
typedef struct
{
BiTree * base; //初始化的动态分配存储空间
int front; //头指针，若队列不空，指向队列元素
int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;//队
//--------------------------------------------栈---------------------------------------------------
//构造一个空栈
int InitStack(SqStack &S)
{
S.base = ( BiTree*) malloc ( STACKSIZE *sizeof ( BiTree) );//分配存储空间
if( !S.base )
return -1;//分配失败，返回-1
S.top=S.base;//栈空
S.len=STACKSIZE;
return 0;
}
int StackEmpty(SqStack S)
{
if(S.top ==S.base ) return 1;
else return 0;
}//判断栈是否为空
//插入元素e为新的栈顶元素
int Push(SqStack &S,BiTree e)
{
if(S.top - S.base>=STACKSIZE)//栈满，追加存储空间
{
S.base=(BiTree* ) realloc ( S.base, ( S.len+stack_size ) * sizeof ( BiTree) );
if(!S.base)
return -1;//分配失败
S.top=S.base+S.len;
S.len++;
}
*S.top++=e;
return 0;
}
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回0，否则返回-1
int Pop(SqStack &S,BiTree &e)
{
if(S.top==S.base)
return -1;//为空，返回-1
e= *--S.top;
return 0;
}
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------队----------------------------------------
//构造一个空队列Qq
int InitQueue(SqQueue *Qq)
{
Qq->base = ( BiTree* ) malloc ( MAXQSIZE * sizeof ( BiTree ) );
if(!Qq->base)
return -1; //分配失败
Qq->front=Qq->rear=0; //分配成功，置空
return 0;
}
int QueueEmpty(SqQueue Qq)
{
if(Qq.front=Qq.rear)
return 0;
else return (Qq.rear-Qq.front+MAXQSIZE)%MAXQSIZE;
}
int GetHead(SqQueue Qq,BiTree *e)
{
if(Qq.front==Qq.rear)
return 0; //为空，不再继续下面的
*e=Qq.base[Qq.front]; //不为空，则赋值
return 1;
}
//插入元素e为Qq的新的队尾元素
int EnQueue(SqQueue *Qq,BiTree e)
{
if((Qq->rear+1)%MAXQSIZE==Qq->front)
return -1; //队列满
Qq->base[Qq->rear]=e;
Qq->rear = ( Qq->rear+1 ) % MAXQSIZE;
return 0;
}
//若队列不空，则删除Qq的队头元素，用e返回其值，并返回1，否则返回0
int DeQueue(SqQueue *Qq,BiTree e)
{
if(Qq->front==Qq->rear)
return 0;//为空，不再执行下面的
e=Qq->base[Qq->front];
Qq->front = ( Qq->front+1 ) % MAXQSIZE;
return 1;
}
//----------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------
int InitBiTree(BiTree &Tt) //构造空树
{
Tt = (BiTNode *) malloc(sizeof(BiTNode)) ;
if(!Tt)
return -1;
Tt->data =NULL;
Tt->lchild =NULL;
Tt->rchild =NULL;
return 0;
}
void DestroyBiTree(BiTree *T)
{ /* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */
if(*T) // 非空树
{
if((*T)->lchild) // 有左孩子
DestroyBiTree(&(*T)->lchild); // 销毁左孩子子树
if((*T)->rchild) // 有右孩子
DestroyBiTree(&(*T)->rchild); // 销毁右孩子子树
free(*T); //释放根结点
*T=NULL; // 空指针赋0
}
}
int BItreeEmpty(BiTree Tt) //判断树是否为空
{
if(Tt==NULL)
return 0;
else
return 1;
}
int BiTreeDepth(BiTree Tt) //求深度
{
int dep1, dep2;
if (Tt == NULL) return 0; //为空树或为空返回上一层
else
{
dep1 = BiTreeDepth(Tt->lchild); /*遍历左子树*/
dep2 = BiTreeDepth(Tt->rchild); /*遍历右子树*/
if (dep1 > dep2) /*取深度大者*/
return (dep1 + 1);
else return (dep2 + 1);
}
}
int ClearBiTree(BiTree &Tt) //清空树
{
if(Tt)
{
ClearBiTree( Tt->lchild );
ClearBiTree( Tt->rchild );
free(Tt);
Tt=NULL;
return 0;
}
else return 0;
}
char Root(BiTree Tt) //返回根节点
{
if(Tt)
return Tt->data;
else
return 0;
}
char Value(BiTree Tt,BiTree e) //返回某节点
{
return e->data;
}
int Assign(BiTree Tt,BiTree &e,char value) //为某节点赋值
{
if (Tt == NULL)
return 0;
if(e!=Tt)
{
Assign(Tt->lchild,e, value);
Assign(Tt->rchild,e, value);
return 0;
}
else Tt->data=value;
return 0;
}
int d;
int Parent(BiTree T,BiTree p,BiTree &e)
{
if(T==p)
return 0;
if(T->lchild == p ||T->rchild == p)
{
d=1;
e=T;
return 0;
}
else
{
if(d==0)
Parent(T->lchild,p,e);
if(d==0)
Parent(T->rchild,p,e);
}
return 0;
}
int flag=0;
int LeftChild(BiTree T,BiTree p,BiTree &e) //返回左孩子
{
if(!T) //为空时结束
return 0;
if(T=p)
{ //在这层条件中，以下两钟情况都应将flag置1，以使递归函数不再查找右子树
if(T->lchild) //找到所给值并且左孩子存在时，返回该左孩子。
{
flag=1;
e=T->lchild;
return 0;
}
else
{
flag=1;
return NULL; //无左孩子
}
}
else
{
LeftChild(T->lchild,p,e);
if(flag==0) //此处即为flag的用途
LeftChild(T->rchild,p,e);
}
return 0;
}
int k=0;
int RightChild(BiTree T,BiTree p,BiTree &e) //返回右孩子
{
if(!T) //为空时结束
return 0;
if(T=p)
{ //在这层条件中，以下两钟情况都应将flag置1，以使递归函数不再查找左子树
if(T->rchild) //找到所给值并且右孩子存在时，返回该右孩子。
{
k=1;
e=T->rchild;
return 0;
}
else
{
k=1;
return NULL; //无右孩子
}
}
else
{
RightChild(T->rchild,p,e);
if(k==0) //此处即为flag的用途
RightChild(T->lchild,p,e);
}
return 0;
}
int c=0;
int LeftSibing(BiTree T,BiTree p,BiTree &e)
{
if(!T) //为空时结束
return 0;
if(T->rchild == p)
{
if(T->lchild) //找到所给值并且左兄弟存在时，返回该左兄弟。
{
c=1;
e=T->lchild;
return 0;
}
else
{
c=1;
e->data=NULL;
return 0; //无左兄弟
}
}
else if(T->lchild == p)//e是T的左孩子
{
c=1;
e->data=NULL;
return 0;
}
else
{
if(c==0)
LeftSibing(T->lchild,p,e);
if(c==0) //此处即为flag的用途
LeftSibing(T->rchild,p,e);
}
return 0;
}
int b=0;
int RightSibing(BiTree T,BiTree p,BiTree &e)
{
if(!T) //为空时结束
return 0;
if(T->lchild == p)
{
if(T->rchild) //找到所给值并且右兄弟存在时，返回该右兄弟。
{
b=1;
e=T->rchild;
return 0;
}
else
{
b=1;
e->data=NULL;
return 0; //无右兄弟
}
}
else if(T->rchild == p)//e是T的右孩子
{
b=1;
e->data=NULL;
return 0;
}
else
{
if(b==0)
RightSibing(T->lchild,p,e);
if(b==0) //此处即为flag的用途
RightSibing(T->rchild,p,e);
}
return 0;
}
int t=0;
int InsertChild(BiTree T,BiTree p,int LR,BiTree c)
{/* 初始条件: 二叉树T存在,p指向T中某个结点,LR为0或1,非空二叉树c与T不相交且右子树为空 */
/* 操作结果: 根据LR为0或1,插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树 */
if(T==p)
{
if(p)/* p不空 */
{
if(LR==0)
{
c->rchild=p->lchild;
p->lchild=c;
t=1;
}
else /* LR==1 */
{
c->rchild=p->rchild;
p->rchild=c;
t=1;
}
return 0;
}
return -1; /* p空 */
}
else
{
if(t==0)
InsertChild(T->lchild,p,LR,c);
if(t==0)
InsertChild(T->rchild,p,LR,c);
}
return 0;
}
int CreateBiTree( BiTree &Tt )
{//按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树
//构造二叉树链表表示的二叉树Tt(-+a##*b##-c##d##/e##f##)
char ch;
scanf("%c", &ch );
if ( ch ==' ')
Tt = NULL;
else
{
Tt = (BiTNode *) malloc(sizeof(BiTNode));
if(!Tt)
return -1;
Tt->data = ch; // 生成根结点
CreateBiTree( Tt->lchild ); // 构造左子树
CreateBiTree( Tt->rchild ); // 构造右子树
}
return 0;
} // CreateBiTree
int InOrderTraverse ( BiTree T )
{
SqStack Ss; // 非递归中序遍历，需要用一个栈来协助
BiTree p;
InitStack( Ss ); // 初始化栈
p=T;
while ( p|| !StackEmpty( Ss ) )
{
if(p)
{
Push( Ss, p );
p=p->lchild;
}
else
{
Pop( Ss, p );
printf("%c ",p->data);
p=p->rchild;
}
}
return 0;
}
/*void LeverTraverse(BiTree T) //非递归层次遍历
{
SqQueue Q;// 非递归按层遍历，需要用一个队来协助
InitQueue( &Q);
BiTree p;
BiTree e;
p = T;
if(T)
{
printf("%c",T->data);
EnQueue(&Q,T);//进队
}
while(!QueueEmpty(Q))
{
GetHead(Q,&e);
p =e;//取队头元素
DeQueue(&Q,p);//出队
if(p->lchild) //左子树不为空，输出，进队
{
printf("%c",p->lchild->data);
EnQueue(&Q,p->lchild);
}
if(p->rchild)//右子树不为空，输出，进队
{
printf("%c",p->rchild->data);
EnQueue(&Q,p->rchild);
}
}
}*/
//先序遍历的递归
int PreOrderTraverse ( BiTree T )
{
if ( T )
{
printf("%c ",T->data ) ; // 访问结点
PreOrderTraverse( T->lchild ); // 遍历左子树
PreOrderTraverse( T->rchild ); // 遍历右子树
return 0;
}
else return 0;
}// end of PreOrderTraverse
//中序遍历的递归
int InOrderTraverse_t (BiTree T)
{
if( T )
{
InOrderTraverse_t(T->lchild); //遍历左子树
printf("%c ",T->data); //访问结点
InOrderTraverse_t(T->rchild); //遍历右子树
return 0;
}
else return 0;
}
//后序遍历的递归
int PostOrderTraverse (BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild); //遍历左子树
PostOrderTraverse(T->rchild); //遍历右子树
printf("%c ",T->data); //访问结点
return 0;
}
else return 0;
}
int main()
{
BiTree rachel;
InitBiTree(rachel);
printf("请输入结点，如-+a##*b##-c##d##/e##f##,#代表空格\n");
CreateBiTree(rachel);
printf("先序遍历的递归\n\n");
PreOrderTraverse(rachel);
printf("\n\n");
printf("中序遍历的递归\n\n");
InOrderTraverse_t(rachel);
printf("\n\n");
printf("后序遍历的递归\n\n");
PostOrderTraverse(rachel);
printf("非递归中序遍历\n\n");
InOrderTraverse(rachel);
printf("\n\n");
//判断是否为空
int result=BItreeEmpty(rachel);
if(result==0)
printf("该树为空树\n\n");
else
printf("该树不为空\n\n");
//求深度
printf("深度为\n\n");
printf("%d\n\n",BiTreeDepth(rachel));
//返回树的根
if(Root(rachel)!=NULL)
printf("该树的根为：%c",Root(rachel));
printf("\n\n");
//返回某个节点
BiTree f=rachel->lchild->rchild;
printf(" f =%c\n\n", Value(rachel, f));
printf(" 先序遍历\n" );
PreOrderTraverse ( rachel );
printf("\n\n");
//为某个节点赋值
char ch='h';
Assign(rachel,f,ch);
printf(" 先序遍历\n\n" );
PreOrderTraverse ( rachel );
printf("\n\n");
//printf(" 先序遍历\n\n" );
BiTree aa;
printf("双亲为\n\n");
Parent(rachel,f,aa);
printf("%c\n\n",aa->data);
printf("左子树为：\n");
LeftChild(rachel,f,aa);
printf("%c\n",aa->data);
printf("右子树为：\n");
RightChild(rachel,f,aa);
printf("%c\n",aa->data);
BiTree a;
printf("左兄弟为：\n");
LeftSibing(rachel,f,a);
printf("%c\n",a->data);
printf("右兄弟为：\n");
RightSibing(rachel,f,a);
printf("%c\n",a->data);
// printf("按层遍历\n\n");
//LeverTraverse(rachel);
BiTree mytree;
InitBiTree( mytree);
printf("请输入结点，如ghi##j###,#代表空格\n");
CreateBiTree( mytree);
InsertChild(rachel,f,0,mytree);
//清空树
/*ClearBiTree(rachel);
result=BItreeEmpty(rachel);
if(result==0)
printf("该树为空树\n\n\n");
else
printf("该树不为空\n\n\n");
InOrderTraverse(rachel);*/
//printf("请输入结点，如-+a##*b##-c##d##/e##f##,#代表空格\n");
//CreateBiTree(rachel);
printf("\n\n");
return 0;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -