当前位置:首页 » 数据结构练习题 » 正文

题目:二叉树应用

1528 人参与  2018年09月10日 21:48  分类 : 数据结构练习题  评论

实现二叉链表表示的二叉树,包括下列运算:

1.建立一棵二叉树;

2.按先序、中序和后序遍历二叉树;

3.按层次遍历;

4.求一棵二叉树的高度;

5.交换一棵二叉树的左右子树;

6.复制一棵二叉树;

#include <stdio.h>
#include <malloc.h>
#include<stdlib.h>
typedef char DataType;/*定义DataType类型*/
typedef enum {Link,Thread}PointerTag;
typedef struct node{
DataType data;
struct node *lchild, *rchild;/*左右孩子子树*/
PointerTag LTag,RTag;
}BiThrNode; /*结点类型*/
typedef BiThrNode *BiThrTree ;/*二叉树类型*/
void  CreatBinTree(BiThrTree *T)
{ /*构造二叉链表,注意:输入序列是先序序列*/
char ch;
if ((ch=getchar())==' ')
  *T=NULL;
else{ /*读入非空格*/
  *T=(BiThrNode *)malloc(sizeof(BiThrNode));/*生成结点*/
(*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;
CreatBinTree(&(*T)->lchild); /*构造左子树    */
CreatBinTree(&(*T)->rchild); /*构造右子树*/
}
}
BiThrTree pre;/*全局变量*/
void InThreading(BiThrTree p)
{ 
if(p)
{InThreading(p->lchild);/*左子树线索化*/
if(!p->lchild){p->LTag=Thread;p->lchild=pre;}/*前驱线索*/
if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}/*后继线索*/
pre=p;/*保持pre指向p*/
InThreading(p->rchild);/*右子树线索化*/
}
} 
int InOrderThreading(BiThrTree *Thrt,BiThrTree T)
                                  /*中序遍厉二叉树T,并将其中序线索化,Thrt指向头结点*/
{ if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);
  (*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建头结点*/
  (*Thrt)->rchild=*Thrt;/*右指针回指*/
  if(!T) (*Thrt)->lchild=*Thrt;
  else
  { (*Thrt)->lchild=T;pre=*Thrt;
    InThreading(T);/*中序遍历进行中序线索化*/
pre->rchild=*Thrt;pre->RTag=Thread;/*最后一个结点线索化*/
(*Thrt)->rchild=pre;
  }
  return 1;
}
int print(BiThrTree e)
{printf("%d  %c  %d\n",e->LTag,e->data,e->RTag);return 1;}
 
int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))
                                  /*T指向头结点,头结点的左链lchild指向根结点,中序遍厉二叉树*/
{BiThrTree p;
p=T->lchild;/*p指向根结点*/
while(p!=T)/*空树或遍厉结束时,p==T*/
{while(p->LTag==Link) p=p->lchild;
  if(!visit(p)) return 0;/*打印*/
  while(p->RTag==Thread&&p->rchild!=T)
  {p=p->rchild;visit(p);}/*访问后继结点*/
  p=p->rchild;
}
return 1;
}
void main()
{ /*测试程序*/
BiThrTree T,Thrt;
CreatBinTree(&T);
    InOrderThreading(&Thrt,T);
    InOrderTraverse(Thrt,print);
}
/*可输入"-+a  *b  -c  d  /e  f  "来测试(注意空格)*/


来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=354

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!