二叉链表作存储结构

发布网友 发布时间：2022-03-22 15:44

我来回答

共2个回答

懂视网 时间：2022-03-22 20:05

二叉链表存储结构是二叉树的一种存储方式。链表中结点的两个链域分别指向该结点的第一个孩子结点和第二个孩子结点。

　　二叉链表是树的二叉链表实现方式。二叉树是逻辑结构，二叉链表是二叉树的物理实现，两者之间的关系属于概念和实现，抽象和具体的关系。二叉树的顺序存储结构由一组连续的存储单元依次从上到下，从左到右存储完全二叉树的结点元素。对于一般二叉树，应将其与完全二叉树对应，然后给每个结点从1到i编上号，依次存储在大小为i到1的数组中。

　　

热心网友 时间：2022-03-22 17:13

//偶尔看到提问，翻了翻以前的课程设计，大部分功能类似...就直接复制上来啦，不知道能帮上忙不...都这么久了
//vc++ 6.0

#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
#define OK 1
#define NULL 0
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef char ElemType;//定义二叉树结点值的类型为字符型
const int MaxLength=10;//结点个数不超过10个

typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;

void CreateBiTree(BiTree &T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树

char ch;
ch=getchar(); //不能用cin来输入，在cin中不能识别空格。
if(ch==' ') T=NULL;
else
{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}

void PreOrderTraverse(BiTree T){//先序遍历
if(T){
cout<<T->data<<' ';
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

void InOrderTraverse(BiTree T){ //中序遍历
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<' ';
InOrderTraverse(T->rchild);
}
}

void PostOrderTraverse(BiTree T){ //后序遍历
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<' ';
}
}

void LevelOrderTraverse(BiTree T){ //层序遍历

BiTree Q[MaxLength];
int front=0,rear=0;
BiTree p;
if(T){ //根结点入队
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front]; //队头元素出队
front=(front+1)%MaxLength;
cout<<p->data<<' ';
if(p->lchild){ //左孩子不为空，入队
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){ //右孩子不为空，入队
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}

}

int BTDepth(BiTree T){ //二叉树的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}

int Leaf(BiTree T){ //二叉树的叶子数

if(!T)
return 0;
else if(!T->lchild&&!T->rchild)
return 1;
else
return(Leaf(T->lchild)+Leaf(T->rchild));
}

int NodeCount(BiTree T){ //二叉树的结点总数
if(!T)
return 0;
else
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

int Initbitree (BiTree T) //空树
{

T=NULL;
return FALSE;
}

int Isempty(BiTree T) //判断为空否
{
if(T!=NULL)
return FALSE;

else
return TRUE;
}

int Destroy (BiTree &T) //销毁
{
if( T != NULL )
{ if(T->lchild!=NULL)
Destroy ( T->lchild );
if(T->rchild!=NULL)
Destroy ( T->rchild );
free(T);
T=NULL;
}
return 1;
}

char Root(BiTree T) //返回根节点
{
if(T==NULL)
return NULL;
else
return T->data;
}

ElemType Value(BiTree &p)
{//返回P所指结点的值
return p->data;
}

ElemType Assign(BiTree p,ElemType value)
{ //给P的结点赋新值
return p->data=value;
}

BiTree Parent(BiTree T, BiTree p)//返回父节点
{

if(T!=NULL)
{
if(T->lchild->data==p->data)
{return T;}
if(T->rchild->data==p->data)
return T;
if(T->lchild)
return Parent(T->lchild,p);
if(T->rchild)
return Parent(T->rchild,p);
}
else return NULL;
}

char LeftChild(BiTree p) //返回p的左孩子的值
{
if(p->lchild) //若p存在左孩子
return p->lchild->data;
if(p->lchild==NULL)
return NULL;
}

char RightChild(BiTree p) // 返回p的右孩子的值
{
if(p->rchild)
return p->rchild->data;
if(p->rchild==NULL)
return NULL;
}

int Deletelchild(BiTree p) //删除此二叉树中p节点的左子树
{
if(p)
{
Destroy(p->lchild);
return OK;
}
return ERROR;
}

int Deleterchild(BiTree p) //删除此二叉树中p节点的右子树
{
if(p)
{
Destroy(p->rchild);
return OK;
}
return ERROR;
}

void search(BiTree T,char h,BiTree &p)//查询节点
{
if(T==NULL)
return ;
else{
if(T->data==h)p=T;
search(T->lchild,h,p);
search(T->rchild,h,p);
}
}

void main()
{
BiTree T;
BiTree p;
BiTree q;
char ch;
T=NULL;
int select;
while(1){

cout<<"\n\n";
cout<<"**********************************\n";
cout<<"1.创建二叉树\n";
cout<<"2.前序递归遍历序列\n";
cout<<" 中序递归遍历序列\n";
cout<<" 后序递归遍历序列\n";
cout<<"3.层次遍历序列\n";
cout<<"4.二叉树的深度\n";
cout<<"5.叶子结点数目\n";
cout<<"6.求结点总数目\n";
cout<<"7.返回树根节点\n";
cout<<"8.返回节点p的左孩子\n";
cout<<" 返回节点p的右孩子\n";
cout<<" 返回节点p的 双亲\n";
cout<<"9.判断是否为空(是返回1，否返回0)\n";
cout<<"10.删除p节点的左子树\n";
cout<<"11.删除p节点的右子树\n";
cout<<"12.销毁树!\n";
cout<<"0.退出\n";
cout<<"**********************************\n";
cout<<"\n请选择要执行的操作(选择数字0-12):";
cin>>select;
switch(select){
case 0:
cout<<"退出!";
return;
case 1:
cout<<"请按先序次序输入各结点的值，以空格表示空节点:"<<endl;
CreateBiTree(T);
cout<<"成功！";
break;
case 2:
if(!T) cout<<"未建立树，请先建树！";
else{
cout<<"\n先序遍历:\n";
PreOrderTraverse(T);
cout<<"\n中序遍历:\n";
InOrderTraverse(T);
cout<<"\n后序遍历:\n";
PostOrderTraverse(T);
}
break;
case 3:
if(!T) cout<<"未建立树，请先建树！";
else{
cout<<"\n层序遍历:\n";
LevelOrderTraverse(T);
}
break;
case 4:
cout<<"二叉树的深度为:\n";
cout<<BTDepth(T);
break;
case 5:
cout<<"\n叶子节点数:\n";
cout<<Leaf(T);
break;
case 6:
cout<<"总节点数:\n";
cout<<NodeCount(T);
break;
case 7:
cout<<"返回根节点："<<Root(T);
break;
case 8:
cout<<"\n请输入要查询的节点p值：";
cin>>ch;
search(T,ch,p);
cout<<ch<<"的左孩子是："<<LeftChild(p)<<endl;
cout<<ch<<"的右孩子是："<<RightChild(p)<<endl;
q=Parent(T,p);
cout<<ch<<"的父亲是："<<Value(q)<<endl;
break;
case 9:
cout<<"判断是否为空(是为1，否为0：)"<<Isempty(T);
break;

case 10:
cout<<"\n请输入节点p值：";
cin>>ch;
search(T,ch,p);
cout<<Deletelchild( p);
cout<<"删除了"<<ch<<"的左孩子";
break;
case 11:
cout<<"\n请输入节点p值：";
cin>>ch;
search(T,ch,p);
cout<<Deleterchild( p);
cout<<"删除了"<<ch<<"的右孩子";
break;
case 12:
cout<<"销毁树!"<<Destroy(T);
break;
default:
cout<<"请确认选择项为数字1-12!\n";
}
}

}

参考资料：(貌似当时就七拼八凑。。。)