数据结构二叉树的基本操作~~~~

Question

RT
类似的建立二叉树~~~

Answer 1

用递归的方法实现以下算法：
1．以二叉链表表示二叉树，建立一棵二叉树；
2．输出二叉树的前序遍历结果；
3．输出二叉树的中序遍历结果；
4．输出二叉树的后序遍历结果；
5．统计二叉树的叶结点个数；
6．统计二叉树的结点个数；
7．计算二叉树的深度。
8．交换二叉树每个结点的左孩子和右孩子；
#include <malloc.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>

#define OK 1
#define NULL 0
#define FALSE 0

typedef struct BiTNode{ //定义链式二叉树结构体
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree T;
char ch;
int flag=0;

int createBiTree(BiTree &T){
//按先序输入二叉树中结点的值（一个字符），空格表示空树
ch=getchar();
if(ch==' ')T=NULL; //表示空树
else if(ch==10)flag=1; //结点信息输入错误则返回0
else {
T=(BiTNode*)malloc(sizeof(BiTree));
if(!T)exit(1);//空间分配不成功则退出
T->data=ch; //生成根结点
createBiTree(T->lchild); //生成左子树
createBiTree(T->rchild); //生成右子树
}//else
return OK;
}//createBiTree

int PreOrderTraverse(BiTree T){ //先序遍历二叉树的递归算法
if(T){
printf("%c",T->data); //访问根结点
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}//if
return OK;
}

int InOrderTraverse(BiTree T){ //中序
if(T){
InOrderTraverse(T->lchild);
printf("%c",T->data); //访问根结点
InOrderTraverse(T->rchild);
}//if
return OK;
}

int PostOrderTraverse(BiTree T){ // 后序
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data); //访问根结点
}
return OK;
}

int NodeCount(BiTree T){ //
if(T==NULL) return 0;// 如果是空树，则结点个数为0
else return 1+NodeCount(T->lchild)+NodeCount(T->rchild);
//否则结点个数为1+左子树的结点个数+右子树的结点个数
}

int LeafNodeCount(BiTree T ){
if(!T)return 0; //如果是空树，则叶子个数为0;
else if(LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild)==0)return 1;//如果是叶子结点，则叶子结点个数为1
else return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);
//否则叶结点个数为左子树的叶结点个数+右子树的叶结点个数
}

int Depth(BiTree T){//计算二叉树的深度
int m,n;
if(T==NULL )return 0;//如果是空树，则深度为0
else {
m=Depth(T->lchild);//计算左子树的深度记为m
n=Depth(T->rchild);//计算右左子树的深度记为n
if(m>n) return(m+1);//二叉树的深度为m 与n的较大者加1
else return (n+1);
}
}
void Exchange1(BiTree T)
{
BiTree temp;
if(T)
{
Exchange1(T->lchild);
Exchange1(T->rchild);
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
}
}

void main(){
int no,out=1;
char choose;
//*****************************主界面**********************************
while(out){
system("cls");
printf("\n这是实验2的程序，请按照说明使用：\n");
printf("1．以二叉链表表示二叉树，建立一棵二叉树，请输入1");
printf("\n2．输出二叉树的前序遍历结果，请输入2");
printf("\n3．输出二叉树的中序遍历结果，请输入3");
printf("\n4．输出二叉树的后序遍历结果请输入4");
printf("\n5．统计二叉树的结点个数，请输入5");
printf("\n6．统计二叉树的叶结点个数，请输入6");
printf("\n7．计算二叉树的深度，请输入7");
printf("\n8. 交换二叉树的左右孩子，请输入8");
printf("\n9．退出，请输入其他\n");
//********************处理输入的选项************************************
choose=getch();
switch(choose){
case '1':
system("cls");
printf("\n请输入二叉链表各结点信息建立二叉树，空树用空格表示：\n");
if(createBiTree(T)==0||flag==1){ //结点输入错误！
printf("输入错误，请重新输入结点信息!\n");
getch();break;}
else
printf("输入完毕！");//成功建立二叉链表
getch();break;
case '2':
printf("\n先序遍历的结果是：");
PreOrderTraverse(T);
getch();break;
case '3':
printf("\n中序遍历的结果是：");
InOrderTraverse(T);
getch();break;
case '4':
printf("\n后序遍历的结果是：");
PostOrderTraverse(T);
getch();break;
case '5':
no=NodeCount(T);
printf("\n总结点个数为:%d\n",no);
getch();break;
case '6':
printf("\n叶子结点的个数为:%d\n",LeafNodeCount(T));
getch();break;
case '7':
printf("\n二叉树深度为：%d\n",Depth(T));
getch();break;
case '8':
printf("\n交换后的结果为：");
Exchange1(T);
PostOrderTraverse(T);
getch();break;
default :
printf("\n你输入的是:其他\n");
getch();
out=0;
} //end switch
}//end of while
system("cls");
printf("\n\n\t\t欢迎使用，再见！");
}

碉堡了！

Answer 2

二叉树的基本操作 C语言实现/*程序实现内容
1．采用二叉树链表作为存储结构，建立二叉树；
2．对二叉树分别按先、中、后序以及按层次遍历，输出相应的访问序列；
3．计算二叉树的深度，统计所有叶子结点总数及树中包含的结点总数。*/
#include"stdio.h"
#include"string.h"
#include"malloc.h"
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//基于先序遍历算法创建二叉树
//要求输入先序序列，其中加入虚结点“#”以示空指针的位置
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode));//生成结点

T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//DLR 先序遍历
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//LDR 中序遍历
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//LRD 后序遍历
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//采用后序遍历求二叉树的深度、结点数及叶子数的递归算法
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//利用“先进先出”（FIFO）队列，按层次遍历二叉树
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队，输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//主函数
main()
{
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree; Input preorder:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do { //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //按层次遍历之前，先选择4，求出该树的结点数。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit (1);
}
printf("\n");
} while(i!=0);本回答被提问者采纳