数据结构-树-006

1二叉树

1.1目标二叉树

在这里插入图片描述

前序遍历：ABDHIEJCFKG
中序遍历：HDIBEJAFKCG
后序遍历：HIDJEBKFGCA
层序遍历：ABCDEFGHIJK

运行结果：

运行结果符合目标二叉树的深度优先（前序遍历，中序遍历，后序遍历）遍历结果。

在这里插入图片描述

树的表示：char sex[]={'A','B','D','H','#','#','I','#','#','E','#','J','#','#','C','F','#','K','#','#','G','#','#'};

说明：

这里自定义数据类型是一个结构体，为了快速实现该二叉树，使用了自定义数据类型中的成员【sex】，其它成员未进行操作。

1.2树的结点结构体定义

/*==========自定义数据类型==========*/
typedef struct student
{char name[32];char sex;int age;
}DATA_TYPE;

/*==========定义一个树结点==========*/
typedef struct tree_node
{DATA_TYPE data;//数据域struct tree_node *left_child;struct tree_node *right_child;
}TREE_NODE;

1.3创建一个二叉树

/*==========创建一个二叉树==========*/
TREE_NODE *create_binary_tree(void)
{DATA_TYPE data;TREE_NODE *pnode=NULL;data.sex=sex[tree_create_index++];if('#'==data.sex){return NULL;}/*创建一个二叉树结点*/pnode=malloc(sizeof(TREE_NODE));if(NULL==pnode){perror("fail to malloc");return NULL;}/*新结点初始化*/pnode->data=data;pnode->left_child=create_binary_tree();pnode->right_child=create_binary_tree();return pnode;
}

1.4树的遍历

自定义树的遍历方式：

/*==========遍历方式==========*/
void show_data(TREE_NODE *proot)
{printf("%-10s\t%-10c\t%-10d\n",proot->data.name,proot->data.sex,proot->data.age);
}

1.4.1前序遍历

/*==========前序遍历==========*/
void preorder_traversal(TREE_NODE *proot,void (*pfun)(TREE_NODE *))
{if(NULL==proot){return ;}pfun(proot);preorder_traversal(proot->left_child,pfun);preorder_traversal(proot->right_child,pfun);
}

1.4.1中序遍历

/*==========中序遍历==========*/
void inorder_traversal(TREE_NODE *proot,void (*pfun)(TREE_NODE *))
{if(NULL==proot){return ;}inorder_traversal(proot->left_child,pfun);pfun(proot);inorder_traversal(proot->right_child,pfun);
}

1.4.1后序遍历

/*==========后序遍历==========*/
void postorder_traversal(TREE_NODE *proot,void (*pfun)(TREE_NODE *))
{if(NULL==proot){return ;}postorder_traversal(proot->left_child,pfun);postorder_traversal(proot->right_child,pfun);pfun(proot);
}