数据结构---二叉树的各种经典算法

<>1：统计二义树中度为1的结点个数、统计二叉树中度为2的结点个数、统计二叉树中度为0的结点个数。
package com.company; public class Tree { int val; Tree lChild; Tree rChild;
public Tree(){ val=0; rChild=null; lChild=null; } public Tree(int value){ this.
val=value; lChild=null; rChild=null; } } public class Main { private static
Tree T; private static int degreeOne; private static int degreeZero; private
static int degreeTwo; public static void main(String[] args){ T=new Tree(10);
createTree(); countDegreeZero(T); countDegreeOne(T); countDegreeTwo(T); System.
out.println("度为0的结点个数："+degreeZero); System.out.println("度为1的结点个数："+degreeOne);
System.out.println("度为2的结点个数："+degreeTwo); } public static void createTree(){ T.
lChild=new Tree(2); T.rChild=new Tree(4); T.lChild.lChild=new Tree(7); T.lChild.
rChild=new Tree(9); T.lChild.lChild.lChild=new Tree(6); T.rChild.rChild=new Tree
(3); } public static void countDegreeZero(Tree p){ if(p!=null){ if(p.lChild==
null&&p.rChild==null){ //System.out.println("值为："+p.val+" 的结点的度为0"); degreeZero
++; } countDegreeZero(p.lChild); countDegreeZero(p.rChild); } } public static
void countDegreeOne(Tree p){ if(p!=null){ if((p.lChild==null&&p.rChild!=null)||(
p.rChild==null&&p.lChild!=null)){ //System.out.println("值为："+p.val+" 的结点的度为1");
degreeOne++; } countDegreeOne(p.lChild); countDegreeOne(p.rChild); } } public
static void countDegreeTwo(Tree p){ if(p!=null){ if(p.lChild!=null&&p.rChild!=
null){ //System.out.println("值为："+p.val+" 的结点的度为2"); degreeTwo++; }
countDegreeTwo(p.lChild); countDegreeTwo(p.rChild); } } }
<>2.统计二叉树的高度。

用递归最方便
public static int heightTree(Tree p){ if(p!=null){ return max(heightTree(p.
lChild),heightTree(p.rChild))+1; } else{ return 0; } }
<>3.统计二叉树的宽度
public static int calHeightTree(Tree p){ int firstLocation=0; int lastLocation=
0; int preLastLocation=0; Tree []layerNode=new Tree[10]; int maxNum=0;
//采用层次遍历的方法 layerNode[++lastLocation]=T; preLastLocation=lastLocation;
firstLocation=lastLocation; boolean flag=true; while(flag) { while (
firstLocation<= preLastLocation) { p = layerNode[firstLocation]; System.out.
print(p.val+" "); if (p.lChild != null) { layerNode[++lastLocation] = p.lChild;
} if (p.rChild != null) { layerNode[++lastLocation] = p.rChild; } firstLocation
++; //表示当前p结点访问过; } int length=lastLocation-firstLocation+1; maxNum=maxNum>
length? maxNum:length; preLastLocation=lastLocation; if(preLastLocation<
firstLocation){ flag=false; } } return maxNum; }
<>4.从二叉树中删去所有叶结点
public static void deleteLeafNodes(Tree p,Tree pre){ if(p!=null){ if(p.rChild==
null&&p.lChild==null&&pre!=null){ if(pre.lChild==p){ pre.lChild=null; } else if(
pre.rChild==p){ pre.rChild=null; } System.out.println("叶子结点:"+p.val+"删除！"); }
deleteLeafNodes(p.lChild,p); deleteLeafNodes(p.rChild,p); } }
<>5.计算指定结点*p所在的层次

//Tree p是树根结点，Tree node是指定要查找层次的结点,deep是当前访问的结点的层次。
//Tree p是树根结点，Tree node是指定要查找层次的结点,deep是当前访问的结点的层次。 public static int
calConcreteLayer(Tree p,Tree node,int deep){ if(p!=null){ deep++; if(p==node){
return deep; } else{ int deep1=calConcreteLayer(p.lChild,node,deep); int deep2=
calConcreteLayer(p.rChild,node,deep); return deep1==0?deep2:deep1; } } else{
return 0; } }
<>6.计算二叉树中各结点中的最大元素的值。
public static int findMaxValue(Tree p){ if(p!=null){ int maxLChild=findMaxValue
(p.lChild); int maxRChild=findMaxValue(p.rChild); int Max=max(maxLChild,
maxRChild); return p.val>Max? p.val:Max; } else{ return 0; } }
<>7.交换二叉树中每个结点的两个子女。
public static void exchangeNodes(Tree p){ if(p!=null){ if(p.lChild!=null&&p.
rChild!=null){ Tree temp; temp=p.lChild.lChild; p.lChild.lChild=p.rChild.lChild;
p.rChild.lChild=temp; temp=p.lChild.rChild; p.lChild.rChild=p.rChild.rChild; p.
rChild.rChild=temp; temp=p.lChild; p.lChild=p.rChild; p.rChild=temp; }
exchangeNodes(p.lChild); exchangeNodes(p.rChild); } }
<>8.以先序次序输出一颗二叉树中所有结点的数据值及结点所在的层次。
public static void PTR(Tree p,int deep){ if(p!=null){ deep++; System.out.
println("该结点值为："+p.val+" ,层次为："+deep); PTR(p.lChild,deep); PTR(p.rChild,deep); }
}
<>8.输入一个整数 data 和一棵二元树。从树的根结点开始往下访问一直到叶结点，所经过的所有结点形成一条路径。打印出路径及与 data 相等的所有路径。

例如，输入整数22 和右图所示的二元树，则打印出两条路径 10，12和10，5，7。

这里我原本用的ArrayList去存储当前路径的结点，但是我发现java中的引用太神奇了，递归到上一层但是下一层对ArrayList的操作依旧存在。。。，所以改用数组外加length固定当前数组得范围。
public static void main(String[] args) { T=new Tree(10); createTree(); Tree []
arrayNode=new Tree[5]; int sum=0; int data=22; int length=0; findPathLengthSame(
T,arrayNode,length,sum,data); } public static void findPathLengthSame(Tree p,
Tree[] arrayNode,int length,int sum,int data){ //采用先序遍历 if(p!=null){ arrayNode[
length++]=p; sum+=p.val; if(p.rChild==null&&p.lChild==null){ if(sum==data) {
showPath(arrayNode,length); } sum-=p.val; length--; //去掉最后一个 }
findPathLengthSame(p.lChild,arrayNode,length,sum,data); findPathLengthSame(p.
rChild,arrayNode,length,sum,data); } } public static void showPath(Tree[]
arrayList,int length){ System.out.print("路径为："); for(int i=0;i<length;i++){
System.out.print(arrayList[i].val+" "); } System.out.println(); }

• « 上一篇：python 实验六 列表与元组（上）
• » 下一篇：使用Ansible批量部署SSH免密登录远程主机