1、创建一棵二叉树，以二叉链表作存储结构，实现先根遍历算法 2、创建一棵二叉树，实现先根遍历算法、中根

最好是c++的

PING熠 · 2018-4-30 01:59:04

你需要的东西这里面都包含了，你自己看哪里用得上就摘一段下来吧。

// 数据结构.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
return 0;
}

#include
#include
#define MAX 20
#define NULL 0
typedef char ElemType;
typedef int Status;
typedef enum{link,thread} pointertag;
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
pointertag Ltag,Rtag;
}BiTNode,*BiTree;
BiTree pre;
Status CreateBiTree(BiTree *T)//按前序构建二叉树。
{
char ch;
ch=getchar();
if(ch=='#')
  *T=NULL;
else
{
  *T=(BiTree)malloc(sizeof(BiTNode));
  (*T)->data=ch;
  (*T)->Ltag=(*T)->Rtag=link;
  CreateBiTree(&(*T)->lchild);
  CreateBiTree(&(*T)->rchild);
}
return 1;
}
Status CreateBiTree1(BiTree *T)//按中序输入构建二叉树。
{
char ch;
ch=getchar();
if(ch=='#')
  *T=NULL;
else
{
  *T=(BiTree)malloc(sizeof(BiTNode));
  CreateBiTree(&(*T)->lchild);
  (*T)->data=ch;
  CreateBiTree(&(*T)->rchild);
}
return 1;
}
void MidOrder(BiTree T)//递归中序输出。
{
if(T)
{
  MidOrder(T->lchild);
  printf("%2c",T->data);
  MidOrder(T->rchild);
}
}
void PreOrder(BiTree T)//前序输出。
{
if(T)
{
  printf("%2c",T->data);
  PreOrder(T->lchild);
  PreOrder(T->rchild);
}
}
void EndOrder(BiTree T)//后序输出。
{
if(T)
{
  EndOrder(T->lchild);
  EndOrder(T->rchild);
  printf("%2c",T->data);
}
}
void MidOrder1(BiTree T)//非递归中序输出。
{
int i=0;
BiTree p,s[100];
p=T;
do
{
  while(p)
  {
s[i++]=p;
p=p->lchild;
  }
  if(i>0)
  {
p=s[--i];
printf("%2c",p->data);
p=p->rchild;
  }
}while(i>0||p!=NULL);

}
void Levle(BiTree T)//按层次遍历二叉树。
{
BiTree Queue[MAX],b;
int front,rear;
front=rear=0;
if(T)
{
  Queue[rear++]=T;
  while(front!=rear)
  {
b=Queue[front++];
printf("%2c",b->data);
if(b->lchild!=NULL)
Queue[rear++]=b->lchild;
if(b->rchild!=NULL)
Queue[rear++]=b->rchild;
  }
}
}
int depth(BiTree T)//求二叉树的深度。
{
int dep1,dep2;
if(T==NULL)return 0;
else
{
  dep1=depth(T->lchild);
  dep2=depth(T->rchild);
  return dep1>dep2?dep1+1:dep2+1;
}
}
void InThreading(BiTree p)//线索化。
{
if(p)
{
  InThreading(p->lchild);
  if(p->lchild=NULL){p->Ltag=thread;p->lchild=pre;}
  if(pre->rchild==NULL){pre->Rtag=thread;pre->rchild=p;}
  pre=p;
  InThreading(p->rchild);
}
}
Status InorderThreading(BiTree *Thrt,BiTree T)//中序遍历二叉树T，并将其线索化。
{
(*Thrt)=(BiTree)malloc(sizeof(BiTNode));
(*Thrt)->Ltag=link;
(*Thrt)->Rtag=thread;
(*Thrt)->rchild=*Thrt;
if(T==NULL)
  (*Thrt)->lchild=*Thrt;
else
{
  (*Thrt)->lchild=T;
  pre=*Thrt;
  InThreading(T);
  pre->rchild=(*Thrt);
  pre->Rtag=thread;
  (*Thrt)->rchild=pre;
}
return 1;
}
Status InorderTraverse(BiTree Thrt)//中序遍历线索二叉树Thrt,Thrt指向头结点。
{
BiTree p;
p=Thrt->lchild;
while(p!=Thrt)
{
  while(p->Ltag==link)p=p->lchild;
  printf("%2c",p->data);
  while(p->Rtag==thread&&p->lchild!=Thrt)
  {
p=p->rchild;
printf("%2c",p->data);
  }
  p=p->rchild;
}
return 1;
}
void main()
{
BiTree T=NULL,Thrt=NULL;
printf("创建一个二叉树\n");
CreateBiTree(&T);
//InorderThreading(&Thrt,T);
//InorderTraverse(Thrt);
//printf("中序遍历的结果是：");
//MidOrder(T);
//printf("\n");
printf("先序遍历的结果是：");
PreOrder(T);
printf("\n");
/*printf("后序遍历的结果是：");
EndOrder(T);
printf("\n");
printf("按层次遍历二叉树的结果是：");
Levle(T);
printf("\n");
printf("深度输出为：%d",depth(T));
printf("\n");*/
}

李航yan · 2018-4-30 01:59:05

#include "stdio.h"
#include "malloc.h"
#define ELEMTYPE char
typedef struct BiTNode
{ ELEMTYPE data;
  struct BiTNode *lchild,*rchild;
} BiTNode;
BiTNode *bulid()       /*建树*/
{ BiTNode *q;
  BiTNode *s[20];
int i,j;
char x;
printf("请按顺序输入二叉树的结点以输入0和*号结束\n");
printf("请输入你要输入的为第几个结点i=\n");
scanf("%d",&i);
printf("请输入你要输入该结点的数为x=");
getchar();
scanf("%c",&x);
while(i!=0&&x!='*')
{q=(BiTNode*)malloc(sizeof(BiTNode));
q->data=x;
q->rchild=NULL;
q->lchild=NULL;
s=q;

if(i!=1)
{ j=i/2;
   if(i%2==0)
   s[j]->lchild=q;
else
   s[j]->rchild=q;
}

printf("请输入你要输入的为第几个结点x=\n");
scanf("%d",&i);
printf("请输入你要输入该结点的数x=");
getchar();
scanf("%c",&x);
}
return s[1];
}
void preoder(BiTNode *bt)  /*先序遍历*/
{ if(bt!=NULL)
{
  printf("%c\n",(bt->data));

  preoder(bt->lchild);

  preoder(bt->rchild);
}
}
void InOrder(BiTNode *bt) /*中序遍历*/
{ if(bt!=NULL)
{  InOrder(bt->lchild);
printf("%c\n",bt->data);
InOrder(bt->rchild);
}
}
void postOrder(BiTNode *bt)  /*后序遍历*/
{ if(bt!=NULL)
{ postOrder(bt->lchild);
  postOrder(bt->rchild);
  printf("%c\n",bt->data);
}
}

main()
{ int a;
  BiTNode *bt;
  bt=bulid();
k1: printf("需要先序遍历输出请输入1，中序遍历请输入2，后序遍历请输入3,结束输入0:");
  scanf("%d",&a);
  switch(a)
  {
  case(1): preoder(bt);  goto k1;
  case(2): InOrder(bt);  goto k1;
  case(3): postOrder(bt); goto k1;
  case(0): break;
}
}

194344836 · 2018-4-30 01:59:06

1、创建一棵二叉树，以二叉链表作存储结构，实现先根遍历算法 2、创建一棵二叉树，实现先根遍历算法、中根

3 个回复