二叉链的存储表示什么

⑴ 二叉链表在存储器是怎样的

大概这个样子，这个是我以前写的二叉搜索树：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data,rep;
struct node *left,*right;
} node;
node* insert(node *tree,int x);
int search(node *tree,int x);
node* del(node *tree,int x);
int main()
{
char str[20],ch;
int x;
struct node *tree = NULL;
gets(str);
while (strcmp(str,"quit"))
{
if (!strcmp(str,"insert"))
{
scanf("%d",&x);
tree = insert(tree,x);
}
else if (!strcmp(str,"delete"))
{
scanf("%d",&x);
tree = del(tree,x);
}
else if (!strcmp(str,"search"))
{
scanf("%d",&x);
if (search(tree,x))
puts("Found!");
else
puts("Not Found!");
}
else
puts("There is an error!");
ch = getchar();
gets(str);
}
return 0;
}
node* insert(node *tree,int x)
{
if (tree == NULL)
{
tree = (struct node *)malloc(sizeof(struct node *));
tree->data = x;
tree->rep = 1;
tree->left = (struct node *)malloc(sizeof(struct node *));
tree->right = (struct node *)malloc(sizeof(struct node *));
tree->left = NULL;
tree->right = NULL;
}
else if (tree->data == x)
tree->rep++;
else if (x < tree->data)
tree->left = insert(tree->left,x);
else if (x > tree->data)
tree->right = insert(tree->right,x);
return tree;
}
int search(node *tree,int x)
{
if (tree == NULL)
return 0;
else if (tree->data == x)
return 1;
else if (x < tree->data)
return search(tree->left,x);
else if (x > tree->data)
return search(tree->right,x);
}
node* del(node *tree,int x)
{
struct node *p,*q;

if (tree == NULL) {}
else if (x < tree->data)
tree->left = del(tree->left,x);
else if (x > tree->data)
tree->right = del(tree->right,x);
else if (tree->data == x)
{
if (tree->rep > 1)
tree->rep--;
else
{
if (tree->left == NULL)
return tree->right;
else if (tree->right == NULL)
return tree->left;
else
{
p = tree->left;
q = tree;
while (p->right)
{
q = p;
p = p->right;
}
tree->data = p->data;
tree->rep = p->rep;
q->right = p->left;
}
}
}
return tree;
}

⑵ 简述二叉链表的类型定义

二叉链表是树的二叉链表实现方式。
树的二叉链表实现方式
（孩子兄弟表示法）
以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和它的下一个兄弟结点。
typedefstruct
CSNode{
ElemType
data；
struct
CSNode
*firstchild
，
*netsibling；
}
CSNode，*
CSTree；
由于二叉树的存储结构比较简单，处理起来也比较方便，所以有时需要把复杂的树，转换为简单的二叉树后再作处理。

⑶ 二叉链表是二叉树的存储结构吗

是的，二叉链表是二叉树的存储结构。二叉链表的每一个节点包含一个数据域和两个链接域。

⑷ 顺序存储是二叉树常用的存储结构吗

二叉树的存储结构
二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构。
1．顺序存储结构
二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。图5-5(a)是一棵完全二叉树，图5-5（b）给出的图5-5(a)所示的完全二叉树的顺序存储结构。

(a) 一棵完全二叉树 (b) 顺序存储结构
图5-5 完全二叉树的顺序存储示意图
对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。如图5-6给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。最坏的情况是右单支树，如图5-7 所示，一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。

(a) 一棵二叉树 (b) 改造后的完全二叉树

(c) 改造后完全二叉树顺序存储状态
图5-6 一般二叉树及其顺序存储示意图

(a) 一棵右单支二叉树 (b) 改造后的右单支树对应的完全二叉树

(c) 单支树改造后完全二叉树的顺序存储状态
图5-7 右单支二叉树及其顺序存储示意图
结构5-1二叉树的顺序存储

#define Maxsize 100 //假设一维数组最多存放100个元素
typedef char Datatype; //假设二叉树元素的数据类型为字符
typedef struct
{ Datatype bt[Maxsize];
int btnum;
}Btseq;

2．链式存储结构
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为：

其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表，如图5-8所示。

(a) 一棵二叉树 (b) 二叉链表存储结构
图5-8 二叉树的二叉链表表示示意图
为了方便访问某结点的双亲，还可以给链表结点增加一个双亲字段parent,用来指向其双亲结点。每个结点由四个域组成，其结点结构为：

这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。利用这样的结点结构表示的二叉树的链式存储结构被称为三叉链表。
图5-9给出了图5-8 (a)所示的一棵二叉树的三叉链表表示。

图5-9二叉树的三叉链表表示示意图
尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。
结构5-2二叉树的链式存储
#define datatype char //定义二叉树元素的数据类型为字符
typedef struct node //定义结点由数据域，左右指针组成
{ Datatype data;
struct node *lchild,*rchild;
}Bitree;

⑸ 二叉树的存储结构是怎样的有哪些类型的存储结构对应的c语言描述是

