二叉链表存储
㈠ 具有N个结点的二叉树,采用二叉链表存储,共有( )个空 链域.
这道数据题一共有N＋1个空链域。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树被称为满二叉树。
完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。
㈡ 二叉链表是二叉树的存储结构吗
是的，二叉链表是二叉树的存储结构。二叉链表的每一个节点包含一个数据域和两个链接域。
㈢ 一颗二叉树具有n个节点 用二叉链表存储时，其中有（ ）个指针用于指向孩子节点
1、这个问题有点不太清晰啊，由于是n个节点，每个节点有两个指针（左右指针），所以其2n个指针用于指向孩子节点。
2、如果从实际指向了孩子节点的指针则为n-1个，因为n个节点的二叉树，除根结点以外都有自己的父亲结点或者说其都是一个孩子节点，所以有n-1个指针指向他们。
3、函数（function）在数学中为两不为空集的集合间的一种对应关系：输入值集合中的每项元素皆能对应唯一一项输出值集合中的元素。
4、其定义通常分为传统定义和近代定义，前者从运动变化的观点出发，而后者从集合、映射的观点出发。其近代定义是给定一个数集A，假设其中的元素为x，对A中的元素x施加对应法则f，记作f（x），得到另一数集B，假设B中的元素为y，则y与x之间的等量关系可以用y=f（x）表示。
在一个变化过程中，发生变化的量叫变量（数学中，常常为x，而y则随x值的变化而变化），有些数值是不随变量而改变的，我们称它们为常量。
函数与不等式和方程存在联系（初等函数），令函数值等于零，从几何角度看，对应的自变量的值就是图像与X轴的交点的横坐标，从代数角度看，对应的自变量是方程的解。
㈣ 以二叉链表作为二叉树的储存结构，在具有n个结点的二叉链表中n（n＞0），空链域的个数为（）
以二叉链表作为二叉树的储存结构，在具有n个结点的二叉链表中n（n＞0），空链域的个数为n+1。
二叉链表结构描述：
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild ， *netsibling;
} CSNode，* CSTree;
由于二叉树的存储结构比较简单，处理起来也比较方便，所以有时需要把复杂的树，转换为简单的二叉树后再作处理。
(4)二叉链表存储扩展阅读：
二叉树类型：
1、完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
2、满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
3、平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
㈤ 二叉链表存储二叉树的先序遍历算法
二叉链表存储二叉树的先序遍历算法，通常采用递归的算法实现。首先访问二叉树的根节点，然后递归遍历它的左子树，最后，递归遍历他的右子树。
㈥ 二叉链表作存储结构
//偶尔看到提问，翻了翻以前的课程设计，大部分功能类似...就直接复制上来啦，不知道能帮上忙不...都这么久了
//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";
}
}
}
㈦ 二叉树只能采用二又链表来存储.，这个是否正确，为什么
不是的.
二叉链表只是最直观的一种存储方式.而事实上,大部分的情况都不会使用二叉链表.除了一些动态调整树的算法比如平衡树.
更为普遍的存储方式是用线性表来储存二叉树.这种方式下,线性表N存储的节点是N div 2的儿子节点.
㈧ 利用二叉链表存储树，则根节点的右指针是空的，这是为什么呢，谢谢
二叉链表存储树结构，那么任意节点的左孩子指向该结点的孩子结点，右孩子指针指向该节点的兄弟节点，因为这里是树，不是森林，所以树的根节点没有兄弟结点，则右指针是空。
㈨ 建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历，怎么做
建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历，程序操作如下:
#include "stdio.h"
#include "stdlib.h"#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度
typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉树结点定义
typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针
//建立一个空栈
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间
if(!s->base) exit(1); //抛出异常
s->top=s->base; //栈顶=栈尾 表示栈空
s->stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小
return 1;
}
//进栈
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果栈满 追加开辟空间
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1); //抛出异常
s->top=s->base+s->stacksize; //感觉这一句没用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //进栈 栈顶后移
return 1;
}
//出栈
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //栈空 返回0
--s->top;*e=*(s->top); //栈顶前移 取出栈顶元素给e
return 1;}
//取栈顶
int gettop(sqstack *s,bitree **e) //去栈顶元素 注意top指向的是栈顶的后一个
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非递归-----先序建立二叉树----------------------------------*/
bitree *createprebitree(){sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非递归-----中序输出二叉树----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非递归----后序遍历二叉树----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r结点表示访问了右子树 代替标志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}