Frost_Jiang 于 2015.06.28 10:42 提问

4个回答

u012736907   2015.06.28 10:47

// 二叉树_C.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "malloc.h"
#define MAX 1240

typedef struct bitnode
{
char data;
struct bitnode *lchild,*rchild;
}BiTNode,*BiTree;

/*初始化*/
BiTree Initiate()
{
BiTNode *bt;
bt=NULL;
return bt;
}

/*生成根节点*/
BiTree Create(char x,BiTree lbt,BiTree rbt)
{
BiTree p;
if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL)return NULL;
p->data=x;
p->lchild=lbt;
p->rchild=rbt;
return p;
}

/*添加左节点*/
BiTree InsertL(BiTree bt,char x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\n插入出错！\n");
return NULL;
}
if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->lchild==NULL) parent->lchild=p;
else
{
p->lchild=parent->lchild;
parent->lchild=p;
}
return bt;
}

/*添加右节点*/
BiTree InsertR(BiTree bt,char x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\n插入出错！");
return NULL;
}
if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->rchild==NULL) parent->rchild=p;
else
{
p->rchild=parent->rchild;
parent->rchild=p;
}
return bt;
}

/*删除左子树*/
BiTree DeleteL(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->lchild==NULL)
{
printf("\n删除出错！");
return NULL;
}
p=parent->lchild;
parent->lchild=NULL;
free(p);
return bt;
}

/*删除右子树*/
BiTree DeleteR(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->rchild==NULL)
{
printf("\n删除出错！");
return NULL;
}
p=parent->rchild;
parent->rchild=NULL;
free(p);
return bt;
}

/*访问节点值*/
void Vist(BiTree bt)
{
printf("%c\t",bt->data);
}

/*递归前序遍历*/
void PreOrder(BiTree bt)
{
if(bt==NULL) return;
Vist(bt);
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}

/*递归中序遍历*/
void InOrder(BiTree bt)
{
if(bt==NULL) return;
InOrder(bt->lchild);
Vist(bt);
InOrder(bt->rchild);
}

/*递归后序遍历*/
void PostOrder(BiTree bt)
{
if(bt==NULL) return;
PostOrder(bt->lchild);
PostOrder(bt->rchild);
Vist(bt);
}

/*非递归前序遍历*/
void NRPreOrder(BiTree bt)
{
BiTNode *stack[MAX],*p;
int top=-1;                     //栈初始化为空
if(bt==NULL) return;
p=bt;                           //p指向根结点
while(! (p == NULL && top == -1))
{
while(p!=NULL)
{
Vist(p);
top++;
stack[top]=p;
p=p->lchild;
}
if(top<0) return;
else
{
p=stack[top];
top--;
p=p->rchild;
}
}
}

/*非递归中序遍历*/
void NRInOrder(BiTree bt)
{
BiTNode *stack[MAX],*p;
int top=-1;                     //栈初始化为空
if(bt==NULL) return;
p=bt;                           //p指向根结点
while(! (p == NULL && top == -1))
{
while(p!=NULL)
{
top++;
stack[top]=p;
p=p->lchild;
}
if(top<0) return;
else
{
p=stack[top];
Vist(p);
top--;
p=p->rchild;
}
}
}

/*非递归后序遍历*/
void NRPostOrder(BiTree bt)
{
BiTNode *stack[MAX];
int Frist[MAX];         //判断在栈中的次数，正则第一次，负则第二次
BiTNode *p;
int top=-1;             //栈初始化为空
if(bt==NULL) return;
p=bt;                   //p指向根结点
while(! (p == NULL && top == -1))
{
while(p != NULL)
{
top++;
stack[top]=p;
Frist[top]=1;
p=p->lchild;
}
if(top > -1)
{
if(Frist[top] > 0)
{
p=stack[top]->rchild;
Frist[top]=-Frist[top];
}
else
{
p=stack[top];
top--;
Vist(p);
p=NULL;
}
}
}
}

