二叉链表的存储表示

㈠ 若用二叉链表作为二叉树的存储表示，试用编写递归算法，统计二叉树中叶子结点的个数

int count(Node *root) {
if (!root) return 0;
int ret = count(root->leftChild) + count(root->rightChild);
return ret == 0 ? 1 : ret;
}
第一行: 空指针返回0
第二行：统计左右子树的叶子节点个数
第三行：如果左右子树的叶子节点个数为0,则本身是一个叶子节点，返回1；否则返回左右子树的叶子节点个数。

㈡ 以二叉链表作为二叉树的储存结构，在具有n个结点的二叉链表中n（n＞0），空链域的个数为（）

以二叉链表作为二叉树的储存结构，在具有n个结点的二叉链表中n（n＞0），空链域的个数为n+1。

二叉链表结构描述：

typedef struct CSNode{

ElemType data;

struct CSNode *firstchild ， *netsibling;

} CSNode，* CSTree;

由于二叉树的存储结构比较简单，处理起来也比较方便，所以有时需要把复杂的树，转换为简单的二叉树后再作处理。

(2)二叉链表的存储表示扩展阅读：

二叉树类型：

1、完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

2、满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

3、平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

㈢ 若用二叉链表作为二叉树的存储表示，试针对以下问题编写算法：统计二叉树终结点的个数

void CountLeaf (BiTree T, int& count)
{ //递归方法，
if ( T )
{
if ((!T->lchild)&& (!T->rchild))
count++;
CountLeaf( T->lchild, count); // 统计左子树中叶子结点个数
CountLeaf( T->rchild, count); // 统计右子树中叶子结点个数
}
}
----------
非递归，就是采用前序/中序/后序遍历所有节点，并统计。下面就给你提供分别用三个函数的统计方法(PS：因为计数器定义为全局，所以三个函数不能同时使用，使用其中一个就能统计你要的节点数)。
#include "stdlib.h"
#define MAXNODE 20
#define ISIZE 8
#define NSIZE0 7
#define NSIZE1 8
#define NSIZE2 15
//SHOWCHAR = 1(显示字符) SHOWCHAR = 0(显示数字)
#define SHOWCHAR 1

//二叉树结构体
struct BTNode
{
int data;
BTNode *rchild;
BTNode *lchild;
};
//非递归遍堆栈
struct ABTStack
{
BTNode *ptree;
ABTStack *link;
};
static pCounter = 0; //计数器，记录节点个数
/*
前序遍历函数pre_Order_Access()<非递归算法>
参数描述：
BTNode *head: 根节点指针
*/
void pre_Order_Access(BTNode *head)
{
BTNode *pt;
ABTStack *ps,*top;
pt = head;
top = NULL;
printf("\n二叉树的前序遍历结果<非递归>：\t");
while(pt!=NULL ||top!=NULL) /*未遍历完,或堆栈非空*/
{
while(pt!=NULL)
{
if(SHOWCHAR)
printf("%c ",pt->data); /*访问根节点*/
else
printf("%d ",pt->data); /*访问根节点*/
ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
pCounter++;
}
if(top!=NULL)
{
pt = top->ptree; /*栈顶节点出栈*/
ps = top;
top = top->link;
free(ps); /*释放栈顶节点空间*/
pt = pt->rchild; /*遍历节点右子树*/
}
}
}

/*
中序遍历函数mid_Order_Access()<非递归算法>
参数描述：
BTNode *head: 根节点指针
*/
void mid_Order_Access(BTNode *head)
{
BTNode *pt;
ABTStack *ps,*top;
int counter =1;
pt = head;
top = NULL;
printf("\n二叉树的中序遍历结果<非递归>：\t");
while(pt!=NULL ||top!=NULL) /*未遍历完,或堆栈非空*/
{
while(pt!=NULL)
{
ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
pCounter++;
}
if(top!=NULL)
{
pt = top->ptree; /*栈顶节点出栈*/
ps = top;
top = top->link;
free(ps); /*释放栈顶节点空间*/
if(SHOWCHAR)
printf("%c ",pt->data); /*访问根节点*/
else
printf("%d ",pt->data); /*访问根节点*/
pt = pt->rchild; /*遍历节点右子树*/
}
}
}

