二叉树怎么建立?
4个回答
展开全部
先序递归创建二叉树,并对其进行 先序、中序、后序遍历
#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
}
#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
}
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
展开全部
C语言中二叉树的创建需要用到结构体来定义一个树的数据类型。树这个数据结构有一些数据域,和多个指针域。当然,对于二叉树而言,一般可以定义两个指针域,分别指向root节点的左右子节点。数据结构定义:
struct tree{
int data; //这里数据域以此为例
tree*right,*left;};
真正构建二叉树可以使用动态内存申请,这是一种比较常见的方法(如果不会动态内存申请,可以先看看),但是这样做在子树很多时会耗费较多时间。
因此可以事先开辟好一段内存空间用于存储树。比如 tree T[2000];如果需要建立新的子树,那么只需将数组中某个左右子节点赋值即可。
如有疑问,欢迎继续追问。
struct tree{
int data; //这里数据域以此为例
tree*right,*left;};
真正构建二叉树可以使用动态内存申请,这是一种比较常见的方法(如果不会动态内存申请,可以先看看),但是这样做在子树很多时会耗费较多时间。
因此可以事先开辟好一段内存空间用于存储树。比如 tree T[2000];如果需要建立新的子树,那么只需将数组中某个左右子节点赋值即可。
如有疑问,欢迎继续追问。
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
展开全部
#define NULL 0
#include "stdio.h"
#include "stdlib.h"
//二叉链表结点定义
struct tree
{
int data;
struct tree *lchild;
struct tree *rchild;
};
// 先序建立二叉树
struct tree *create(struct tree *BT,int k)
{
struct tree *p;
int x;
p=(struct tree *)malloc(sizeof(struct tree));
printf("输入结点的整数值(0表示空) : ");
scanf("%d",&x);
if(x!=0)
{
if(!(p=(struct tree *)malloc(sizeof(struct tree))))
exit(0);
//生成主根或子树根
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(k==0)
BT=p;
if(k==1)
BT->lchild=p;
if(k==2)
BT->rchild=p;
create(p,1);//建立左子树
create(p,2);//建立右子树
}
return(BT);
}
// 先序遍历
int visit(struct tree *BT)
{
if(BT!=NULL)
{
printf("%d ",BT->data);
visit(BT->lchild);
visit(BT->rchild);
}
return 0;
}
void main()
{
struct tree *p;
p=(struct tree *)malloc(sizeof(struct tree));
p=create(p,0);
visit(p);
printf("\n");
}
#include "stdio.h"
#include "stdlib.h"
//二叉链表结点定义
struct tree
{
int data;
struct tree *lchild;
struct tree *rchild;
};
// 先序建立二叉树
struct tree *create(struct tree *BT,int k)
{
struct tree *p;
int x;
p=(struct tree *)malloc(sizeof(struct tree));
printf("输入结点的整数值(0表示空) : ");
scanf("%d",&x);
if(x!=0)
{
if(!(p=(struct tree *)malloc(sizeof(struct tree))))
exit(0);
//生成主根或子树根
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(k==0)
BT=p;
if(k==1)
BT->lchild=p;
if(k==2)
BT->rchild=p;
create(p,1);//建立左子树
create(p,2);//建立右子树
}
return(BT);
}
// 先序遍历
int visit(struct tree *BT)
{
if(BT!=NULL)
{
printf("%d ",BT->data);
visit(BT->lchild);
visit(BT->rchild);
}
return 0;
}
void main()
{
struct tree *p;
p=(struct tree *)malloc(sizeof(struct tree));
p=create(p,0);
visit(p);
printf("\n");
}
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询