二叉树的定义和实现

时间:2021-02-28 10:10:53

/*


  1.节点:节点包括一个数据元素及若干指向其子树的分支
  2.节点的度:节点所拥有的子树的个数成为该节点的度
  3.叶节点:度为0的节点称为叶结点
  4.分支节点:度不为0的节点称为分支节点
  5.树的度:树中所有节点的度的最大值
  6.二叉树:是n(n>=0)个有限节点构成的集合。n=0的树称为空二叉树;n=1的树只有一个根结点;
  n〉1的二叉树由一个根节点和至多两个互不相交的,分别称为左子树和右子树的子二叉树构成
  二叉树不是有序树,这是因为,二叉树中某个节点即使只有一个子树也要区分是左子树还是右子树;
  而对于有序树来说,如果某个节点只有一个子树就必定是第一个子树
  
  7.二叉树所有结点的形态有5种:空节点,无左右子树节点,只有左子树节点,只有右子树节点和左右子树均存在的节点


  8.满二叉树:在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子节点都在同一层,则这样的二叉树称作满二叉树


  9.完全二叉树:如果一颗具有n个节点的二叉树的结构与满二叉树的前n个节点的结构相同,这样的二叉树称为完全二叉树


  10二叉树的性质:
  (1):若规定根节点的层数为0,则一棵非空二叉树的第i层上最多有2^i(i>=0)个节点


  (2):
     若规定只有根节点的二叉树的深度为0,则深度为k的二叉树的最大节点数是2^(k+1)-1(k>=-1)
  (3):
     对于一棵非空的二叉树,如果叶节点个数为n0,度为2的节点个数为n2,则有n0=n2+1
  (4):
     具有n个节点的完全二叉树的深度k为大于或等于ln(n+1)-1的最小整数
  (5):
      对于具有n个节点的完全二叉树,如果按照从上至下和从左至右的顺序对所有节点序号从0开始顺序编号,则对于序号为i(0<=i<n)的节点有:
 如果i〉0,则序号为i节点的双亲节点的序号为(i-1)/2(/为整除);如果i=0,则序号为i节点为根节点,无双亲节点
 如果2i+1<n,则序号为i节点的左孩子节点的序号为2i+1;如果2i+1>=n,则序号为i节点无左孩子
 如果2i+2<n,则序号为i节点的右孩子节点的序号为2i+2;如果2i+2>=n,则序号为i节点无右孩子


  11.二叉树的存储结构
    1.二叉树的顺序存储结构
 利用性质5,对于完全二叉树可以利用一维数组存储,如果不是完全二叉树,则可以补空节点,使成为完全二叉树在进行存储,
 但是对于非完全二叉树,可能要浪费很多的空间。


2.二叉树的链式存储结构
  二叉树的链式存储结构就是用指针建立二叉树中节点之间的关系,二叉树最常用的链式存储结构是二叉链。二叉树的二叉链存储结构是一种常用的
  二叉树存储结构。二叉链存存储结构的优点时,结构简单,可以方便的构造任何形状的二叉树,并可以方便的实现二叉树的大多数操作。
  二叉链存储结构的缺点是,查找当前节点的双亲节点操作实现比较麻烦


    3.二叉树的仿真指针存储结构
 利用一维数组和结构体实现,利用数组的下标进行仿真指针进行二叉树的操作
 

*/


<span style="font-size:18px;">#include<stdio.h>
#include<malloc.h>
typedef char DataType;

typedef struct Node{

DataType data;//数据域
struct Node *leftChild;//左子树指针
struct Node *rightChild;//右子树指针
}BiTreeNode;//节点的结构体定义


//初始化
void Initiate(BiTreeNode **root){

*root=(BiTreeNode *)malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}



//左插入节点
//若当前节点curr非空,则在curr的左子树插入元素值为x的新节点
//原curr所指节点的左子树成为新插入节点的左子树
//若插入成功,则返回新插入节点的指针,否则返回空指针
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x){

BiTreeNode *s,*t;
if(curr==NULL){//判断当前节点是否为空

return NULL;//是空则返回NULL
}

t=curr->leftChild;//保存原curr所指节点的左子树
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));//创建节点空间
s->data=x;//赋值
s->leftChild=t;//新插入节点的左子树为原curr的左子树
s->rightChild=NULL;//右子树为空

curr->leftChild=s;//新节点成为curr的左子树
return curr->leftChild;//返回新插入节点的指针
}



//右插入节点
//若当前节点curr非空,则在curr的右子树插入元素值为x的新节点
//原curr所指节点的右子树成为新插入节点的右子树
//若插入成功,则返回新插入节点的指针,否则返回空指针
BiTreeNode *InsertRightNode(BiTreeNode *curr,DataType x){

BiTreeNode *s,*t;
if(curr==NULL){//判断当前节点是否为空

return NULL;//是空则返回NULL
}

t=curr->rightChild;//保存原curr所指节点的右子树
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));//创建节点空间
s->data=x;//赋值
s->rightChild=t;//新插入节点的右子树为原curr的右子树
s->leftChild=NULL;//右子树为空

