赞
踩
ps:这里只讲解二叉树的主要方法的实现过程,内容比较进阶,不讲解二叉树的基本知识!!!!
static class TreeNode { public char value; public TreeNode left; public TreeNode right; public TreeNode(char value) { this.value=value; } } public TreeNode newTree() { TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); TreeNode G = new TreeNode('G'); TreeNode H = new TreeNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; return A; }
由代码可知,我们创建的二叉树的结构如下图
以下代码基本都用到了递归思想
前序遍历的核心思想就是 根 左 右
先打印根,再打印左,再打印右
如果我们的树是一颗很庞大的树,可以把大问题小化,比如上面那个树有8个结点,我们可以只看前三个,也就是
打印出来A之后,递归打印左树B,然后再打印右树C
现在结合代码来看
看不清的可以放大来看
这个是三个结点的思想画法,多个结点也这样画,可以自己动手画一下
public void prevOrder(TreeNode root)
{
if(root==null)
{
return;
}
System.out.print(root.value+" ");
prevOrder(root.left);
prevOrder(root.right);
}
画法同前序遍历
public void inOrder(TreeNode root)
{
if(root==null)
{
return;
}
inOrder(root.left);
System.out.print(root.value+" ");
inOrder(root.right);
}
画法同前序遍历和中序遍历
public void postOrder(TreeNode root)
{
if(root==null)
{
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.value+" ");
}
还是拿三个结点举例,你可以换成两个结点,递归的思想就是把大的换成一个个小的,比如那个从A到H的树,往大了说就是包括根节点A,以及A的左树和A的右树,这个三个结点的也是根节点A和A的左树B和A的右树C
计算二叉树的节点个数可以想成 根结点+左树的结点个数+右树的结点个数
下面结合代码来看一下
public int size(TreeNode root)
{
if(root==null)
{
return 0;
}
return 1+size(root.left)+size(root.right);
}
核心思想:
1.左树的叶子结点+右树的叶子结点
2.一个结点的左右结点都为空的时候,返回1
下面结合代码图来看
public int levelSize(TreeNode root)
{
if(root==null)
{
return 0;
}
if(root.left==null&&root.right==null)
{
return 1;
}
return levelSize(root.left)+levelSize(root.right);
}
核心思想
1.左树第K层结点个数+右树第K层结点个数
2.k=1时返回1
下面结合代码
public int getKLevelNodeCount(TreeNode root,int k)
{
if(root==null)
{
return 0;
}
if(k==1)
{
return 1;
}
return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
}
核心思想
1.根结点的左树和右树哪个高,就返回哪个树的高度Height
2.返回的Height+1,这个1是把根节点的高度算上了
结合代码图看
public int getHeight(TreeNode root)
{
if(root==null)
{
return 0;
}
int leftH=getHeight(root.left);
int rightH=getHeight(root.right);
return (leftH>=rightH?leftH:rightH)+1;
}
1.如果根节点的val跟要找的val相等,返回根节点
2.如果根节点的val跟要找的val不相等,从左树找,左树有就返回左树对应的结点
3.左树没有,从右树找,右树右返回右树对应的结点
4.右树也没有,就返回null
下面结合代码图看
TreeNode find(TreeNode root, char val) { if(root==null) { return null; } if(root.value==val) { return root; } TreeNode leftNode=find(root.left,val); if(leftNode!=null) { return leftNode; } TreeNode rightNode=find(root.right,val); if(rightNode!=null) { return rightNode; } return null; }
核心思想
1.用队列实现
2.如果头结点不是空,入队
3.出队,用cur代替这个出队的,出队的结点如果不是空,将这个结点的左右结点都入
4.当cur为null时候,停下
5.这时候判断队列是否都是空,挨个出队,如果有一个不是空就不是完全二叉树
下面看代码图
boolean isCompleteTree(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); if(root != null) { queue.offer(root); } while (!queue.isEmpty()) { TreeNode cur = queue.poll(); if(cur != null) { queue.offer(cur.left); queue.offer(cur.right); }else { break; } } while (!queue.isEmpty()) { TreeNode cur = queue.poll(); if(cur != null) { return false; } } return true; }
核心思想
1.跟判断是不是完全二叉树差不多,也是用队列的思想
2.如果头结点不是空,入队
3.出队,用cur代替这个出队的,先打印cur的value,然后判断出队的结点的左结点是不是空,如果不是空,入左结点
4.再判断出队的结点的右节点是不是空,不是空的话就入队
层序遍历的思想比上面的判断是否是完全二叉树要简单,掌握了判断是否是完全二叉树就很容易掌握层序遍历,因为思想差不多,就不画代码图了
public void levelOrder(TreeNode root) { Queue<TreeNode> queue=new LinkedList<>(); if(root!=null) { queue.offer(root); } while(!queue.isEmpty()) { TreeNode cur=queue.poll(); System.out.print(cur.value+" "); if(cur.left!=null) { queue.offer(cur.left); } if(cur.right!=null) { queue.offer(cur.right); } } }
public class BinaryTree { static class TreeNode { public char value; public TreeNode left; public TreeNode right; public TreeNode(char value) { this.value=value; } } public TreeNode newTree() { TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); TreeNode G = new TreeNode('G'); TreeNode H = new TreeNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; return A; } public void prevOrder(TreeNode root) { if(root==null) { return; } System.out.print(root.value+" "); prevOrder(root.left); prevOrder(root.right); } public void inOrder(TreeNode root) { if(root==null) { return; } inOrder(root.left); System.out.print(root.value+" "); inOrder(root.right); } public void postOrder(TreeNode root) { if(root==null) { return; } postOrder(root.left); postOrder(root.right); System.out.print(root.value+" "); } public int size(TreeNode root) { if(root==null) { return 0; } return 1+size(root.left)+size(root.right); } public int levelSize(TreeNode root) { if(root==null) { return 0; } if(root.left==null&&root.right==null) { return 1; } return levelSize(root.left)+levelSize(root.right); } // 获取第K层节点的个数 public int getKLevelNodeCount(TreeNode root,int k) { if(root==null) { return 0; } if(k==1) { return 1; } return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1); } // 获取二叉树的高度 public int getHeight(TreeNode root) { if(root==null) { return 0; } int leftH=getHeight(root.left); int rightH=getHeight(root.right); return (leftH>=rightH?leftH:rightH)+1; } // 检测值为value的元素是否存在 TreeNode find(TreeNode root, char val) { if(root==null) { return null; } if(root.value==val) { return root; } TreeNode leftNode=find(root.left,val); if(leftNode!=null) { return leftNode; } TreeNode rightNode=find(root.right,val); if(rightNode!=null) { return rightNode; } return null; } //层序遍历 public void levelOrder(TreeNode root) { Queue<TreeNode> queue=new LinkedList<>(); if(root!=null) { queue.offer(root); } while(!queue.isEmpty()) { TreeNode cur=queue.poll(); System.out.print(cur.value+" "); if(cur.left!=null) { queue.offer(cur.left); } if(cur.right!=null) { queue.offer(cur.right); } } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。