二叉树
二叉树首先是一棵树,每个节点都不能有多于两个的儿子,也就是树的度不能超过2。二叉树的两个儿子分别称为“左儿子”和“右儿子”,次序不能颠倒。如图1是一个简单的二叉树。
二叉树的种类
一种是满二叉树,除了最后一层的叶子节点外,每一层的节点都必须有两个儿子节点。如图2是一个满二叉树。
另一种是完全二叉树,一棵二叉树去掉最后一层后剩下的节点组成的树为满二叉树,最后一层的节点从左到右连续,即所有的结点都连续集中在最左边。
这样的树称为完全二叉树。如图3是一棵完全二叉树。
满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树
二叉树的实现
因为一棵树有最多只有两个儿子,所以我们可以用指针直接指向他们。一个节点包括值(data)、指向左儿子的指针(lson)和指向右儿子的指针(rson)。
struct treenode { int data; struct treenode* lson; struct treenode* rson; }
二叉树的插入,删除,查找和链表差不多,不同的是需要指定是左儿子还是右儿子。
二叉树的数组实现也很简单,假如说根节点在arr[0]这个位置,那么它的左儿子就在arr[2*0+1],也就是arr[1]这个位置,它的右儿子在arr[2*0+2] ,也就是arr[2]这个位置。对于下标为i的节点来说,它的左儿子的下标为2*i+1,右儿子的下标为2*i+2。
二叉树的遍历
用被访问的结点N(Node)、L(Left subtree)和R(Right subtree)代表根、左子树和右子树。NLR、LNR和LRN分别又称为先序遍历、中序遍历和后序遍历。
先序遍历,最先读取根节点,然后左子树,最后右子树;
中序遍历,最先读取左子树,然后根节点,最后右子树;
后序遍历,最先读取左子树,然后右子树,最后根节点。
递归实现代码:
//先序遍历
void print1(treetp t)
{
if (t!=0)
{
printf("%d ",t->data);
print1(t->lchild);
print1(t->rchild);
}
}
//中序遍历
void print2(treetp t)
{
if (t!=0)
{
print2(t->lchild);
printf("%d ",t->data);
print2(t->rchild);
}
}
//后序遍历
void print3(treetp t)
{
if (t!=0)
{
print3(t->lchild);
print3(t->rchild);
printf("%d ",t->data);
}
}
转载于:https://www.cnblogs.com/li-hao/archive/2013/04/06/3002133.html