java基础复习笔记08数据结构-二叉树和二叉树的遍历

《java基础复习笔记08数据结构-二叉树和二叉树的遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Java基础复习笔记08数据结构-二叉树和二叉树的遍历刘岩Email:suhuanzheng7784877@163.com1.二叉树一般的树限制比较少，所以才提出了具有特色的二叉树的概念。二叉树顾名思义，每个节点最多有两个子节点，分别叫做左子节点和右子节点。有了这个限定性后，就可以干很多树不能干的事情了。如果树的所有层，除了最后一层的节点外都是两个子节点，那么称这个树为满二叉树。如下图若设二叉树的高度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树。2.二叉树的操作二叉树具有为指定节点增加子节点操作、判断树是否为空、返回根节

2、点、返回指定节点的父节点，返回指定节点的左子节点、返回指定节点的右子节点、返回树的深度、返回指定节点的位置。3.二叉树的延伸其实二叉树只是一个引子，计算机界很多的算法都是根据二叉树所展开的，比如排序二叉树、红黑树、哈夫曼树、线索二叉树等等。19/191.顺序实现二叉树下面我们来看看二叉树的顺序实现方式，顺序实现二叉树就是利用数组存储所有的二叉树的节点。代码如下packagedateStructer.tree.binaryTree;/***顺序二叉树**@authorliuyan*/publicclassArrayBinaryTree{//树的默认深度privatestaticfinal

3、intDefTreeDeep=4;//节点数组privateObject[]datas;//指定的树的深度privateinttreeDeep;//实际的数组个数privateintarraySize;/***默认构造函数*/publicArrayBinaryTree(){//设置默认的树深度treeDeep=DefTreeDeep;//2的DefTreeDeep次方-1个数组元素arraySize=(int)Math.pow(2,DefTreeDeep)-1;datas=newObject[arraySize];}/***指定深度构建二叉树*@paramdeep*/publicArrayB

4、inaryTree(intdeep){//按指定深度treeDeep=deep;arraySize=(int)Math.pow(2,treeDeep)-1;19/19datas=newObject[arraySize];}/***指定深度和指定根节点构建二叉树*@paramdeep*@paramdata*/publicArrayBinaryTree(intdeep,Tdata){//按指定深度treeDeep=deep;arraySize=(int)Math.pow(2,treeDeep)-1;datas=newObject[arraySize];datas[0]=data;}/***为指定

5、节点索引增加子节点*@paramindex*@paramdata*@paramisLeft*@return*/publicbooleanaddNode(intindex,Tdata,booleanisLeft){if(index*2+2>arraySize

6、

7、datas[index]==null){thrownewRuntimeException("标记无效");}if(isLeft){datas[index*2+1]=data;}else{datas[index*2+2]=data;}returntrue;}/***判断二叉树是否为空**@return*/publicbooleanisEm

8、pty(){returnarraySize==0;}19/19/***返回根节点**@return*/@SuppressWarnings("unchecked")publicTgetRoot(){return(T)datas[0];}/***返回指定节点的父节点*@return*/@SuppressWarnings("unchecked")publicTgetParent(intindex){if(index>arraySize

9、

10、datas[index]==null){thrownewRuntimeException("标记无效");}if(datas[(index-1)/2]==null

11、){thrownewRuntimeException("无父节点");}return(T)datas[(index-1)/2];}/***返回左子节点*@return*/@SuppressWarnings("unchecked")publicTgetLeftNode(intindex){if(index*2+2>arraySize

12、

13、datas[index]==null){thrownewRuntimeExc