二叉树是一种树形数据结构,其中每个节点最多有两个子节点:通常被称为左子节点和右子节点。这种结构使得二叉树非常重要,因为它们具有许多有用的性质,如高效的搜索、排序和存储数据的能力。
二叉树的基本术语
- 根节点:树最顶层的节点,它是整棵树的唯一入口点。
- 子节点:一个节点(如A)的直接后继节点(如B和C)被称为该节点的子节点。
- 父节点:若节点A有指向节点B的边,则A是B的父节点。
- 叶子节点(叶节点):没有子节点的节点。
- 兄弟节点:具有相同父节点的节点。
- 子树:树的一个部分,包含某个节点及其所有后代节点。
- 深度:从根节点到最远叶子节点的最长路径上的节点数。
- 高度:从某个节点到其最远叶子节点的最长路径上的节点数。根节点的高度是整个树的高度。
二叉树的类型
- 满二叉树:一个二叉树,如果每一层的节点数都达到最大值,则这个二叉树就是满二叉树。
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);}}