C语言中二叉树的链式存储实例分析
二叉树作为树的一种,其节点至多有两个子节点。本文是本站小编搜索整理的关于C语言中二叉树的链式存储实例分析,感兴趣的朋友一起学习吧!!想了解更多相关信息请持续关注我们应届毕业生考试网!
二叉树的链式存储
实现二叉树的基本操作:建立、遍历、计算深度、结点数、叶子数等。
输入C,先序创建二叉树,#表示空节点;
输入H:计算二叉树的高度;
输入L:计算二叉树的叶子个数;
输入N:计算二叉树节点总个数;
输入1:先序遍历二叉树;
输入2:中序遍历二叉树;
输入3:后续遍历二叉树;
输入F:查找值=x的节点的.个数;
输入P:以缩格文本形式输出所有节点。
很简单就不需要多解释了,代码贴上
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
/*二叉树的链式存储表示*/
typedef char DataType; /*应由用户定义DataType的实际类型*/
typedef struct node
{
DataType data;
node *lchild, *rchild; /*左右孩子指针*/
} BinTNode; /*结点类型*/
typedef BinTNode *BinTree;
int sum=0;
void DisplayBinTree(BinTree T); /*用格文本形式表示二叉树*/
void CreateBinTree(BinTree *T); /*构造二叉链表*/
void Preorder(BinTree T); /*前序遍历二叉树*/
void Inorder(BinTree T); /*中序遍历二叉树*/
void Postorder(BinTree T); /*后序遍历二叉树*/
int nodes(BinTree T); /*计算总结点数*/
int leafs(BinTree T); /*计算总叶子数*/
int hight(BinTree T); /*计算二叉树的高度*/
int find(BinTree T,char x); //查找值=x的节点的个数;
int main()
{
BinTree T;
char flg;
while(cin>>flg)
switch(flg)
{
case'C':
getchar();
CreateBinTree(&T);
cout<<"Created success!"<<endl;
break;
case'H':
cout<<"Height="<<hight(T)<<"."<<endl;
break;
case'L':
cout<<"Leaf="<<leafs(T)<<"."<<endl;
break;
case'N':
cout<<"Nodes="<<nodes(T)<<"."<<endl;
break;
case'1':
printf("Preorder is:");
Preorder(T);
cout<<"."<<endl;
break;
case'2':
printf("Inorder is:");
Inorder(T);
cout<<"."<<endl;
break;
case'3':
printf("Postorder is:");
Postorder(T);
cout<<"."<<endl;
break;
case'F':
char x;
int ko;
getchar();
cin>>x;
ko=find(T,x);
cout<<"The count of "<<x<<" is "<<ko<<"."<<endl;
break;
case'P':
cout<<"The tree is:"<<endl;
DisplayBinTree(T);
break;
default:
cout<<"输入有误,请重新输入"<<endl;
}
}
/*构造二叉链表*/
void CreateBinTree(BinTree *T)
{
char ch;
if ((ch=getchar())=='#')
*T=NULL;
else
{
/*读入非空格*/
*T=(BinTNode *)malloc(sizeof(BinTNode));/*生成结点*/
(*T)->data=ch;
CreateBinTree(&(*T)->lchild ); /*构造左子树*/
CreateBinTree(&(*T)->rchild ); /*构造右子树*/
}
}
/*用缩格文本形式表示二叉树*/
void DisplayBinTree(BinTree T)
{
BinTree stack[100],p;
int level[100],top,n,i;
if (T)
{
top=1;
stack[top]=T;
level[top]=0;
while(top>0)
{
p=stack[top];
n=level[top];
for (i=1; i<=n; i++)
cout<<" ";
printf("%cn",p->data);
top--;
if (p->rchild!=NULL)
{
top++;
stack[top]=p->rchild;
level[top]=n+2;
}
if (p->lchild!=NULL)
{
top++;
stack[top]=p->lchild;
level[top]=n+2;
}
}
}
}
/*计算总结点数*/
int nodes(BinTree T)
{
if(T)
{
if( (T->lchild==NULL)&&(T->rchild==NULL))
return 1;
else
return nodes(T->lchild)+nodes(T->rchild)+1;
}
return 0;
}
/*计算总叶子数*/
int leafs(BinTree T)
{
if(T)
{
if ((T->lchild==NULL)&&(T->rchild==NULL))
return 1;
else
return leafs(T->lchild)+leafs(T->rchild);
}
return 0;
}
/*计算树的高度*/
int hight(BinTree T)
{
if(T)
{
if ((T->lchild==NULL)&&(T->rchild==NULL))
return 1;
else if((T->lchild==NULL)&&(T->rchild))
return 1+hight(T->rchild);
else if((T->lchild)&&(T->rchild==NULL))
return 1+hight(T->lchild);
else
return hight(T->lchild)+hight(T->rchild);
}
return 0;
}
/*前序遍历二叉树*/
void Preorder(BinTree T)
{
if(T)
{
printf("%c ",T->data); /*访问结点*/
Preorder(T->lchild);
Preorder(T->rchild);
}
}
/*中序遍历二叉树*/
void Inorder(BinTree T)
{
if(T)
{
Inorder(T->lchild);
printf("%C ",T->data);
Inorder(T->rchild);
}
}
/*后序遍历二叉树*/
void Postorder(BinTree T)
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%C ",T->data);
}
}
int find(BinTree T,char x)
{
if(T)
{
if((T->data)==x)
sum++;
find(T->lchild,x);
find(T->rchild,x);
}
return sum;
}
-
C语言入门知识:常量
导语:在程序运行中,其值不能被改变的量称为常量。下面是常量相关知识,欢迎阅读:常量有5种类型:整型常量、实型常量、字符常量、字符串常量和符号常量。(一)数值转换数字的四种表现形式:①:二进制:所有数字由0,1构成,逢二进一,二进制数中不会出现2.。例:110101②:八进制:以数...
-
计算机C语言考点大全
C语言是世界上最流行、使用最广泛的高级程序设计语言之一。下面小编整理了计算机C语言考点大全,希望对大家有帮助!【考点1】C程序C语言程序结构有三种:顺序结构,循环结构(三个循环结构),选择结构(if和switch)【考点2】main函数每个C语言程序中main函数是有且只...
-
C语言自学入门技巧
学习C语言不是一朝一夕的事情,但也不需要花费很长的时间才能精通。下面小编就为大家介绍一下C语言自学入门技巧吧!C语言自学入门技巧11、程语语言其实是一个很初级的工具,但是又必须熟练的掌握它,学懂一门编程语言就好像学会了写字,但是会写字的人不见得会写文章,而...
-
2017年计算机二级C语言对C语言的深入探讨知识点
引导语:它的应用范围广泛,具备很强的数据处理能力。以下是本站小编分享给大家的2017年计算机二级C语言对C语言的深入探讨知识点,欢迎阅读!【考点1】编译预处理凡以#开头的这一行,都是编译预处理命令行,编译预处理不加分号,不占运行时间。宏替换仅是简单的文本替换,如#...