#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "list_queue.h"
#define TREE_TYPE char
//定义结构
typedef struct BinTree
{
TREE_TYPE* arr;
size_t cal;
}BinTree;
//构建 ‘#’空位置
BinTree* create_tree(TREE_TYPE* arr,size_t len)
{
BinTree* tree = malloc(sizeof(BinTree));
tree->arr = malloc(sizeof(TREE_TYPE)*len);
memcpy(tree->arr,arr,sizeof(TREE_TYPE)*len);
tree->cal = len;
}
//对编号为index的节点进行前序遍历
void _dlr_show(BinTree* tree,size_t index)
{
if(index-1>=tree->cal||tree->arr[index-1]=='#') return;
//根
printf("%c ",tree->arr[index-1]);
//左
_dlr_show(tree,index*2);
//右
_dlr_show(tree,index*2+1);
}
//对编号为index的节点进行中序遍历
void _ldr_show(BinTree* tree,size_t index)
{
if(index-1>=tree->cal||tree->arr[index-1]=='#') return;
//左
_ldr_show(tree,index*2);
//根
printf("%c ",tree->arr[index-1]);
//右
_ldr_show(tree,index*2+1);
}
//对编号为index的节点进行后序遍历
void _lrd_show(BinTree* tree,size_t index)
{
if(index-1>=tree->cal||tree->arr[index-1]=='#') return;
//左
_lrd_show(tree,index*2);
//右
_lrd_show(tree,index*2+1);
//根
printf("%c ",tree->arr[index-1]);
}
//前序遍历
void dlr_show(BinTree* tree)
{
_dlr_show(tree,1);
printf("\n");
}
void ldr_show(BinTree* tree)
{
_ldr_show(tree,1);
printf("\n");
}
void lrd_show(BinTree* tree)
{
_lrd_show(tree,1);
printf("\n");
}
//层序遍历
void layer_show(BinTree*tree)
{
ListQueue* queue = create_list_queue();
push_list_queue(queue,1);//编号入队
while(!empty_list_queue(queue))
{
int index = head_list_queue(queue);
//入左子树
int left = index*2;
if(left-1<tree->cal && tree->arr[left-1]!='#')
push_list_queue(queue,left);
//入右子树
int right = index*2+1;
if(right-1<tree->cal && tree->arr[right-1]!='#')
push_list_queue(queue,right);
printf("%c ",tree->arr[index-1]);
pop_list_queue(queue);
}
destroy_list_queue(queue);
printf("\n");
}
//计算编号为index节点的高度
int _high_tree(BinTree* tree,size_t index)
{
if(index-1>=tree->cal || tree->arr[index-1]=='#') return 0;
int left_high = _high_tree(tree,index*2);
int right_high = _high_tree(tree,index*2+1);
return left_high>right_high?left_high+1:right_high+1;
}
//树的高度
int high_tree(BinTree* tree)
{
return _high_tree(tree,1);
}
//计算编号index节点的密度
int _density_tree(BinTree* tree,size_t index)
{
if(index-1>=tree->cal || tree->arr[index-1]=='#') return 0;
return _density_tree(tree,index*2)+_density_tree(tree,index*2+1)+1;
}
//树的密度
int density_tree(BinTree* tree)
{
int density = 0;
for(int i=0;i<tree->cal;i++)
{
if('#' != tree->arr[i]) density++;
}
return density;
//return _density_tree(tree,1);
}
//插入
bool insert_tree(BinTree* tree,TREE_TYPE data,TREE_TYPE pdata)
{
size_t index = 1;
while(index-1<tree->cal)
{
if(tree->arr[index-1] == pdata)
{
if(index*2-1>=tree->cal)
{
//扩容
tree->arr = realloc(tree->arr,tree->cal*2*sizeof(TREE_TYPE));
for(int i=tree->cal;i<tree->cal*2;i++) tree->arr[i] = '#';//赋值
tree->cal *=2;
}
if('#' == tree->arr[index*2-1])
{
tree->arr[index*2-1] = data;
return true;
}
else if('#' == tree->arr[index*2])
{
tree->arr[index*2] = data;
return true;
}
else return false;
}
index++;
}
return false;
}
//删除叶子节点
bool del_tree(BinTree* tree,TREE_TYPE data)
{
size_t index = 1;
while(index-1<tree->cal)
{
if(data == tree->arr[index-1])
{
if(index*2-1 < tree->cal&&'#'!=tree->arr[index*2-1]) return false;
if(index*2 < tree->cal && '#'!=tree->arr[index*2]) return false;
tree->arr[index-1] = '#';
return true;
}
index++;
}
return false;
}
//根据编号显示数据
void index_show_tree(BinTree* tree,size_t index)
{
if(index<1) return;
printf("%c \n",tree->arr[index-1]);
}
//求左
int left_tree(BinTree* tree,TREE_TYPE data)
{
for(int index=0;index<tree->cal;index++)
{
if(tree->arr[index] == data)
{
if((index+1)*2<tree->cal&& '#'!=tree->arr[(index+1)*2-1])
return (index+1)*2;
}
}
return -1;
}
//求右
int right_tree(BinTree* tree,TREE_TYPE data)
{
for(int index=0;index<tree->cal;index++)
{
if(tree->arr[index] == data)
{
if((index+1)*2+1<tree->cal&& '#'!=tree->arr[(index+1)*2])
return (index+1)*2+1;
}
}
return -1;
}
//求根
int root_tree(BinTree* tree,TREE_TYPE data)
{
for(int index=0;index<tree->cal;index++)
{
if(tree->arr[index] == data)
{
if((index+1)%2 == 0)
{
return (index+1)/2;
}
else
{
return index/2;
}
}
}
return -1;
}
int main(int argc,char *argv[])
{
char* str = "ABCD#EFGH##I##J";
BinTree* tree = create_tree(str,strlen(str));
dlr_show(tree);
ldr_show(tree);
lrd_show(tree);
layer_show(tree);
insert_tree(tree,'x','B');
layer_show(tree);
del_tree(tree,'H');
del_tree(tree,'x');
layer_show(tree);
index_show_tree(tree,left_tree(tree,'H'));
index_show_tree(tree,root_tree(tree,'B'));
printf("%d\n",density_tree(tree));
}