‘壹’ 二叉树_链式存储
二叉链：数据域（data）、左子结点域（lchild）、右子节点域（rchild）
定义：
求指定节点的左子节点地址：
求指定节点的右子节点地址：
二叉树的遍历：
定义： 按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次；
用途： 它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心；
遍历规则：
1、先序遍历(DLR)： 头 -> 左 -> 右
2、中序遍历(LDR)： 左 -> 头 -> 右
3、后序遍历(LRD)： 左 -> 右 -> 头
先中后都是对于根结点而言。
二叉树遍历的递归实现：
访问方法：
先序遍历：
中序遍历：
后序遍历：
插一嘴：递归实现的思路清晰，易于理解，但是执行效率很低。非递归实现效率高些。
二叉树遍历的非递归实现：
先序遍历：
中序遍历：
后序遍历：好难-.-||略
利用“扩展先序遍历序列” 创建二叉树二叉链表：
1、若输入的字符是 '#'，则建立空树；
2、否则建立根结点，接着递归建立左子树，然后递归建立右子树。
‘贰’ 二叉树的链式存储结构的数据结构定义、创建、先序和后序遍历，并将结果序列输出。
1、建立一个单链表，并从屏幕显示单链表元素列表。
2、从键盘输入一个数，查找在以上创建的单链表中是否存在该数;如果存在，显示它的位置;如果不存在，给出相应提示。
3、在上述的单链表中的指定位置插入指定的元素
4、删除上述单链表中指定位置的元素。
源程序：头文件
#include<iostream.h>
#include<malloc.h>
typedef char ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
typedef struct LNode{
ElemType data;
LNode *next;
}LNode,*LinkList;
void about(){ //版本信息
cout<<"单链表的操作"
}
void showmenu(){ //功能列表
cout<<endl <<" **********功能**********"<<endl
<<" * 1.输出单链表的全部数据*"<<endl
<<" * 2.查找链表元素 *"<<endl
<<" * 3.链表插入元素 *"<<endl
<<" * 4.链表删除元素 *"<<endl
<<" * 5.结束 *"<<endl
<<" ************************"<<endl
<<"请输入所需功能: ";
}
//*******查看输入的全部数据*********
void PrintList(LinkList L){
LinkList p;
cout<<endl<<"你输入的数据为: ";
p=L->next; //从头结点开始扫描
while(p){ //顺指针向后扫描，直到p->next为NULL或i=j为止
cout<<p->data;
p=p->next; }
cout<<endl; }
//逆序输入 n 个数据元素，建立带头结点的单链表
void CreateList_L(LinkList &L, int n) {
int i;
LinkList p;
L = new LNode;
L->next = NULL; // 先建立一个带头结点的单链表
cout<<"逆序输入 n 个数据元素，建立带头结点的单链表"<<endl;
for (i = n; i > 0; --i) {
p = new LNode;
cin>>p->data; // 输入元素值
p->next = L->next; L->next = p; // 插入
}
}
// L是带头结点的链表的头指针，以 e 返回第 i 个元素
Status GetElem_L(LinkList L, int i, ElemType &e) {
int j;
LinkList p;
p = L->next; j = 1; // p指向第一个结点，j为计数器
while (p && j<i) { p = p->next; ++j; } // 顺指针向后查找，直到 p 指向第 i 个元素或 p 为空
if ( !p || j>i )
return ERROR; // 第 i 个元素不存在
e = p->data; // 取得第 i 个元素
return OK;
}
// 本算法在链表中第i 个结点之前插入新的元素 e
Status ListInsert_L(LinkList L, int i, ElemType e) {
int j;
LinkList p,s;
p = L; j = 0;
while (p && j < i-1)
{ p = p->next; ++j; } // 寻找第 i-1 个结点
if (!p || j > i-1)
return ERROR; // i 大于表长或者小于1
s = new LNode; // 生成新结点
if ( s == NULL) return ERROR;
s->data = e;
s->next = p->next; p->next = s; // 插入
return OK;
}
Status ListDelete_L(LinkList L, int i, ElemType &e)
{LinkList p,q;
int j;
p = L; j = 0;
while (p->next && j < i-1) { p = p->next; ++j; }
// 寻找第 i 个结点，并令 p 指向其前趋
if (!(p->next) || j > i-1)
return ERROR; // 删除位置不合理
q = p->next; p->next = q->next; // 删除并释放结点
e = q->data; free(q);
return OK;
}
#include"LinkList.h"
void main()
{LinkList L;
int n,choice,i;
ElemType e;
about();
cout<<"请输入链表中元素的个数";
cin>>n;
CreateList_L(L, n);
showmenu(); //功能列表
cin>>choice;
while(choice!=5)
{ //输入时候退出程序
switch(choice){
case 1:PrintList(L);break; //1.查看输入的全部数据
case 2:{
cout<<"输入你要查找的元素的位置： ";
cin>>i;GetElem_L(L, i, e);
cout<<"第"<<i<<"个元素的值是"<<e<<endl;
break;} //2.查找链表元素
case 3:
{cout<<"请输入你要插入元素的位置i： ";
cin>>i;
cout<<endl<<"请输入你要插入元素的值： ";
cin>>e;
ListInsert_L(L, i,e);
break;} //3.链表插入元素
case 4:
{cout<<"请输入你要删除元素的位置";
cin>>i;
ListDelete_L(L, i, e) ;
break;} //4.链表删除元素
default:cout<<"输入错误,请输入-5,输入重显示功能表^_^ "<<endl;
}
cout<<endl<<"输入功能序号:";
cin>>choice;
}
}
‘叁’ 采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作
#include<iostream>
#include<cstdio>
#include<stdlib.h>
using namespace std;
typedef int Elemtype;
typedef struct BiTnode
{
Elemtype data;//数据域
struct BiTnode* Lchild,*Rchild; //左右子树域；
}BiTnode,*BiTree;
int create(BiTree *T)
{
Elemtype ch;
Elemtype temp;
scanf("%d",&ch);
temp=getchar();
if(ch==-1)
{
*T=NULL;
}
else
{
*T=(BiTree)malloc(sizeof(BiTnode) );
if(!(*T))
{
exit(-1);
}
else
{
(*T)->data=ch;
printf("请输入%d的左节点的值",ch);
create(&(*T)->Lchild);
printf("请输入%d的右节点的值",ch);
create(&(*T)->Rchild);
}
}
return 1;
}
void Traverse(BiTree T)//前序遍历二叉树
{
if(NULL==T)
{
return;
}
else
{
printf("%d ",T->data);
Traverse(T->Lchild);
Traverse(T->Rchild);
}
}
//中序遍历二叉树
void midTraverse(BiTree T)
{
if(T==NULL){return;}
midTraverse(T->Lchild);
printf("%d ",T->data);
midTraverse(T->Rchild);
}
//后序遍历二叉树
void lasTraverse(BiTree T)
{
if(T==NULL){return;}
lasTraverse(T->Lchild);
lasTraverse(T->Rchild);
printf("%d ",T->data);
}
//求二叉树的深度
int TreeDeep(BiTree T)
{
int deep=0;
if(T)
{
int leftdeep=TreeDeep(T->Lchild);
int rightdeep=TreeDeep(T->Rchild);
deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1;
}
return deep;
}
//求二叉树叶子节点个数
int Leafcount(BiTree T,int &num)
{
if(T)
{
if(T->Lchild==NULL&&T->Rchild==NULL)
{
num++;
}
Leafcount(T->Lchild,num);
Leafcount(T->Rchild,num);
}
return num;
}
int main()
{
BiTree T;
BiTree *p=(BiTree*)malloc(sizeof(BiTree));
int deepth=0,num=0;
printf("请输入第一个节点的值，-1代表没有叶节点: ");
create(&T);
printf("先序遍历二叉树： ");
Traverse(T);
printf(" ");
printf("中序遍历二叉树: ");
midTraverse(T);
printf(" ");
printf("后序遍历二叉树： ");
lasTraverse(T);
printf(" ");
deepth=TreeDeep(T);
printf("树的深度:%d ",deepth);
printf(" ");
Leafcount(T,num);
printf("二叉树的叶子节点个数为:%d ",num);
printf(" ");
return 0;
(3)二叉链存储先后序扩展阅读：
二叉链表是树的二叉链表实现方式。
树的二叉链表实现方式：（孩子兄弟表示法）
以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。
结构描述：
typedefstruct CSNode{
ElemType data；
struct CSNode *firstchild ， *netsibling；
} CSNode，* CSTree；
由于二叉树的存储结构比较简单，处理起来也比较方便，所以有时需要把复杂的树，转换为简单的二叉树后再作处理。
‘肆’ 建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历，怎么做
建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历，程序操作如下:
#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;}
}
}
‘伍’ 以二叉链表为存储结构，分别写出前序、中序、后序遍历二叉树的递归与非递归算法。（数据结构）
#include<iostream.h>
#include<stdlib.h>
typedef char ElemType;
struct BTreeNode
{
ElemType data;
BTreeNode*left;
BTreeNode*right;
};
void InitBTree(BTreeNode*& BT)
{
BT=NULL;
}
void CreateBTree(BTreeNode*& BT,char*a)
{
const int MaxSize=1000;
BTreeNode*s[MaxSize];
int top=-1;
BT=NULL;
BTreeNode*p;
int k;
int i=0;
while (a[i])
{
switch(a[i])
{
case ' ':
break;
case'(':
if(top==MaxSize-1)
{
cout<<"栈空间太少，请增加MaxSize的值！"<<endl;
exit(1);
}
top++; s[top]=p;k=1;
break;
case ')':
if(top==-1)
{
cout<<"二叉树的广义表出错!"<<endl; exit(1);
}
top--;
break;
case ',':
k=2;
break;
default:
p=new BTreeNode;
p->data=a[i];p->left=p->right=NULL;
if(BT==NULL) BT=p;
else
{
if(k==1) s[top]->left=p;
else s[top]->right=p;
}
}
i++;
}
}
bool EmptyBTree (BTreeNode*BT)
{
return BT==NULL;
}
void PreOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
cout<<BT->data<<' ';
PreOrder(BT->left);
PreOrder(BT->right);
}
}
void InOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
InOrder(BT->left);
cout<<BT->data<<' ';
InOrder(BT->right);
}
}
void PostOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
PostOrder(BT->left);
PostOrder(BT->right);
cout<<BT->data<<' ';
}
}
void LevelOrder(BTreeNode* BT)
{
const int MaxSize=30;
BTreeNode* q[MaxSize];
int front=0,rear=0;
BTreeNode* p;
if(BT!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=BT;
}
while (front!=rear)
{
front=(front+1)%MaxSize;
p=q[front];
cout<<p->data<<' ';
if(p->left!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=p->left;
}
if(p->right!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=p->right;
}
}
}
void PrintBTree(BTreeNode*BT)
{
if(BT!=NULL)
{
cout<<BT->data;
if(BT->left!=NULL || BT->right!=NULL )
{
cout<<'(';
PrintBTree(BT->left);
if(BT->right!=NULL)
cout<<',';
PrintBTree(BT->right);
cout<<')';
}
}
}
void ClearBTree(BTreeNode*&BT)
{
if(BT!=NULL)
{
ClearBTree(BT->left);
ClearBTree(BT->right);
delete BT;
BT=NULL;
}
}
void main()
{
BTreeNode* bt;
InitBTree(bt);
char b[50];
cout<<"输入二叉树的广义表字符串"<<endl;
cin.getline(b,sizeof(b));
CreateBTree(bt,b);
PrintBTree(bt); cout<<endl;
cout<<"前序："; PreOrder(bt);cout<<endl;
cout<<"中序："; InOrder(bt); cout<<endl;
cout<<"后序: "; PostOrder(bt); cout<<endl;
cout<<"按层："; LevelOrder(bt); cout<<endl;
}
‘陆’ 二叉链表存储二叉树的先序遍历算法
二叉链表存储二叉树的先序遍历算法，通常采用递归的算法实现。首先访问二叉树的根节点，然后递归遍历它的左子树，最后，递归遍历他的右子树。