二叉树相关
2018-05-25 本文已影响2人
z七夜
二叉树相关问题
静态创建二叉树
1.首先建立一个树节点，节点有值，左节点和右节点
/**
* @author 张梦楠
* @Title: ${file_name}
* @Package ${package_name}
* @Description: ${todo}
* @date 2018/5/2519:27
* @blog www.itzmn.com
*
* 树的节点类
*/
public class TreeNode {
public int value;
public TreeNode leftNode;
public TreeNode rightNode;
public TreeNode() {
}
public TreeNode(int value) {
this.value = value;
}
2.想要创建的二叉树
image.png
3.创建二叉树
public static void main(String args[]){
TreeNode treeNode10 = new TreeNode(10);
TreeNode treeNode9 = new TreeNode(9);
TreeNode treeNode15 = new TreeNode(15);
TreeNode treeNode1 = new TreeNode(1);
TreeNode treeNode13 = new TreeNode(13);
TreeNode treeNode12 = new TreeNode(12);
treeNode10.setLeftNode(treeNode9);
treeNode10.setRightNode(treeNode15);
treeNode9.setRightNode(treeNode12);
treeNode15.setLeftNode(treeNode13);
treeNode15.setRightNode(treeNode1);
这样一颗二叉树就创建完成了
树的遍历
案例树：
image.png
- 先序遍历：先遍得到根节点，然后是左节点，最后是右节点
10 9 12 15 13 1 - 中序遍历：先得到左节点，然后是根节点，最后是右节点
9 12 10 13 15 1 - 后序遍历： 先得到左节点，然后是右节点，最后是根节点
12 9 13 1 15 10
只需要记住，前中后是对于根节点来说的，所有遍历，都是先左后右，然后看看根节点在哪，
代码实现：
先序遍历
//先序遍历二叉树
/**
* 思路：
* 先查找根节点，然后查找左节点，然后查找右节点
* @param RoottreeNode 树的根节点
*/
private static void xianxu(TreeNode RoottreeNode) {
if (RoottreeNode!=null){
System.out.print(RoottreeNode.getValue()+" ");
//查找左节点
xianxu(RoottreeNode.getLeftNode());
//查找右节点
xianxu(RoottreeNode.getRightNode());
}
}
中序遍历
//中序遍历二叉树
/**
* 思路：
* 先查找左节点，然后查找根节点，最后查找右节点
* @param RoottreeNode
*/
private static void zhongxu(TreeNode RoottreeNode) {
if (RoottreeNode!=null){
//查找左边的节点
zhongxu(RoottreeNode.getLeftNode());
//输出节点值
System.out.print(RoottreeNode.getValue()+" ");
//查找右节点
zhongxu(RoottreeNode.getRightNode());
}
}
后序遍历
//后序遍历二叉树
/**
* 思路：
* 先遍历左节点，然后遍历右节点，然后输出根几点
* @param RoottreeNode
*/
private static void houxu(TreeNode RoottreeNode) {
if (RoottreeNode!=null){
houxu(RoottreeNode.getLeftNode());
houxu(RoottreeNode.getRightNode());
System.out.print(RoottreeNode.getValue()+" ");
}
}
动态创建二叉树
一般而言都是给数组，然后自己实现二叉树，所以要自己动态生成二叉树
{7,1,9,3,2,6}
最终树的效果：
image.png
- 思路：选定一个数据为根节点，然后判断后面的数据，如果比根节点大，就放在右边，如果比根节点小，放在左边，如果右边有节点，就把右节点当做根节点，继续比较，递归，左节点同理
首先需要创建一个根节点，用来存储根节点
代码：
* 树的根类
*/
public class TreeRoot {
public TreeNode treeRoot;
public TreeNode getTreeRoot() {
return treeRoot;
}
public void setTreeRoot(TreeNode treeRoot) {
this.treeRoot = treeRoot;
}
}
代码实现：
/**
* 动态创建二叉查找树
* 思路：
* 根据根节点，如果根节点为null就创建根节点，
* 根据传入的值，和根节点比较大小，小的放左边，大的放右边，
* 如果左边有节点，就把左节点看成根节点重新判断，右边同理
* @param treeRoot
* @param value
*/
private static void create(TreeRoot treeRoot, int value) {
if (treeRoot.getTreeRoot()==null){//如果跟没有节点，就创建一个节点，作为树根
treeRoot.setTreeRoot(new TreeNode(value));
}else {
TreeNode currtreeRoot = treeRoot.getTreeRoot();
while (currtreeRoot!=null){
if (currtreeRoot.getValue()>value){//如果当前数根的值大于传入的值
//将值放在树的左边，
if (currtreeRoot.getLeftNode()==null){
//如果树节点的左侧没有值，就直接插入
currtreeRoot.setLeftNode(new TreeNode(value));
return;
}else {
//如果节点左侧有值,就把根节点变成左侧节点，继续判断
currtreeRoot = currtreeRoot.getLeftNode();
}
}else {
//如果当前根值小于传入的值，将值放在右边
if (currtreeRoot.getRightNode()==null){
currtreeRoot.setRightNode(new TreeNode(value));
return;
}else {
//如果右侧节点存在的话
currtreeRoot = currtreeRoot.getRightNode();
}
}
}
}
}
测试用例：加上刚刚的遍历，
public static void main(String args[]){
int[] arrs = {7,1,9,3,2,6};
TreeRoot treeRoot = new TreeRoot();
for (int i:arrs){
create(treeRoot,i);
}
System.out.print("先序查找：");
xianxu(treeRoot.getTreeRoot());
System.out.println();
System.out.print("中序查找：");
zhongxu(treeRoot.getTreeRoot());
System.out.println();
System.out.print("后序查找：");
houxu(treeRoot.getTreeRoot());
二叉树相关
得到二叉树的高度
代码：
/**
* 得到树的高度
* @param treeRoot
* *
* 7
* 1 9
* 3
* 2 6
*/
private static int getHeight(TreeNode treeRoot) {
if (treeRoot==null){
return 0;
}else {
//如果节点不为空
int left = getHeight(treeRoot.getLeftNode());
int right = getHeight(treeRoot.getRightNode());
if (right > left){
return right+1;
}
return left+1;
}
}
更多详情QQ群：552113611
