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

1/19Java基础复习笔记08数据结构-二叉树和二叉树的遍历刘岩Email:[e-mail]1.二叉树一般的树限制比较少，所以才提出了具有特色的二叉树的概念。二叉树顾名思义，每个节点最多有两个子节点，分别叫做左子节点和右子节点。有了这个限定性后，就可以干很多树不能干的事情了。如果树的所有层，除了最后一层的节点外都是两个子节点，那么称这个树为满二叉树。如下图若设二叉树的高度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树。2.二叉树的操作二叉树具有为指定节点增加子节点操作、判断树是否为空、返回根节点、返回指定节点的父节点，返回指定节点的左子节点、返回指定节点的右子节点、返回树的深度、返回指定节点的位置。3.二叉树的延伸其实二叉树只是一个引子，计算机界很多的算法都是根据二叉树所展开的，比如排序二叉树、红黑树、哈夫曼树、线索二叉树等等。2/194.顺序实现二叉树下面我们来看看二叉树的顺序实现方式，顺序实现二叉树就是利用数组存储所有的二叉树的节点。代码如下packagedateStructer.tree.binaryTree;/***顺序二叉树**@authorliuyan*/publicclassArrayBinaryTreeT{//树的默认深度privatestaticfinalintDefTreeDeep=4;//节点数组privateObject[]datas;//指定的树的深度privateinttreeDeep;//实际的数组个数privateintarraySize;/***默认构造函数*/publicArrayBinaryTree(){//设置默认的树深度treeDeep=DefTreeDeep;//2的DefTreeDeep次方-1个数组元素arraySize=(int)Math.pow(2,DefTreeDeep)-1;datas=newObject[arraySize];}/***指定深度构建二叉树*@paramdeep*/publicArrayBinaryTree(intdeep){//按指定深度treeDeep=deep;arraySize=(int)Math.pow(2,treeDeep)-1;3/19datas=newObject[arraySize];}/***指定深度和指定根节点构建二叉树*@paramdeep*@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,booleanisLeft){if(index*2+2arraySize||datas[index]==null){thrownewRuntimeException(标记无效);}if(isLeft){datas[index*2+1]=data;}else{datas[index*2+2]=data;}returntrue;}/***判断二叉树是否为空**@return*/publicbooleanisEmpty(){returnarraySize==0;}4/19/***返回根节点**@return*/@SuppressWarnings(unchecked)publicTgetRoot(){return(T)datas[0];}/***返回指定节点的父节点*@return*/@SuppressWarnings(unchecked)publicTgetParent(intindex){if(indexarraySize||datas[index]==null){thrownewRuntimeException(标记无效);}if(datas[(index-1)/2]==null){thrownewRuntimeException(无父节点);}return(T)datas[(index-1)/2];}/***返回左子节点*@return*/@SuppressWarnings(unchecked)publicTgetLeftNode(intindex){if(index*2+2arraySize||datas[index]==null){thrownewRuntimeException(标记无效);}return(T)datas[index*2+1];}/***返回右子节点*@return*/@SuppressWarnings(unchecked)publicTgetRightNode(intindex){if(index*2+2arraySize||datas[index]==null){5/19thrownewRuntimeException(标记无效);}return(T)datas[index*2+2];}/***返回树的深度*@return*/publicintgetTreeDeep(){returntreeDeep;}/***返回指定节点的索引位置*@paramdata*@return*/publicintgetNodeIndex(Tdata){for(inti=0;iarraySize;i++){if(data==datas[i]){returni;}}return-1;}@OverridepublicStringtoString(){StringBufferstr=newStringBuffer([);for(inti=0;idatas.length;i++){str.append([+datas[i]+],);}if(datas.length0){returnstr.substring(0,str.lastIndexOf(,))+];}returnstr.append(]).toString();}}测试代码如下publicstaticvoidmain(String[]args){ArrayBinaryTreeStringarrayBinaryTree=new6/19ArrayBinaryTreeString(4,汉献帝);System.out.println(arrayBinaryTree);arrayBinaryTree.addNode(0,刘备,true);arrayBinaryTree.addNode(0,曹操,false);arrayBinaryTree.addNode(1,关羽,true);arrayBinaryTree.addNode(1,张飞,false);arrayBinaryTree.addNode(2,张辽,true);arrayBinaryTree.addNode(2,许褚,false);System.out.println(arrayBinaryTree);System.out.println(arrayBinaryTree.getLeftNode(1));System.out.println(arrayBinaryTree.getRightNode(0));System.out.println(arrayBinaryTree.isEmpty());System.out.println(arrayBinaryTree.getParent(4));}测试效果如下顺序实现是比较浪费资源的，可以看到数组没有元素的位置都是null。如果将测试代码稍微变更一下，如下publicstaticvoidmain(String[]args){ArrayBinaryTreeStringarrayBinaryTree=newArrayBinaryTreeString(4,汉献帝);System.out.println(arrayBinaryTree);arrayBinaryTree.addNode(0,刘备,true);arrayBinaryTree.addNode(0,曹操,false);arrayBinaryTree.addNode(2,张辽,true);arrayBinaryTree.addNode(2,许褚,false);arrayBinaryTree.addNode(6,李典,true);arrayBinaryTree.addNode(6,乐进,false);System.out.println(arrayBinaryTree);System.out.println(arrayBinaryTree.getLeftNode(2));System.out.println(arrayBinaryTree.getRightNode(0));System.out.println(arrayBinaryTree.isEmpty());System.out.println(arrayBinaryTree.getParent(14));}运行效果如下可以看到数组中间资源浪费得很严重。7/195.二叉链表实现二叉树为了弥补顺序实现的空间浪费问题，可以使用链表方式实现二叉树，但是链表又分为两种情况，一种是二叉链表，另一种稍后再说。二叉链表的思想就是构造一个对象，记住它的两个子节点，所谓记住两个子节点可以是子节点的位置，可以是子节点的实体对象。如果记录了位置，其实是离不开数组的帮助的。如果记录了整个子节点对象，那么就可以完全脱离数组，完完全全，真真正正的链表离散式存储。这次使用记录节点位置，算法如下packagedateStructer.tree.binaryTree;/***二叉链表二叉树**@authorliuyan*/publicclassTwoLinkedBinaryTreeT{//树的默认深度privatestaticfinalintDefTreeDeep=4;//节点数组privateTwoLinkNodeT[]datas;//指定的树的深度privateinttreeDeep;//实际的数组个数privateintarraySize;//节点个数privateintnodeSize;/***二叉节点*/@SuppressWarnings(hiding)classTwoLinkNodeT{publicintleftChildIndex;publicintrightChildIndex;publicintindex;publicTdata;8/19}@SuppressWarnings(unchecked)publicTwoLinkedBinaryTree(){treeDeep=DefTreeDeep;arraySize=(int)Math.pow(2,treeDeep)-1;datas=newTwoLinkNode[arraySize];}@SuppressWarnings(unchecked)publicTwoLinkedBinaryTree(intdeep,Tdata){treeDeep=DefTreeDeep;arraySize=(int)Math.pow(2,treeDeep)-1;datas=newTwoLinkNode[arraySize];TwoLinkNodeTtwoLinkNode=newTwoLinkNodeT();twoLinkNode.data=data;twoLinkNode.leftChildIndex=1;twoLinkNode.rightChildIndex=2;twoLinkNode.index=0;datas[0]=twoLinkNode;nodeSize=1;}/***为指定节