当前位置: 首页 > >

数据结构二叉树

发布时间:



数据结构之二叉树
二叉树定义与特性基本概念结点分类二叉树的特点性质特例定理操作二叉树的存储结构:二叉查找树



二叉树
二叉树的定义与主要特性二叉树的实现及遍历(周游)二叉查找树(Binary search Tree)堆(Heap)霍夫曼(Huffman)编码树
定义与特性
一棵二叉树由结点的有限集合组成。或者由一个根结点以及两颗不相交的二叉树组成。这两颗二叉树分别称为这个根的左子树与右子树
基本概念
边子节点父节点路径路径长度祖先子孙结点深度:到根的路径长度+1;节点的层数:同深度;树的高度:最深节点的深度;叶节点:没有非空子树的结点,(度为0的结点)分支结点: 至少有一个非空子树,也称内结点(度不为0的结点)。结点的度:子结点的个数树的度:结点度的最大值;兄弟:同一个父节点的子节点之间互为兄弟;堂兄弟:父结点在同一层的结点互为堂兄弟。
空子树:即空,没有结点的树。
结点分类
叶结点、分支结点度为0、度为1、度为2的结点
二叉树的特点
每个结点最多有两颗子树。子树有左右之分,不能颠倒。
性质
在二叉树的第i层上的结点个数最多为2^(i-1)个(i>=1)。高度为m的二叉树最多有2^m-1个结点。对于任意一棵二叉树,度为0的结点,总比度为2的结点多一个。具有n个结点的二叉树的高度至少为 ?logn?+1,至多为n。
特例

满二叉树:每个节点要么是叶子节点,要么是有两个非空子节点的分支结点,即只有度为0和度为2的结点。


完全二叉树:一棵高度为d的完全二叉树除了d层以外,每一层都是满的;底层的叶子结点集中在左边的若干位置上。


定理
    满二叉树定理:非空满二叉树的叶节点等于其分支节点树+1;
    用途:分析二叉树的空间代价一棵非空二叉树空子树的数目等于其结点数+1
    (任一一棵非空二叉树的结点与其空子树的和就是一棵满二叉树。)
    用途:分析二叉树的空间代价时,知道有多少个空子树是很有用的。

操作
二叉树的操作
    结点的操作整棵树的操作,例如初始化、遍历

结点的基本操作
    获取结点的内容设置结点的内容获取左子树,获取右子树设置左子树,设右子树获取节点类型(叶还是分支)

按照一定的顺序访问二叉树的结点,称为一次周游或者遍历。
前序:中+左+右
后序:左+右+中
中序:左+中+右
结论:前序+中序;后序+中序可以唯一确定一棵二叉树前序+后序不能唯一的确定一棵二叉树。

practice:写出树的前序、中序以及后序遍历内容。


二叉树的存储结构:
顺序存储:利用数组实现,仅可存储完全二叉树。链式存储适合一般二叉树。

完全二叉树:


假设r表示结点的序号,范围:0-n-1,n为结点数。
    parent?=?(r-1)/2?;当r!=0时;leftchild?=2r+1 当2r+1

    根节点:序号为0;
    第一个叶节点序号:n/2;
    最后一个分支节点:n/2-1;


    链式二叉树:


    结点:
    数据域+两个指向子节点的指针;空间代价:
    二叉树的结点数为n;
    一个指针的空间大小为p;
    一个数据值的指针大小为d;
    那么一个简单的基于指针的二叉树所需要的总空间为n(2P+d);
    结构性开销为2pn,所占比例为2p/(2p+d)。
    从空树与节点数的关系角度可知,大约有一般的指针是空的。
    二叉查找树

    二叉查找树的特点
    左边的数值大小<根结点的数值大小<右边结点的数值大小。


    左子树上的所有结点值小于根节点值;
    右边树上的节点值大于等于根节点值;
    左右子树也满足上述条件。


    所以对二叉查找树进行中序遍历可以得到一个非递减序列。


    二叉查找树的构成
    二叉树结点的插入:


    第一个读入元素为根节点;小于根插入到左子树中,大于插入到右子树;依次读入后续元素进行上述过程。

    结论:


    新插入的结点总是在叶结点上二叉查找树只用改变叶结点即可。中序遍历二叉查找树后可以得到有序序列。无序序列构造二叉树的过程就是排序的过程。同一个无序序列,改变数据元素先后顺序后将得到不一样的二叉查找树。

    (待续)



友情链接: