欢迎来到天天文库
浏览记录
ID:15081236
大小:163.50 KB
页数:19页
时间:2018-08-01
《java基础复习笔记数据结构-二叉树和二叉树的遍历》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、Java基础复习笔记08数据结构-二叉树和二叉树的遍历刘岩Email:suhuanzheng7784877@163.com1.二叉树一般的树限制比较少,所以才提出了具有特色的二叉树的概念。二叉树顾名思义,每个节点最多有两个子节点,分别叫做左子节点和右子节点。有了这个限定性后,就可以干很多树不能干的事情了。如果树的所有层,除了最后一层的节点外都是两个子节点,那么称这个树为满二叉树。如下图若设二叉树的高度为h,除第h层外,其它各层(1~h-1)的结点数都达到最大个数,第h层所有的节点都连续集中在最左边,这就是完全二叉
2、树。2.二叉树的操作二叉树具有为指定节点增加子节点操作、判断树是否为空、返回根节点、返回指定节点的父节点,返回指定节点的左子节点、返回指定节点的右子节点、返回树的深度、返回指定节点的位置。3.二叉树的延伸其实二叉树只是一个引子,计算机界很多的算法都是根据二叉树所展开的,比如排序二叉树、红黑树、哈夫曼树、线索二叉树等等。19/191.顺序实现二叉树下面我们来看看二叉树的顺序实现方式,顺序实现二叉树就是利用数组存储所有的二叉树的节点。代码如下packagedateStructer.tree.binaryTree;/*
3、**顺序二叉树**@authorliuyan*/publicclassArrayBinaryTree{//树的默认深度privatestaticfinalintDefTreeDeep=4;//节点数组privateObject[]datas;//指定的树的深度privateinttreeDeep;//实际的数组个数privateintarraySize;/***默认构造函数*/publicArrayBinaryTree(){//设置默认的树深度treeDeep=DefTreeDeep;//2的DefTree
4、Deep次方-1个数组元素arraySize=(int)Math.pow(2,DefTreeDeep)-1;datas=newObject[arraySize];}/***指定深度构建二叉树*@paramdeep*/publicArrayBinaryTree(intdeep){//按指定深度treeDeep=deep;arraySize=(int)Math.pow(2,treeDeep)-1;19/19datas=newObject[arraySize];}/***指定深度和指定根节点构建二叉树*@paramde
5、ep*@paramdata*/publicArrayBinaryTree(intdeep,Tdata){//按指定深度treeDeep=deep;arraySize=(int)Math.pow(2,treeDeep)-1;datas=newObject[arraySize];datas[0]=data;}/***为指定节点索引增加子节点*@paramindex*@paramdata*@paramisLeft*@return*/publicbooleanaddNode(intindex,Tdata,booleani
6、sLeft){if(index*2+2>arraySize
7、
8、datas[index]==null){thrownewRuntimeException("标记无效");}if(isLeft){datas[index*2+1]=data;}else{datas[index*2+2]=data;}returntrue;}/***判断二叉树是否为空**@return*/publicbooleanisEmpty(){returnarraySize==0;}19/19/***返回根节点**@return*/@Suppres
9、sWarnings("unchecked")publicTgetRoot(){return(T)datas[0];}/***返回指定节点的父节点*@return*/@SuppressWarnings("unchecked")publicTgetParent(intindex){if(index>arraySize
10、
11、datas[index]==null){thrownewRuntimeException("标记无效");}if(datas[(index-1)/2]==null){thrownewRuntimeEx
12、ception("无父节点");}return(T)datas[(index-1)/2];}/***返回左子节点*@return*/@SuppressWarnings("unchecked")publicTgetLeftNode(intindex){if(index*2+2>arraySize
13、
14、datas[index]==null){thrownewRuntimeExc
此文档下载收益归作者所有