数据结构————二叉树

二叉树是一种树形数据结构，其中每个节点最多有两个子节点：通常被称为左子节点和右子节点。这种结构使得二叉树非常重要，因为它们具有许多有用的性质，如高效的搜索、排序和存储数据的能力。

二叉树的基本术语

• 根节点：树最顶层的节点，它是整棵树的唯一入口点。
• 子节点：一个节点（如A）的直接后继节点（如B和C）被称为该节点的子节点。
• 父节点：若节点A有指向节点B的边，则A是B的父节点。
• 叶子节点（叶节点）：没有子节点的节点。
• 兄弟节点：具有相同父节点的节点。
• 子树：树的一个部分，包含某个节点及其所有后代节点。
• 深度：从根节点到最远叶子节点的最长路径上的节点数。
• 高度：从某个节点到其最远叶子节点的最长路径上的节点数。根节点的高度是整个树的高度。

二叉树的类型

1. 满二叉树：一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。

        2.完全二叉树：若设二叉树的深度为h，除第h层外，其它各层的节点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树。

二叉树的表示

二叉树通常使用链式存储结构表示，每个节点包含三个部分：数据域、指向左子节点的指针、指向右子节点的指针。

二叉树的操作

• 遍历：二叉树的遍历是指按照一定的规则访问树中的每个节点，并且每个节点只被访问一次。常见的遍历方法有：前序遍历、中序遍历、后序遍历和层序遍历。

创建二叉树（#为空指针）

int idx = 0;
char tree[] = {"ABEH###G##CF#D##I##"};Tnode_t *create_bin_tree()
{TDataType data = tree[idx++];if(data == '#'){return NULL;}Tnode_t *p = malloc(sizeof(Tnode_t));if(NULL == p){perror("malloc error!");return NULL;}p->data = data;p->pl = create_bin_tree();p->pr = create_bin_tree();return p;
}

前序遍历

void printf_tree(Tnode_t *proot)
{if(NULL == proot){printf("#");return;}printf("%c",proot->data);printf_tree(proot->pl);printf_tree(proot->pr);
}

中序遍历

void printf_inorder(Tnode_t *proot)
{if(NULL == proot){return;}printf_inorder(proot->pl);printf("%c",proot->data);printf_inorder(proot->pr);}

后序遍历

void printf_postorder(Tnode_t *proot)
{if(NULL == proot){return;}printf_postorder(proot->pl);printf_postorder(proot->pr);printf("%c",proot->data);
}

层序遍历

void printf_tree_level(Tnode_t *proot)
{Queue_t *p = Create_queue();if(NULL == p){return;}push_queue(p,proot);while(!is_empty_queue(p)){QDataType out;pop_queue(p,&out);printf("%c",out->data);if(out->pl != NULL){push_queue(p,out->pl);}if(out->pr != NULL){push_queue(p,out->pr);}}