二叉树 – 数据结构
最后更新于：2022-04-01 20:05:57
二叉树在树结构的应用中起着非常重要的作用，二叉树很多操作简单，并且任何树都可以与二叉树进行相互转换。一个具有n个节点的二叉树，一共有2n个指针域，其中只有n-1个用来指向节点的左右孩子，其余的n+1个指针为空。
二叉树具有很多重要特征：
1. 二叉树的第I层之多有2^(i-1)个节点
2. 具有n个节点的完全二叉树的深度为[log2(n)] + 1
3. 如果i=1，则节点i就是根节点，无双亲；否则其双亲是节点[i/2]。（i是节点的标号）
二叉树有几种存储结构：
1. 顺序存储结构
2. 链式存储结构(在有n个节点的二叉链表中有n+1个空链域)
二叉树的遍历：
限定先左后右的顺序的话，有三种遍历方法。先序遍历，中序遍历，后序遍历。（DLR，LDR，LRD）
除了这三种方式外，还可从上到下，从左到右按层次进行。
线索二叉树：
非线性化结构线性化操作，在每个节点增加两个指针域fwd和bkwd，分别指示节点在依任一次遍历是得到的前驱和后继的信息。以这种节点结构构成的叫做线索链表。
在一棵非线索二叉树以某种次序遍历是其变为一棵线索二叉树的过程称为二叉树的线索化。对于寻找前驱和后继节点这两种运算而言，线索树优于非线索树。但也有缺点，在进行插入和删除操时，线索树比非线索树的时间开销大，原因在于线索树进行插入和删除操作时，除了修改相应的指针外，还要修改相应的线索。
--------------------华丽滴分割线-----------------------------------
关于二叉树结构的定义说明：
~~~
typedef char datatype;
typedef struct bitnode
{
datatype data;
int lflag, rflag;
struct bitnode *lchild, *rchild;
}BitNode, *BitTree;
~~~
二叉树的创建
~~~
BitTree CreatBitTree(void)
{
char ch;
BitTree root;
scanf("%c", &ch);
if(ch == '#')
root = NULL;
else
{
if(!(root = (BitTree)malloc(sizeof(BitNode))))
return 0;
root->data = ch;
root->lflag = 0;
root->rflag = 0;
root->lchild = CreatBitTree();
root->rchild = CreatBitTree();
}
return root;
}
~~~
二叉树的复制，返回一个指向二叉树的指针
~~~
BitTree CopyBitTree(BitTree T)
{
BitTree root;
if(!T)
root = NULL;
else
{
if(!(root=(BitTree)malloc(sizeof(BitNode))))
return 0;
root->data = T->data;
root->lflag = T->lflag;
root->rflag = T->rflag;
root->lchild = CopyBitTree(T->lchild);
root->rchild = CopyBitTree(T->rchild);
}
return root;
}
~~~
二叉树的遍历，三种方式遍历，先序、中序和后序遍历方式
~~~
//先序遍历
void PreOrderTraverse(BitTree root)
{
if(root)
{
printf("%c->", root->data);
PreOrderTraverse(root->lchild);
PreOrderTraverse(root->rchild);
}
}
//中序遍历
void InOrderTraverse(BitTree root)
{
if(root)
{
InOrderTraverse(root->lchild);
printf("%c->", root->data);
InOrderTraverse(root->rchild);
}
}
//后序遍历
void PostOrderTraverse(BitTree root)
{
if(root)
{
PostOrderTraverse(root->lchild);
PostOrderTraverse(root->rchild);
printf("%c->", root->data);
}
}
~~~
二叉树的释放
~~~
void FreeBitTree(BitTree root)
{
if(root)
{
FreeBitTree(root->lchild);
FreeBitTree(root->rchild);
free(root);
}
}
~~~
//---------------------------线索化二叉树-----------------------------
~~~
BitTree pre; //记录上一个节点的指针
//先序线索化二叉树
void PreThreading(BitTree p);
int PreOrderThreading(BitTree *root, BitTree T) //先序线索化二叉树
{
if(!((*root) = (BitTree)malloc(sizeof(BitNode))))
exit(1);
(*root)->lflag = 0;
(*root)->rflag = 1;
(*root)->rchild = (*root);
if(!T)
{
(*root)->lchild = *(root);
return 0;
}
else
{
(*root)->lchild = T;
pre = *(root);
PreThreading(T);
pre->rchild = *(root);
pre->rflag = 1;
(*root)->rchild = pre;
return 1;
}
}
void PreThreading(BitTree p) //先序建立节点的搜索化
{
if(p)
{
if(!p->lchild)
{
p->lchild = pre;
p->lflag = 1;
}
if(!pre->rchild)
{
pre->rchild = p;
pre->rflag = 1;
}
pre = p;
if(p->lflag == 0)
PreThreading(p->lchild);
if(p->rflag == 0)
PreThreading(p->rchild);
}
}
//中序线索化二叉树
void InThreading(BitTree p);
int InOrderThreading(BitTree *root, BitTree T) //中序线索化二叉树
{
if(!((*root) = (BitTree)malloc(sizeof(BitNode))))
exit(1);
(*root)->lflag = 0;
(*root)->rflag = 1;
(*root)->rchild = (*root);
if(!T)
{
(*root)->lchild = *(root);
return 0;
}
else
{
(*root)->lchild = T;
pre = *(root);
InThreading(T);
pre->rchild = *(root);
pre->rflag = 1;
(*root)->rchild = pre;
return 1;
}
}
void InThreading(BitTree p)
{
if(p)
{
InThreading(p->lchild); //左子树线索化
if(!p->lchild)
{
p->lchild = pre;
p->lflag = 1;
}
if(!pre->rchild)
{
pre->rchild = p;
pre->rflag = 1;
}
pre = p;
InThreading(p->rchild);
}
}
~~~
//---------------------------遍历线索化二叉树-----------------------------
~~~
//先序遍历线索化二叉树
void PreOrderTraverse_Threaing(BitTree root) //该root为头结点
{
BitTree p = root, par;
p = root->lchild;
while(p != root)
{
printf("%c->", p->data);
while(p->lflag == 0)
{
p = p->lchild;
printf("%c->", p->data);
}
while((p->rflag==1) && (p->rchild != root))
{
p = p->rchild;
printf("%c->", p->data);
}
if(p->lflag == 0)
p = p->lchild;
else
p = p->rchild;
}
}
//中序遍历线索化二叉树
void InOrderTraverse_Threaing(BitTree root) //该root为头结点
{
BitTree p = root;
p = root->lchild;
while(p != root)
{
while(p->lflag == 0)
{
p = p->lchild;
}
printf("%c->", p->data);
while((p->rflag==1) && (p->rchild != root))
{
p = p->rchild;
printf("%c->", p->data);
}
p = p->rchild;
}
}
~~~
//---------------------------释放线索化二叉树-----------------------------
~~~
//释放先序线索化二叉树
void FreePreOrderThreading(BitTree root)
{
BitTree p = root, t;
static int num = 0;
printf("释放先序线索化链表······\n");
t = p;
p = root->lchild;
while(p != root)
{
if(t != root)
{
free(t);
num++;
}
while(p->lflag == 0)
{
t = p;
p = p->lchild;
free(t);
num++;
}
while((p->rflag==1) && (p->rchild != root))
{
t = p;
p = p->rchild;
free(t);
num++;
}
if(p->lflag == 0)
{
t = p;
p = p->lchild;
}
else
{
t = p;
p = p->rchild;
}
}
free(t);
num++;
free(root);
num++;
printf("释放先序线索化链表%d个节点成功\n", num);
}
//释放中序线索化二叉树
void FreeInOrderThreading(BitTree root)
{
BitTree p = root, t;
static int num = 0;
printf("\n释放中序线索化链表······\n");
t = p;
p = root->lchild;
while(p != root)
{
while(p->lflag == 0)
{
t = p;
p = p->lchild;
}
while((p->rflag==1) && (p->rchild != root))
{
t = p;
free(t);
num++;
p = p->rchild;
}
t = p;
p = p->rchild;
free(t);
num++;
}
free(root);
num++;
printf("释放中序线索化链表%d个节点成功\n\n", num);
}
~~~
//**********************求解关于二叉树的一些问题***************************//
1. 递归求解二叉树中叶子节点的数目
~~~
int LeafCount(BitTree root)
{
if(!root)
return 0;
else if(!root->lchild && !root->rchild)
return 1;
else
return (LeafCount(root->lchild) + LeafCount(root->rchild));
}
~~~
2. 递归将二叉树所有节点的左右子树节点相互交换
~~~
void BitTreeRevolute(BitTree root)
{
BitTree p;
p = root->lchild;
root->lchild = root->rchild;
root->rchild = p;
if(root->lchild)
BitTreeRevolute(root->lchild);
if(root->rchild)
BitTreeRevolute(root->rchild);
}
~~~
';