搜索
Java基本复习笔记08数据构造-二叉树和二叉树遍历刘岩Email:1.二叉树普通树限制比较少，因此才提出了具备特色二叉树概念。二叉树顾名思义，每个节点最多有两个子节点，分别叫做左子节点和右子节点。有了这个限定性后，就可以干诸多树不能干事情了。如果树所有层，除了最后一层节点外都是两个子节点，那么称这个树为满二叉树。如下图若设二叉树高度为h，除第h层外，其他各层(1～h-1)结点数都达到最大个数，第h层所有节点都持续集中在最左边，这就是完全二叉树。2.二叉树操作packagedateStructer.tree.binaryTree;/***顺序二叉树**@authorliuyan*/publicclassArrayBinaryTreeT{//树默认深度privatestaticfinalintDefTreeDeep=4;//节点数组privateObject[]datas;//指定树深度privateinttreeDeep;//实际数组个数privateintarraySize;/***默认构造函数*/publicArrayBinaryTree(){//设立默认树深度treeDeep=DefTreeDeep;二叉树具备为指定节点增长子节点操作、判断树与否为空、返回根节点、返回指定节点父节点，返回指定节点左子节点、返回指定节点右子节点、返回树深度、返回指定节点位置。3.二叉树延伸其实二叉树只是一种引子，计算机界诸多算法都是依照二叉树所展开，例如排序二叉树、红黑树、哈夫曼树、线索二叉树等等。4.顺序实现二叉树下面咱们来看看二叉树顺序实现方式，顺序实现二叉树就是运用数组存储所有二叉树节点。代码如下//2DefTreeDeep次方-1个数组元素arraySize=(int)Math.pow(2，DefTreeDeep)-1;datas=newObject[arraySize];}/***指定深度构建二叉树*@paramdeep*/publicArrayBinaryTree(intdeep){//按指定深度treeDeep=deep;arraySize=(int)Math.pow(2，treeDeep)-1;datas=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;}/***返回根节点**@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){thrownewRuntimeException(标记无效);}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([);publicstaticvoidmain(String[]args){ArrayBinaryTreeStringarrayBinaryTree=newArrayBinaryTreeString(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));}publicstaticvoidmain(String[]args){ArrayBinaryTreeStringarrayBinaryTree=newArrayBinaryTreeString(4,汉献帝);System.out.println(arrayBinaryTree);arrayBinaryTree.addNode(0，刘备，true);arrayBinaryTree.addNode(0，曹操，false);测试代码如下测试效果如下顺序实现是比较挥霍资源，可以看到数组没有元素位置都是null。如果将测试代码稍微变更一下，如下for(inti=0；idatas.length；i++){str.append([+datas[i]+],);}if(datas.length0){returnstr.substring(0，str.lastIndexOf(,))+];}returnstr.append(]).toString();}}packagedateStructer.tree.binaryTree;/***二叉链表二叉树**@authorliuyan*/publicclassTwoLinkedBinaryTreeT{//树默认深度privatestaticfinalintDefTreeDeep=4;//节点数组privateTwoLinkNodeT[]datas;//指定树深度运营效果如下可以看到数组中间资源挥霍得很严重。5.二叉链表实现二叉树为了弥补顺序实现空间挥霍问题，可以使用链表方式实现二叉树，但是链表又分为两种状况，一种是二叉链表，另一种稍后再说。二叉链表思想就是构造一种对象，记住它两个子节点，所谓记住两个子节点可以是子节点位置，可以是子节点实体对象。如果记录了位置，其实是离不开数组协助。如果记录了整个子节点对象，那么就可以完全脱离数组，完完全全，真真正正链表离散式存储。这次使用记录节点位置，算法如下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));}privateinttreeDeep;//实际数组个数privateintarraySize;//节点个数privateintnodeSize;/***二叉节点*/@SuppressWarnings(hiding)classTwoLinkNodeT{publicintleftChildIndex;publicintrightChildIndex;publicintindex;publicTdata;}@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;}/***为指定节点索引增长子节点**@paramindex*@paramdata*@paramisLeft*@return*/publicbooleanaddNode(intindex，Tdata，booleanisLef