MyException - 我的异常网
当前位置:我的异常网» 编程 » 二叉树(1)——二叉树的基本实现(数组实现和链表

二叉树(1)——二叉树的基本实现(数组实现和链表实现)

www.MyException.Cn  网友分享于:2014-08-06  浏览:0次
二叉树(一)——二叉树的基本实现(数组实现和链表实现)
1.树是一种数据结构,树的一些相关的术语:
结点的度:一个结点的后继结点的个数。
树的度:树中度值最大的结点的度被称为树的度。
树的深度:树的层次数。
分支结点:度值大于0的结点,分支结点至少含有一个后继,分支结点也称为非终端结点。
叶子结点:树中的度值为0的结点。
双亲结点:树中某个结点的前驱结点,也成为父节点。
子女结点:树中某结点的后继结点。
兄弟结点:树中同一层的结点。
2.二叉树
(1)二叉树是一种特殊的树,树的度值最大为2.
(2)二叉树的表示:
           A
         /      \
       B        C
      /     \     /   \
     D   E   F   G
二元表示:
Binary-tree = (D, S)

D={A, B, C, D, E, F, G}

S={<A,B>, <A,C>, <B,D>, <B,E>, <C,F>, <C,G>}

3.二叉树的特点
(1)任何一棵二叉树的叶子结点总比双分支结点个数多一个。
分别设叶子结点,单分子结点,双分子结点的个数为:n0, n1, n2,则有:
n0+n1+n2 = 2n2+n1+1 ==>  n0 = n2+1
2n2+n1+1:n2结点每个节点有两个叶子节点,n1结点每个结点有一个叶子结点,+1的原因是根结点不属于任何一个结点的子节点,所以根结点需要单独加上。
(2)二叉树的第i层最多有2^(i-1)个元素。
(3)一棵h层的二叉树最多有2^h - 1个元素。
4.满二叉树:h层的二叉树共有2^h - 1个元素。
完全二叉树:h层的二叉树若前h-1层是满的,最后一层是连续缺失右边的若干个结点。
对于完全二叉树存在:
(1)若结点编号为i的结点存在左子女,左子女编号为2i,若存在右子女,则右子女的结点编号为2i+1。
(2)编号为i的结点若存在双亲结点,则双亲结点的编号为i/2向下取整。
5.理想平衡二叉树:一棵h层的二叉树前h-1层是满的,最后一层的叶子结点可任意摆放。
二叉树存储的实现:
(1)顺序存储:将二叉树存储在内存中一块连续的存储单元中,数组的元素个数取决于二叉树的层数。
(2)将二叉树的每个结点的编号作为该结点在数组中的存储下标。
(3)将根节点存放在下标为1的单元里。
(4)若下标为i的单元存在左子女,则左子女的下标为2i,若存在右子女,右子女的下标为2i+1。
6.中根查找顺序
对于一个给定的二叉树,如果要对其进行遍历可以有前序遍历、中序遍历、后序遍历基本的三种遍历方式,这三种遍历方式都是相对于根而言的。比如中序遍历,就是先访问左子树,再访问根,最后访问右子树,意思就是根的访问顺序在中间。
对于一棵给定的二叉树:

中序遍历的顺序为:10, 42, 45, 55, 58, 63, 67, 70, 83, 90, 98。
从这个遍历顺序可以看出正好是一个从小到大的排过序的顺序,这是在构建二叉树的时候就可以做到的,在构建二叉树的时候,选择好根节点,比根节点小的数放到根节点的左子树,比根节点大的数放到根节点的右子树即可。
例如给出一个序列:63, 42, 45, 67, 70。
访问到63,将其作为根节点,访问到42<63则作为63的左子树,访问到45<63放到63的左子树上,而45>42所以放到42的右子树上,访问到67>63,则将67作为63的右子树,访问到70>63应该放在63的右子树上,而进一步有70>67,则70应该作为67的右子树,所以可以得到下面的二叉树:
                        63
                      /    \
                    42      67
                      \       \
                       45      70
7.二叉树的链式存储
结点类型:left域、data域、right域
left域:用来存放左子女的地址,若不存在左子女,left域为空。
data域:用来存放该结点的数据。
right域:用来存放右子女的地址,若不存在右子女,right域为空。
8.二叉搜索树

若树中左子女的值都小于根节点的值,右子女的值都大于根节点的值,这样的二叉树叫做二叉搜索树。

9.二叉树的数组实现方式

分析:首先给定一个二叉树之后,就可以知道该二叉树的层次数h,然后创建一个2^h = 2^h - 1 + 1个元素的数组,加1的目的是因为数组的0下标是不用的,根节点存放在下标为1的单元中。所有数组中没有用到的单元,均赋值为二叉树中数值域不包含的值,这样在遍历的时候就可以将这个值作为判断的依据。

#include <stdio.h>

void create_btree(int list[], int bt[], int n) /*n表示list数组中元素的个数*/
{
	int i, order;

	bt[1] = list[0];
	for(i = 1; i < n; i++)
	{
		order = 1; /*每次进来从根结点开始比较*/
		while(bt[order] != 0)
		{
			if(list[i] < bt[order])
				order *= 2;
			else
				order = order*2 + 1;
		}
		bt[order] = list[i];
	}
}

int main()
{
	int list[7] = {30, 18, 16, 25, 34, 7, 31};
	int bt[16] = {0};
	int i;

	create_btree(list, bt, 7);
	for(i = 0; i < 16; i++) /*按层输出*/
		if(bt[i] != 0)
			printf("%4d", bt[i]);
	printf("\n");

	return 0;
}
程序的输出结果:


二叉树的链表实现:

#include <stdio.h>
#include <malloc.h>

#define NULL	0

typedef struct tree
{
	int data;
	struct tree *left, *right;
}ElemBT;

void create_btree(ElemBT *root, int list[], int n) /*n表示list数组中元素的个数*/
{
	int i;
	ElemBT *current, *parent, *p;

	for(i = 1; i < n; i++)
	{
		p = (ElemBT *)malloc(sizeof(ElemBT));
		p->left = p->right = NULL;
		p->data = list[i];
		current = root;
		while(current != NULL)
		{
			parent = current;
			if(current->data > p->data)
				current = current->left;
			else
				current = current->right;
		}
		if(parent->data > p->data)
                        parent->left = p;
                else
                        parent->right = p;
         }
}

int main()
{
	int list[7] = {30, 18, 16, 25, 34, 7, 31};
	ElemBT *root;

	root = (ElemBT *)malloc(sizeof(ElemBT));
	root->data = list[0];
	root->left = root->right = NULL;
	create_btree(root, list, 7);

	return 0;
}


文章评论

程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
如何成为一名黑客
如何成为一名黑客
鲜为人知的编程真相
鲜为人知的编程真相
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
我是如何打败拖延症的
我是如何打败拖延症的
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
老程序员的下场
老程序员的下场
Java程序员必看电影
Java程序员必看电影
旅行,写作,编程
旅行,写作,编程
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
代码女神横空出世
代码女神横空出世
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
一个程序员的时间管理
一个程序员的时间管理
编程语言是女人
编程语言是女人
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
中美印日四国程序员比较
中美印日四国程序员比较
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
 程序员的样子
程序员的样子
程序员必看的十大电影
程序员必看的十大电影
那些争议最大的编程观点
那些争议最大的编程观点
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
每天工作4小时的程序员
每天工作4小时的程序员
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员应该关注的一些事儿
程序员应该关注的一些事儿
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
漫画:程序员的工作
漫画:程序员的工作
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员的鄙视链
程序员的鄙视链
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
总结2014中国互联网十大段子
总结2014中国互联网十大段子
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员都该阅读的书
程序员都该阅读的书
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
我的丈夫是个程序员
我的丈夫是个程序员
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员和编码员之间的区别
程序员和编码员之间的区别
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有