二叉树
链表实现利用数组建立二叉树整体代码实现直接添加元素，建立二叉排序树二叉树的搜索二叉运算树接下来实现二叉运算树前序遍历递归实现前序遍历非递归实现解法一解法二中序遍历递归实现中序遍历非递归实现后序遍历递归实现后序遍历非递归实现层序遍历递归实现层序遍历非递归实现线索化二叉树中序遍历线索化二叉树及其遍历先定义一个结点类实现中序线索化二叉树从后继节点开始遍历从前驱结点开始遍历先定义一个节点类前序线索化二叉树遍历前序线索化二叉树后序线索化二叉树后序线索化二叉树的节点类实现后序线索化二叉树遍历后序线索化二叉树数组实现添加元素,利用数组建立二叉搜索树遍历数组实现的二叉树整体代码实现
链表实现
先创建一个节点类
publicclassTeNode{intvalue;//数据TeNodeleft;//指向左子树TeNoderight;//指向右子树publicTeNode(){}publicTeNode(intvalue){this.value=value;left=null;right=null;}}
利用数组建立二叉树
利用递归一一将数组中的数全部存储到二叉树中建立二叉树
publicTeNodecate(char[]arr,intindex){if(index=arr.length){turnnull;}else{TeNodetmpNode=newTeNode((int)(arr[index]));tmpNode.left=cate(arr,*index);tmpNode.right=cate(arr,*index+);turntmpNode;}}
整体代码实现
```javapublicclassBinaryTe{publicTeNoderoot;publicTeNode(){}publicBinaryTe(char[]ch,intindex){root=cate(ch,index);}//将数组表示法转换为链表表示法publicTeNodecate(char[]arr,intindex){if(index=arr.length){turnnull;}else{TeNodetmpNode=newTeNode((int)(arr[index]));tmpNode.left=cate(arr,*index);tmpNode.right=cate(arr,*index+);turntmpNode;}}
直接添加元素，建立二叉排序树
publicvoidadd(intdata){TeNodenewNode=newTeNode(data);//建立树根if(root==null){root=newNode;turn;}TeNodecur=root;while(true){if(newNode.valuecur.value){if(cur.left==null){cur.left=newNode;turn;}else{cur=cur.left;}}else{if(cur.right==null){cur.right=newNode;turn;}else{cur=cur.right;}}}}
二叉树的搜索
可以看到二叉树的搜索是建立在二叉排序树的基础上
//查找该二叉树上是否含有该元素publicbooleanfindTeNode(TeNoderoot,intvalue){if(root==null){turnfalse;}else{if(root.value==value){turntrue;}else{if(valueroot.value){count++;turnfindTeNode(root.left,value);}else{count++;turnfindTeNode(root.right,value);}}}}
二叉运算树
先创建一个节点类
publicclassTeNode{intvalue;TeNodeleft;TeNoderight;publicTeNode(){}publicTeNode(intdata){this.value=data;left=null;right=null;}}
接下来实现二叉运算树
publicclassBinaryTe{publicTeNoderoot;publicBinaryTe(char[]ch,intindex){root=cate(ch,index);}//添加元素publicvoidadd(intdata){TeNodenewNode=newTeNode(data);if(root==null){root=newNode;turn;}TeNodecur=root;while(true){if(newNode.valuecur.value){if(cur.left==null){cur.left=newNode;turn;}else{cur=cur.left;}}else{if(cur.right==null){cur.right=newNode;turn;}else{cur=cur.right;}}}}//将数组表示法转换为链表表示法publicTeNodecate(char[]arr,intindex){if(index=arr.length){turnnull;}else{TeNodetmpNode=newTeNode((int)(arr[index]));tmpNode.left=cate(arr,*index);tmpNode.right=cate(arr,*index+);turntmpNode;}}//判断表达式如何运算的方法声明publicintcondition(charch,intn,intn){switch(ch){case+:turnn+n;case-:turnn-n;case*:turnn*n;case/:turnn/n;case%:turnn%n;default:turn-;}}//计算二叉运算树的值publicintanswer(TeNoderoot){intfirst=0;intsecond=0;if(root.left==nullroot.right==null){turnCharacter.getNumericValue((char)root.value);}else{first=answer(root.left);second=answer(root.right);turncondition((char)root.value,first,second);}}//中序表示法publicvoidinOrder(TeNoderoot){if(root!=null){inOrder(root.left);System.out.print((char)root.value+"");inOrder(root.right);}}//后序表示法publicvoidpostOrder(TeNoderoot){if(root!=null){postOrder(root.left);postOrder(root.right);System.out.print((char)root.value+"");}}//前序表示法publicvoidpOrder(TeNoderoot){if(root!=null){System.out.print((char)root.value+"");pOrder(root.left);pOrder(root.right);}}}
前序遍历递归实现
//前序遍历publicvoidpOrder(TeNoderoot){if(root!=null){System.out.print(root.value+"");pOrder(root.left);//遍历左子树pOrder(root.right);//遍历右子树}}
前序遍历非递归实现
解法一
利用堆栈的性质
//前序遍历非递归publicvoidpOrder(TeNodecur){StackTeNodestack=newStack();while(cur!=null
!stack.isEmpty()){while(cur!=null){stack.add(cur);System.out.print(cur.value+"");cur=cur.left;}cur=stack.pop();cur=cur.right;}}
解法二
将元素按照前序遍历的顺序压入栈中，再依次弹出即可
//前序遍历非递归publicvoidpOrder(TeNodecur){StackTeNodestack=newStack();stack.add(cur);while(!stack.isEmpty()){cur=stack.pop();System.out.print(cur.value+"");if(cur.right!=null)stack.add(cur.right);if(cur.left!=null)stack.add(cur.left);}}
中序遍历递归实现
//中序遍历publicvoidinOrder(TeNoderoot){if(root!=null){inOrder(root.left);//处理左子树System.out.print(root.value+"");inOrder(root.right);//处理右子树}}
中序遍历非递归实现
和前序遍历的非递归实现一样，只不过是交换了打印顺序。
//中序遍历非递归publicvoidinOrder(TeNodecur){StackTeNodestack=newStack();while(cur!=null
!stack.isEmpty()){while(cur!=null){stack.add(cur);cur=cur.left;}cur=stack.pop();System.out.print(cur.value+"");cur=cur.right;}}
后序遍历递归实现
//后序遍历publicvoidpostOrder(TeNoderoot){if(root!=null){postOrder(root.left);//处理左子树postOrder(root.right);//处理右子树System.out.print(root.value+"");}}
后序遍历非递归实现
后序遍历较为复杂，需要用到栈的性质，且用cur来判断打印树叶，用p来记录左或右节点来判断是否打印父节点
publicvoidpostOrder(TeNodecur){if(cur==null)turn;StackTeNodestack=newStack();TeNodep=null;stack.add(cur);while(!stack.isEmpty()){cur=stack.peek();if((cur.left==nullcur.right==null)
(p!=null(p==cur.left
p==cur.right))){System.out.print(cur.value+"");stack.pop();p=cur;}else{if(cur.right!=null)stack.add(cur.right);if(cur.left!=null)stack.add(cur.left);}}}
层序遍历递归实现
classSolution{publicListListIntegerlevelOrder(TeNoderoot){ListListIntegersult=newArrayListListInteger();helper(root,0,sult);turnsult;}publicvoidhelper(TeNoderoot,intlevel,ListListIntegerlists){if(root==null){turn;}if(lists.size()level+){lists.add(newArrayListInteger());}lists.get(level).add(root.val);helper(root.left,level+,lists);helper(root.right,level+,lists);}}
层序遍历非递归实现
利用队列先进先出的性质即可。
//层序遍历非递归publicvoidlevelOrder(TeNodecur){LinkedListTeNodequeue=newLinkedList();queue.add(cur);while(!queue.isEmpty()){cur=queue.pop();System.out.print(cur.value+"");if(cur.left!=null)queue.add(cur.left);if(cur.right!=null)queue.add(cur.right);}}
线索化二叉树
学过链表的读者肯定存在双向链表的，也就是节点相连两个节点之间相互指引，那么二叉树是否也可以通过特定的遍历方式变成特殊的“双向链表”呢？答案是肯定的。
我们选定一种遍历方式时，遍历到节点A时，所遍历到的前一个元素叫做节点A的前驱元素，遍历节点A过后，所遍历到的下一个元素叫节点A的后继节点。
中序遍历线索化二叉树及其遍历
先定义一个结点类
publicclassTeNode{intvalue;TeNodeleft;TeNoderight;booleanlef=false;booleanrig=false;publicTeNode(){}publicTeNode(intdata){this.value=data;left=null;right=null;}}
实现中序线索化二叉树
//中序线索化二叉树publicvoidinThadOrder(TeNoderoot){if(root==null){turn;}//处理左子树inThadOrder(root.left);if(root.left==null){root.left=p;root.lef=true;}//前一个节点的后继结点指向当前节点if(p!=nullp.right==null){p.right=root;p.rig=true;}p=root;inThadOrder(root.right);}
从后继节点开始遍历
//中序遍历线索二叉树，按照后继方式遍历publicvoidinOrderBlack(){TeNodecur=root;while(cur!=null!cur.lef){cur=cur.left;}while(cur!=null){System.out.print(cur.value+"");if(cur.rig){cur=cur.right;}else{cur=cur.right;while(cur!=null!cur.lef)cur=cur.left;}}}
从前驱结点开始遍历
//中序遍历线索二叉树，按照前驱方式遍历publicvoidinOrderBefo(){TeNodecur=root;while(cur.right!=null!cur.rig)cur=cur.right;while(cur!=null){System.out.print(cur.value+"");if(cur.lef){cur=cur.left;}else{cur=cur.left;while(cur.right!=null!cur.rig)cur=cur.right;}}}
先定义一个节点类
publicclassTeNode{intvalue;TeNodeleft;TeNoderight;booleanlef=false;booleanrig=false;publicTeNode(){}publicTeNode(intdata){this.value=data;left=null;right=null;}}
前序线索化二叉树
//前序遍历线索化二叉树publicvoidpOrderBinaryT(TeNoderoot){if(root==null)turn;//左指针为空，将左指针指向前驱节点if(root.left==null){root.left=p;root.lef=true;}//将前一个节点的后继节点指向当前节点if(p!=nullp.right==null){p.right=root;root.rig=true;}p=root;if(!root.lef)pOrderBinaryT(root.left);if(!root.rig)pOrderBinaryT(root.right);}
遍历前序线索化二叉树
//前序遍历线索二叉树publicvoidpOrderblack(){TeNodecur=root;while(cur!=null){while(!cur.lef){System.out.println(cur.value+"");cur=cur.left;}System.out.println(cur.value+"");cur=cur.right;}}
后序线索化二叉树
后序线索化二叉树的节点类
后序线索化二叉树创建的节点类，与前面有所不同，需要一个pant记录父节点
publicclassTeNode{intvalue;TeNodeleft;TeNoderight;TeNodepant;booleanlef=false;booleanrig=false;publicTeNode(){}publicTeNode(intdata){this.value=data;left=null;right=null;}}
实现后序线索化二叉树
//后序遍历线索化二叉树publicvoidpostThadOrder(TeNoderoot){if(root==null)turn;//处理左子树postThadOrder(root.left);//处理右子树postThadOrder(root.right);if(root.left==null){root.left=p;root.lef=true;}if(p!=nullp.right==null){p.right=root;p.rig=true;}p=root;}
遍历后序线索化二叉树
//遍历后序遍历线索化的二叉树publicvoidpostOrderBinaryTe(){p=null;TeNodecur=root;while(cur!=null!cur.lef)cur=cur.left;while(cur!=null){if(cur.lef){System.out.println(cur.value+"");p=cur;cur=cur.right;}else{if(cur.right==p){System.out.println(cur.value+"");if(cur==root)turn;p=cur;cur=cur.pant;}else{if(cur==rootcur.right==null)turn;cur=cur.right;while(cur!=null!cur.lef)cur=cur.left;}}}}
数组实现
通数组的下标一样，可以将二叉树的各节点下标化
添加元素,利用数组建立二叉搜索树
可以发现规律，左子树索引值为父节点索引值+右子树索引值为父节点索引值+故有：
//添加元素publicvoidadd(){intlevel=;for(inti=0;idata.length;i++){for(level=;bte[level]!=0;){if(databte[level])level=level*;elselevel=level*+;}bte[level]=data;}}
遍历数组实现的二叉树
因为数组是连续存储的，所以直接打印就行。
//遍历二叉树publicvoidergodic(){System.out.println("二叉树的内容");for(inti=;ibte.length;i++)System.out.print(bte+"");System.out.println();}
整体代码实现
publicclassBinaryTeByArray{int[]data;int[]bte=newint[00];publicBinaryTeByArray(int[]arr){data=arr;}//添加元素publicvoidadd(){intlevel=;for(inti=0;idata.length;i++){for(level=;bte[level]!=0;){if(databte[level])level=level*;elselevel=level*+;}bte[level]=data;}}//遍历二叉树publicvoidergodic(){System.out.println("二叉树的内容");for(inti=;ibte.length;i++)System.out.print(bte+"");System.out.println();}}
,