线性表的链式存储结构：
typedef
int
elemtype;
typedef
struct
lnode
{
elemtype
data;
struct
lnode
*next;
}lnode,*linklist;
(被封装好的每个节点，都有一个数据域data和一个指针域*next用于指向下一个节点)
二叉树的二叉链表：
typedef
int
telemtype;
typedef
struct
bitnode
{
telemtype
data;
struct
bitnode
*lchild,*rchild;
}bitnode,*bitree;
(被封装好的每个节点，都有一个数据域data和两个指针域
*lchild,*rchild分别指向左右子树)
需要什么类型的数据作为数据域可更改，或者typedef
int
elemtype;和typedef
int
telemtype;中的int，比如改为char、float等或者自定义数据类型。

⑹ 若用二叉链表作为二叉树的存储表示，试编写算法交换二叉树中各结点的左右子数。

递归:
void exchange(BTree *rt){
BTree *temp = NULL;
if(rt->lchild == NULL && rt->rchild == NULL)
return;
else{
temp = rt->lchild;
rt->lchild = rt->rchild;
rt->rchild = temp;
}
if(rt->lchild)
exchange(rt->lchild);
if(rt->rchild)
exchange(rt->rchild);
}

非递归:
Stack是一个定义好的通用堆栈类型,支持初始化/进站/出战等操作
int Exchange(BiTree *T)
{
Stack s;
BiTree *p;
InitStack(s);
p=T;
while(p||!StackEmpty(s)){
if(p){
push(s,p);
p->Lchild;
}
else{
pop(s,p);
t=p->Rchild;
p->Rchild=p->Lchild;
p->Lchild=t;
p-＝->Lchild;
}
}
return 1;
}

⑺ 二叉链表存储结构，实现二叉树的遍历

前几天写的，输入二叉树的广义表形式，建立二叉树的链式存储。输出的是中序。有注释，看懂了应该其他的都能写了吧。#include<stdio.h>
#include<stdlib.h>
int n=0; //全局变量
struct tree //二叉树结构体
{
char data;
struct tree *lc;
struct tree *rc;
};
tree *creat(char a[]) //创建树的二叉树
{
tree *h;
h=(tree *)malloc(sizeof(tree));
h->lc=NULL;
h->rc=NULL;
if(a[n]!=')'&&a[n]!='('&&a[n]!=',') //当a[n]为字母存入a[]
{
h->data=a[n];
n++;
}
if(a[n]=='(') //a[n]为左括号对h->lc递归操作
{
n++;
h->lc=creat(a);
}
if(a[n]==',') //a[n]为逗号对h->rc递归操作
{
n++;
h->rc=creat(a);
return h;
}
if(a[n]==')') //a[n]为右括号返回h
{
n++;
return h;
}
else
return h;

}
void print(tree *h) //二叉树中序输出
{
if(h!=NULL)
{
print(h->lc);
printf("%c",h->data);
print(h->rc);
}

}

int high(char a[]) //判断树的高度
{
int i=0,max=0,p=0;
while(a[i]!=0)
{
if(a[i]=='(')
{
p++;
if(max<i)
max=p;
}
if(a[i]==')')
p--;
i++;
}
if(p!=0)
{
printf("左右括号数不等,输入错误\n"); //判断左右括号数是否相等
exit(1);
}
return max+1;
}
void main() //主函数
{
int i=0;
tree *h;
char a[50]={0};
gets(a);
while(a[i]!=0) //判断各种可能出现的输入错误
{

if(i==0&&(a[i]=='('||a[i]==')'||a[i]==',')) //判断数组首元素是否为字母
{
printf("首节点错误\n");
exit(1);
}
if(a[i]=='(') //左括号之前一定是字母
{
if(a[i-1]=='('||a[i-1]==')'||a[i-1]==',')
{
printf("输入错误\n");
exit(1);
}
}
if(a[i]!='('&&a[i]!=')'&&a[i]!=',') //两个字母不能在一起
{
if(a[i+1]!='('&&a[i+1]!=')'&&a[i+1]!=',')
{
printf("输入错误,两个字母不能在一起\n");
exit(1);
}
}
i++;
}
h=creat(a); //创建树
printf("该树的高度为:%d\n",high(a));
printf("该二叉树的中序输出为:");
print(h);
printf("\n");
}

⑻ 二叉链表作存储结构

//偶尔看到提问，翻了翻以前的课程设计，大部分功能类似...就直接复制上来啦，不知道能帮上忙不...都这么久了
//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";
}
}

}

⑼ 二叉树的存储结构为二叉链表 typedef struct node { DateType data； Struct node * next； }ListNode；

typedefListNode*LinkList；
LinkListLeafhead=NULL；
VoidInorder(BinTreeT)

{
LinkLists；
If(T){
Inorder(T－>lchild)；
If((!T－>lchild)&&(!T－>rchild)){
s=(ListNode*)malloc(sizeof(ListNode))；
s－>data=T－>data；
s－>next=Leafhead；
Leafhead=s；
}
Inorder(T－>rchild)；
}
}