/*
后序遍历函数last_Order_Access()<非递归算法>
参数描述：
BTNode *head: 根节点指针
*/
void last_Order_Access(BTNode *head)
{
BTNode *pt;
ABTStack *ps,*top;
int counter =1;
pt = head;
top = NULL;
printf("\n二叉树的后序遍历结果<非递归>：\t");
while(pt!=NULL ||top!=NULL) /*未遍历完,或堆栈非空*/
{
while(pt!=NULL)
{
ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
pCounter++;
}
if(top!=NULL)
{
pt = top->ptree; /*栈顶节点出栈*/
ps = top;
top = top->link;
free(ps); /*释放栈顶节点空间*/
printf("%c ",pt->data); /*访问根节点*/
pt = pt->rchild; /*遍历节点右子树*/
}
}
}

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

及层次顺序遍历二叉树的算法。
#define M 10
typedef int DataType;/*元素的数据类型*/
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BitTNode,*BiTree;
int front=0,rear=0;
BitTNode *que[10];
BitTNode *creat()
{BitTNode *t;
DataType x;
scanf("%d",&x);
if(x==0) t=NULL;
else{ t=(BitTNode *)malloc(sizeof(BitTNode));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return(t);
}/*creat*/

/* 前序遍历二叉树t */
void preorder(BiTree t)
{ if(t!=NULL)
{ printf("%4d",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}

/* 中序遍历二叉树t */
void inorder(BiTree t)
{ if(t!=NULL)
{ inorder(t->lchild);
printf("%4d",t->data);
inorder(t->rchild);
}
}

/* 后序遍历二叉树t */
void postorder(BiTree t)
{ if(t!=NULL)
{ postorder(t->lchild);
postorder(t->rchild);
printf("%4d",t->data);
}
}

void enqueue(BitTNode *t)
{if (front!=(rear+1)%M)
{ rear=(rear+1)%M;
que[rear]=t;
}
}/*enqueue*/

BitTNode * delqueue()
{ if(front==rear)return NULL;
{ front=(front+1)%M;
return (que[front]);
}
}/*delqueue*/

/* 按层次遍历二叉树t */
void levorder(BiTree t)
{ BitTNode *p;
if(t!=NULL)
{ enqueue(t);
while (front!=rear)
{ p=delqueue();
printf("%4d",p->data);
if(p->lchild!=NULL) enqueue(p->lchild);
if(p->rchild!=NULL) enqueue(p->rchild);
}
}
}/* levorder */
main()
{BitTNode *root;
root=creat();
printf("\n按先序遍历次序生成的二叉树");
printf("\n前序遍历二叉树");
preorder(root);
printf("\n中序遍历二叉树");
inorder(root);
printf("\n后序遍历二叉树");
postorder(root);
printf("\n层次顺序遍历二叉树");
levorder(root);
}

2、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
#include <stdio.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
} BTree;
BTree * createbt( )
{ BTree *q;
struct node1 *s[30];
int j,i,x;
printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");
printf("i,x = ");
scanf("%d,%c",&i,&x);
while(i != 0 && x != '$')
{ q = (BTree*)malloc(sizeof(BTree)); /*建立一个新结点q*/
q->data = x; q->left = NULL; q->right = NULL;
s[i] = q; /*q新结点地址存入s指针数组中*/
if(i != 1) /*i = 1，对应的结点是根结点*/
{ j = i / 2; /*求双亲结点的编号j*/
if(i % 2 == 0)
s[j]->left = q; /*q结点编号为偶数则挂在双亲结点j的左边*/
else
s[j]->right = q; /*q结点编号为奇数则挂在双亲结点j的右边*/
}
printf("i,x = ");
scanf("%d,%c",&i,&x);
}
return s[1]; /*返回根结点地址*/
}

void preorder(BTree *BT)
/* 前序遍历二叉树t */
{ if(BT!=NULL)
{ printf("%4c", BT ->data);
preorder(BT ->left);
preorder(BT ->right);
}
}

int BTreeDepth(BTree *BT)
{
int leftdep,rightdep;
if (BT==NULL)
return(0);
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if (leftdep>rightdep)
return(leftdep+1);
else
return(rightdep+1);
}
}

int nodecount(BTree *BT)
{
if (BT==NULL)
return(0);
else
return(nodecount(BT->left)+nodecount(BT->right)+1);
}
int leafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(1);
else
return(leafcount(BT->left)+leafcount(BT->right));
}

int notleafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(0);
else
return(notleafcount(BT->left)+notleafcount(BT->right)+1);
}

int onesoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if ((BT->left==NULL && BT->right!=NULL) ||
(BT->left!=NULL && BT->right==NULL))
return(onesoncount(BT->left)+onesoncount(BT->right)+1);
else
return(onesoncount(BT->left)+onesoncount(BT->right));
}

int twosoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL || BT->right==NULL)
return(twosoncount(BT->left)+twosoncount(BT->right));
else if (BT->left!=NULL && BT->right!=NULL)
return(twosoncount(BT->left)+twosoncount(BT->right)+1);
}

main()
{
BTree *B;
B=creatree();
printf("\n按先序遍历次序生成的二叉树");
preorder(B);
printf("\n二叉树深度:%d\n",BTreeDepth(B));
printf("总结点个数:%d\n",nodecount(B));
printf("叶子结点个数:%d\n",leafcount(B));
printf("非叶子结点个数:%d\n",notleafcount(B));
printf("具有双孩子结点个数:%d\n",twosoncount(B));
printf("具有单孩子结点个数:%d\n",onesoncount(B));
}
如果还没解决你的问题，可以加我网络HI账号。

㈤ 用二叉链表存储结构表示下图所示二叉树的，并用递归方法输出三种遍历结果。

//上机题3，已在VC下调试成功。
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 30
typedef struct bnode{
char data;
struct bnode *lchild,*rchild;
}Bnode,*BTree;
typedef BTree DataType;
typedef struct{
DataType data[MAXSIZE];
int top;
}SeqStack,*PseqStack;//定义一个线性表栈
PseqStack Init_SeqStack(void)
{
PseqStack S;
S=(PseqStack)malloc(sizeof(SeqStack));
if(S)
S->top=-1;
return(S);
}//初始化栈。
int Empty_SeqStack(PseqStack S)
{
if(S->top==-1)
return(1);
else return (0);
}//判断是否栈空
int Push_SeqStack(PseqStack S,DataType x)
{
if(S->top==MAXSIZE-1)
return (0);
else
{
S->top++;
S->data[S->top]=x;
return (1);
}
}//入栈。
int Pop_SeqStack(PseqStack S,DataType *x)
{
if(Empty_SeqStack(S))
return (0);
else
{
*x=S->data[S->top];
S->top--;
return (1);
}
}//出栈。
BTree CreateBinTree(void)
{
BTree t;
char ch;
ch=getchar();
if(ch=='#') t=NULL;
else
{
t=(Bnode*)malloc(sizeof(Bnode));
t->data=ch;
t->lchild=CreateBinTree();
t->rchild=CreateBinTree();
}
return t;
}//创建一个二叉树。
void Visit(BTree t)
{
if(t!=NULL)
printf("%c ",t->data);
}//访问结点t。
void InOrder(BTree t)
{
if(t)
{
InOrder(t->lchild);
Visit(t);
InOrder(t->rchild);
}
}//二叉树的递归中序遍历。
int HighTree(BTree p)
{
int h1,h2;
if(p==NULL) return 0;
else
{
h1=HighTree(p->lchild);
h2=HighTree(p->rchild);
if(h1>h2) return (h1+1);
return (h2+1);
}
}//递归求二叉树的高度。
void PreOrder(BTree t)
{
PseqStack S;
BTree p=t;
S=Init_SeqStack();
while(p||!Empty_SeqStack(S))
{
if(p)
{
Visit(p);
Push_SeqStack(S,p);
p=p->lchild;
}
else
{
Pop_SeqStack(S,&p);
p=p->rchild;
}
}
}//二叉树的非递归先序遍历。

void main()
{
BTree T;
int a;
printf("输入二叉树的先序排列(空的地方输入#)：");
T=CreateBinTree();
printf("输出二叉树的先序遍历: ");
PreOrder(T);
printf("\n");
printf("输出二叉树的中序遍历: ");
InOrder(T);
printf("\n");
a=HighTree(T);
printf("二叉树的高度是： %d\n",a);
}
输入是输入12##346###5##

㈥ 二叉链表作存储结构

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

}

㈦ 二叉树的顺序存储方式

二叉树按照层序遍历，依次编号，按照编号的顺序，存储在连续存储单元的方式就是二叉树的顺序存储。

㈧ 二叉树的存储结构是怎样的有哪些类型的存储结构对应的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等或者自定义数据类型。

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

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