curr->rightChild=s;//新节点成为curr的右子树
return curr->rightChild;//返回新插入节点的指针
}




//左删除子树
//若curr非空,则删除curr所指节点的左子树
//若删除成功,则返回删除节点的双亲节点,否则返回空指针
BiTreeNode *DeleteLeftTree(BiTreeNode *curr){

//如果当前节点为空或者左子树为空则返回NULL
if(curr==NULL||curr->leftChild==NULL){

return NULL;
}
//释放节点
//Destroy(&curr->leftChild);
curr->leftChild=NULL;//删除后,当前节点的左子树为NULL
return curr;//返回删除节点的双亲节点


}


//右删除子树
//若curr非空,则删除curr所指节点的右子树
//若删除成功,则返回删除节点的双亲节点,否则返回空指针
BiTreeNode *DeleteRightTree(BiTreeNode *curr){

//如果当前节点为空或者右子树为空则返回NULL
if(curr==NULL||curr->rightChild==NULL){

return NULL;
}
//释放节点
// Destroy(&curr->rightChild);
curr->rightChild=NULL;//删除后,当前节点的右子树为NULL
return curr;//返回删除节点的双亲节点


}


void Visit(DataType item){

printf("%c ",item);
}


//前序遍历
/*
1.访问根节点
2.前序遍历根节点的左子树
3.前序遍历根节点的右子树
*/
void PreOrder(BiTreeNode *root,void Visit(DataType item)){
//前序遍历二叉树root,访问操作为Visit()函数
if(root!=NULL){

Visit(root->data);//访问数据
PreOrder(root->leftChild,Visit);//访问左子树
PreOrder(root->rightChild,Visit);//反问右子树
}
}



//中序遍历
/*
1.中序遍历根节点的左子树
2.访问根节点
3.中序遍历根节点的右子树
*/
void InOrder(BiTreeNode *root,void Visit(DataType item)){
//中序遍历二叉树root,访问操作为Visit()函数
if(root!=NULL){
InOrder(root->leftChild,Visit);//访问左子树
Visit(root->data);//访问数据
InOrder(root->rightChild,Visit);//访问右子树
}
}


//后序遍历
/*
1.后序遍历根节点的左子树
2.后序遍历根节点的右子树
3.访问根节点
*/
void PostOrder(BiTreeNode *root,void Visit(DataType item)){
//中序遍历二叉树root,访问操作为Visit()函数
if(root!=NULL){
PostOrder(root->leftChild,Visit);//访问左子树
PostOrder(root->rightChild,Visit);//访问右子树
Visit(root->data);//访问根节点数据

}
}


//撤销二叉树操作
void Destroy(BiTreeNode **root){

if((*root)!=NULL&&(*root)->leftChild!=NULL){

Destroy(&(*root)->leftChild);
}

if((*root)!=NULL&&(*root)->rightChild!=NULL){

Destroy(&(*root)->rightChild);
}


free(*root);

}


void PrintBiTree(BiTreeNode *root,int n){
//逆时针旋转90度,打印二叉树root,n为缩进层数,初始值为0

int i;
if(root==NULL){

return ;//递归出口
}
PrintBiTree(root->rightChild,n+1);//遍历打印右子树
//访问根节点
for(i=0;i<n-1;i++){

printf(" ");
}

if(n>0){

printf("---");
printf("%c\n",root->data);
}

PrintBiTree(root->leftChild,n+1);//遍历打印右子树

}


//查找数据元素
BiTreeNode *Search(BiTreeNode *root,DataType x){
//查找数据元素x是否在二叉树root中
//查找到则返回该节点指针,未查找到则返回空指针
BiTreeNode *find=NULL;
if(root!=NULL){

if(root->data==x){

find=root;
}else{

find=Search(root->leftChild,x);//在左子树中找
if(find==NULL){

find=Search(root->rightChild,x);//在右子树中找
}
}
}

return find;//返回查找标志

}



void main(){


BiTreeNode *root,*p,*find;
char x='E';
Initiate(&root);//初始头指针
p=InsertLeftNode(root,'A');//在头结点插入左子树
p=InsertLeftNode(p,'B');//给'A'插入左子树
p=InsertLeftNode(p,'D');//
p=InsertRightNode(p,'G');//
p=InsertRightNode(root->leftChild,'C');//给'A'插入右子树
InsertLeftNode(p,'E');//
InsertRightNode(p,'F');//

PrintBiTree(root,0);//旋转90度打印树
printf("前序遍历:");
PreOrder(root->leftChild,Visit);
printf("\n中序遍历:");
InOrder(root->leftChild,Visit);
printf("\n后序遍历:");
PostOrder(root->leftChild,Visit);
find=Search(root,x);
if(find!=NULL){

printf("\n数据元素%c在二叉树中\n",x);
}else{

printf("\n数据元素%c不在二叉树中\n",x);
}

Destroy(&root);

}</span>