/*层次遍历*/
void LevelOrder(BiTree bt)
{
BiTNode *Queue[MAX];
int front,rear;
if(bt==NULL)return;
front=-1;
rear=0;
Queue[rear]=bt;
while(front!=rear)
{
front++;
Vist(Queue[front]);                     //出队，并取值输出

if(Queue[front]->lchild!=NULL)          //入队操作
{
rear++;
Queue[rear]=Queue[front]->lchild;

}
if(Queue[front]->rchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]->rchild;
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
BiTree t,tr=NULL,tl=NULL;
t=Initiate();
t=Create('A',tl,tr);
printf("根节点：\n");
PreOrder(t);
t=InsertL(t,'B',t);
t=InsertR(t,'C',t);
t=InsertL(t,'D',t->lchild);
t=InsertR(t,'G',t->lchild->lchild);
t=InsertL(t,'E',t->rchild);
t=InsertR(t,'F',t->rchild);
printf("\n二叉树遍历情况如下：\n");
printf("递归法前序遍历：  ");
PreOrder(t);
printf("\n");
printf("非递归法前序遍历：");
NRPreOrder(t);
printf("\n");
printf("\n");
printf("递归法中序遍历：  ");
InOrder(t);
printf("\n");
printf("非递归法中序遍历：");
NRInOrder(t);
printf("\n");
printf("\n");
printf("递归法后序遍历：  ");
PostOrder(t);
printf("\n");
printf("非递归法中序遍历：");
NRPostOrder(t);
printf("\n");
printf("\n");
printf("层次遍历：        ");
LevelOrder(t);
printf("\n");
//printf("\n删除后的为：\n");
//t=DeleteL(t,t->lchild);
//printf("前序遍历：");
//PreOrder(t);
return 0;
}

u012736907 回复Frost_Jiang: 我这个是在vs2012里面编译的，编译环境问题，，这个就要你自己改了
2 年多之前 回复
li1310556122 回复Frost_Jiang:
2 年多之前 回复
Frost_Jiang 有引用 加到C里面实现不了
2 年多之前 回复
caozhy      2015.06.28 10:44
Frost_Jiang 你给的里面有引用 加到C里面实现不了
2 年多之前 回复
li1310556122   2015.06.29 23:21

pubuse.h文件
#include
#include
#include /* malloc()等*/
#include /* INT_MAX 等*/
#include /* EOF(=^Z 或F6),NULL /
#include /
atoi() /
#include /
eof() /
#include /
floor(),ceil(),abs() /
#include /
exit() /
/

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/
typedef int Boolean; /* Boolean 是布尔类型,其值是TRUE 或FALSE */
typedef int TElemType;

BinTreeDef.h文件
typedef struct BiTNode
{
TElemType data;
struct BiTNode lchild,*rchild; / вСср╨╒всж╦уК*/
}BiTNode,*BiTree;

BinTreeAlgo.h文件
Status InitBiTree(BiTree &T)
{ /* 操作结果: 构造空二叉树T */
T=NULL;
return OK;
}

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 */
}
}

#define ClearBiTree DestroyBiTree
void CreateBiTree(BiTree &T)
{ /* 按先序次序输入二叉树中结点的值，构造二叉链表表示的二叉树T。变量Nil 表示空（子）树。*/
TElemType ch;
scanf("%d",&ch);
// printf("%d", ch);
if(ch==Nil) /* 空*/
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)
exit(OVERFLOW);
T->data=ch; /* 生成根结点*/
CreateBiTree(T->lchild); /* 构造左子树*/
CreateBiTree(T->rchild); /* 构造右子树*/
}
}

Status BiTreeEmpty(BiTree T)
{ /* 初始条件: 二叉树T 存在*/
/* 操作结果: 若T 为空二叉树,则返回TRUE,否则FALSE */
if(T)
return FALSE;
else
return TRUE;
}

int BiTreeDepth(BiTree T)
{ /* 初始条件: 二叉树T 存在。操作结果: 返回T 的深度*/
int i,j;
if(!T)
return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild);
else
i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
return i>j?i+1:j+1;
}

TElemType Root(BiTree T)
{ /* 初始条件: 二叉树T 存在。操作结果: 返回T 的根*/
if(BiTreeEmpty(T))
return Nil;
else
return T->data;
}
void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数。*/
/* 操作结果: 先序递归遍历T,对每个结点调用函数Visit 一次且仅一次*/
if(T) /* T 不空*/
{
Visit(T->data); /* 先访问根结点*/
PreOrderTraverse(T->lchild,Visit); /* 再先序遍历左子树*/
PreOrderTraverse(T->rchild,Visit); /* 最后先序遍历右子树*/
}
}
void InOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{//编写此函数
/* 初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数*/
/* 操作结果: 中序递归遍历T,对每个结点调用函数Visit 一次且仅一次*/
if(T)
{
InOrderTraverse(T->lchild,Visit); //先中序遍历左子树
Visit(T->data); //访问根结点
InOrderTraverse(T->rchild,Visit); //最后中序遍历右子树
}
}

void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{//编写此函数
/* 初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数*/
/* 操作结果: 后序递归遍历T,对每个结点调用函数Visit 一次且仅一次*/
if(T) /* T 不空*/
{
PostOrderTraverse(T->lchild, Visit);
PostOrderTraverse(T->rchild, Visit);
Visit(T->data);
}
}

BinTreeUse.cpp文件
/* BinTreeUse.cpp 检验BinTreeAlgo.h 的主程序 /
#include"pubuse.h" /

TElemType Nil=0;
#include"BinTreeDef.h" /* 二叉树链式存储结构定义*/
#include"BinTreeAlgo.h" /* 二叉树基本算法和扩展算法定义*/
Status visitT(TElemType e)
{
printf("%d ",e);return OK;
}
int main()
{
int i;
BiTree T,p,c;
TElemType e1,e2;
/* 基本实验算法的验证*/
InitBiTree(T);
printf("构造空二叉树后,树空否？%d(1:是0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);
if(e1!=Nil)
printf("二叉树的根为: %d\n",e1);
else
printf("树空，无根\n");
printf("请先序输入二叉树\n"); //注：自己设计一棵二叉树输入
CreateBiTree(T);
printf("建立二叉树后,树空否？%d(1:是0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);
if(e1!=Nil)
printf("二叉树的根为: %d\n",e1);
else
printf("树空，无根\n");
printf("先序序递归遍历二叉树:\n");
PreOrderTraverse(T,visitT);
printf("\n中序递归遍历二叉树:\n");
InOrderTraverse(T,visitT);
printf("\n后序递归遍历二叉树:\n");
PostOrderTraverse(T,visitT);
}

miracle_yao   2015.07.04 17:35