中序线索树怎么画_数据结构类型讲解——树和森林
树
树是数据结构内很重要的⼀种结构。不过我们此处不深究，仅讨论⼆叉树，线索⼆叉树，哈夫曼树（最优树）。
⼆叉树
1.⼆叉树
定义:
(1)空树；(2)只有⼀个根节点；(3)有左右两个⼦树，并且⼦树也是⼀颗⼆叉树(如图)。
性质：
1. 第 i 层上最多有
个节点.
2.深度为k的树最多有
个节点，我们称之为满⼆叉树，满⼆叉树在底层从右向左减少n个节点，此时称为完全⼆叉树。
3.度为0的结点的个数为度为2的节点个数加⼀，
1. n个节点的完全⼆叉树的深度为
。
注释:[x]表⽰不超过x的最⼤整数，也就是向下取整。
节点序号为 i ，在⼦节点存在的情况下，节点的序号为2i和2i+1
遍历⽅式
1. 先序遍历：先访问根节点，再访问左⼦树然后是右⼦树。
2. 中序遍历：先访问左⼦树，再访问根节点然后再右⼦树。
3. 后序遍历：先访问左⼦树，再访问右⼦树然后是根节点。
先序中序，后序中序能唯⼀的确定唯⼀⼀个⼆叉树
还有其他三种遍历⽅式 : 只需将以上三种⽅式的左和右换位置即可
存储结构
1. 顺序存储结构(由于太浪费内存，所以说⼀般不⽤)
2. 链式存储结构：利⽤⼆叉链表来组成的⼆叉树(有n个节点的⼆叉树，含有n+1个空链域)。树
#include<stdio.h>
typedef struct Lnode{
char data;
struct Lnode *left,*right;
}Lnode,*linkLnode;
//创建树
void setleaf(linkLnode &L){
char data;
scanf("%c",&data);
if(data=='#'){
L=NULL;
return;
}
Lnode *w=new Lnode;
L=w;
L->data=data;
setleaf(L->left);
setleaf(L->right);
}
//先序遍历
void xian(linkLnode L){
if(L==NULL)
return;
else
printf("%ct",L->data);
xian(L->left);
xian(L->right);
xian(L->right);
}
//中序遍历
void zhong(linkLnode L){
if(L==NULL)
return;
zhong(L->left);
printf("%ct",L->data);
zhong(L->right);
}
//后序遍历
void hou(linkLnode L){
if(L==NULL)
return;
hou(L->left);
hou(L->right);
printf("%ct",L->data);
}
//度为0的节点个数
int ling(linkLnode L){
int i;
if(L!=NULL)
i=ling(L->left)+ling(L->right);
else
return 0;
if(L->left==NULL && L->right==NULL)
i=i+1;
return i;
}
//度为1的节点个数
int yi(linkLnode L){
int i;
if(L!=NULL)
i=yi(L->left)+yi(L->right);
else
return 0;
if((L->left==NULL && L->right!=NULL) ||(L->left!=NULL && L->right==NULL))    i=i+1;
return i;
}
/
/从数的最左边，最底层，开始往⾼处，往右侧检测
//度为2的节点个数
int er(linkLnode L){
int i;先序中序后序遍历二叉树
if(L!=NULL)
i=er(L->left)+er(L->right);
else
return 0;
if(L->left!=NULL && L->right!=NULL)
i=i+1;
return i;
}
//计算树的深度
int deep(linkLnode L){
if(L==NULL)
return 0;
if( deep(L->left) > deep(L->right) )
return deep(L->left)+1;
else
return deep(L->right)+1;
}
void main(){
linkLnode L;
L=new Lnode;
L->left=L->right=NULL;
printf("请以先序遍历的⽅式输⼊(#代表此位置⽆值)n");
setleaf(L);
printf("创建成功n");
printf("先序遍历:n");
xian(L);
printf("n中序遍历：n");
zhong(L);
printf("n后序遍历：n");
hou(L);
printf("n度为0的节点个数为:%dn",ling(L));
printf("n度为1的节点个数为:%dn",yi(L));
printf("n度为2的节点个数为:%dn",er(L));
printf("n树的深度为：%dn",deep(L));
}
线索⼆叉树
2 .线索⼆叉树
线索⼆叉树与⼆叉树⼤致⼀样，只不过是将空链域充分利⽤起来，便于查每个节点的前驱和后继。代码仅是中序线索⼆叉树
#include<stdio.h>
typedef struct Lnode{
char data;
struct Lnode *left,*right;
int zuo,you;
}Lnode,*linkLnode;
//创建树
void setleaf(linkLnode &L){
char data;
char data;
scanf("%c",&data);
if(data=='#'){
L=NULL;
return;
}
Lnode *w=new Lnode;
L=w;
L->data=data;
setleaf(L->left);
setleaf(L->right);
}
//中序遍历
void zhong(linkLnode &L){
if(L==NULL)
return;
zhong(L->left);
zhong(L->right);
if(L->left==NULL)
L->zuo=0;
else
L->zuo=1;
if(L->right==NULL)
L->you=0;
else
L->you=1;
}
//设置线索
void guo(linkLnode &L){
Lnode *m,*n;
m=L->left;n=L->right;
printf("此时进⼊到了%cn",L->data);    //输出⼀些过程，便于观察
if(L->zuo!=0){
while(m->you==1)
m=m->right;
m->right=L;
printf("m的指向值为%c，m的右侧为%cn",m->data,m->right->data);    guo(L->left);
}
printf("此时返回到了%cn",L->data);
if(L->you!=0){
while(n->zuo==1)
n=n->left;
n->left=L;
printf("n的指向值为%c,n的左侧为%cn",n->data,n->left->data);
guo(L->right);
}
printf("准备返回上⼀层n");
return;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。