C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

基本数据结构:二叉树(binary tree)

作者:C小加  更新时间:2012-8-6

二叉树首先是一棵树,每个节点都不能有多于两个的儿子,也就是树的度不能超过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。

二叉树的遍历

二叉树的遍历有三种,分别为先序遍历,中序遍历和后序遍历。这三种遍历方式是根据根节点的读取顺序来分的:

先序遍历,就是最先读取根节点,然后再读取左子树(按照同样的方法读取子树上的节点),最后读取右子树;

中序遍历,就是第二个读取根节点,最先要读取的是左子树,然后根节点,最后右子树;

后序遍历,就是最后一个读取根节点,最先读取的是左子树,第二个读取右子树,最后读取根节点。

先序遍历的递归实现代码:

void insubtree(struct treenode* tree)
{
       If(tree==NULL) return;
       cout<<tree->data;
    insubtree(tree->lson);
insubtree(tree->rson);
}

 

Feedback

# re: 基本数据结构:二叉树(binary tree)  回复  更多评论   

2012-08-06 15:52 by SunRise_at
支持一下....

# re: 基本数据结构:二叉树(binary tree)  回复  更多评论   

2012-08-08 16:56 by zinber
嗯,顶个先

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理