二叉树之java实现

二叉树是数据结构当中比较重要的部分，二叉树当中最重要的部分就是对树的遍历，常用的有几种：前序遍历，中序遍历，后序遍历，以及层次遍历。
求树的高度为遍历的变形，方法类似。当非递归遍历时为了记住所经过的路径，需要用栈来实现

例如一颗二叉树：

先序遍历

思想：

初始化栈，将p指向树的根节点
如果p不为空或者栈不为空则进入下一层判断，否则条件结束
- 如果p不为空，访问该节点，将该节点压栈，访问该节点的左子树
- 如果p为空，则弹出栈顶，将p指向弹出的栈顶，访问该节点的右子树
循环进入第二层进行判断

总结：直接访问p指向的节点，然后访问该节点的左子树，最后访问节点的右子树。
如图所示。根据图例遍历顺序为A,B,D,E,C,F,G

代码实现：

/** 
 * 递归 先序遍历二叉树
 * @param node
 */
public void preShow(Node node){
    if(node != null && node.item != null){
        System.out.print(node.item + "  ");
        preShow(node.left);
        preShow(node.right);
    }
}

/**
 * 非递归先序遍历二叉树
 */
public void preShow(){
    Stack<Node> stack = new Stack<>();
    Node node = root;
    while((node.item != null && node != null) || stack.empty() != true){
        if(node.item != null && node != null){
            System.out.print(node.item + "  ");
            stack.push(node);
            node = node.left;
        }else{
            node = stack.pop();
            node = node.right;
        }
    }
    System.out.println();
}

中序遍历

思想：

让p指向根节点
如果p不为空，将p压入栈内，访问p的左子树，再循环对p进行判断
如果p为空并且栈为空，则算法执行完毕。
- 栈不为空，弹出栈顶元素，另p指向该元素，访问节点内容
- p指向节点的右子树
进入第二层循环判断节点是否为空

总结：先遍历节点的左子树，遍历完毕之后访问此节点，之后访问节点的右子树
根据图例遍历顺序为：D.B.E,A,C,G,F
二叉树之java实现

代码实现：

/**
 * 递归 中序遍历二叉树
 * @param node
 */
public void inorderShow(Node node){
    if(node != null && node.item != null){
        inorderShow(node.left);
        System.out.print(node.item + "  ");
        inorderShow(node.right);
    }
}

/**
 * 非递归中序遍历二叉树
 */
public void inorderShow(){
    Stack<Node> stack = new Stack<>();
    Node node = root;
    while(true){
        while(node != null && node.item != null){
            stack.push(node);
            node = node.left;
        }
        if(stack.empty() == true){
            System.out.println();
            return;
        }
        node = stack.pop();
        System.out.print(node.item + "  ");
        node = node.right;
    }
}

后序遍历

思想：

另p指向树的根节点，树的所有节点含有初始状态
判断p是否为空
- 如果p为不为空，将p压入栈，另p指向p的左节点
- 如果p为空，弹出栈顶，判断栈顶元素是否为初始状态
  - 若果为初始状态，将状态更改，再次压入栈，另p指向自己的右节点，进入第二层判断节点是否为空
  - 不为初始状态，访问该节点，判断栈是否为空
    - 如果栈为空，算法结束
    - 否则弹出栈顶，跳出当前层进行判断

总结：先遍历节点的左子树，然后遍历节点的右子树，最后遍历该节点
根据图例遍历顺序为：D,E,B,G,F,C,A
二叉树之java实现

代码实现：

/**
 * 递归 后序遍历二叉树
 * @param node
 */
public void posShow(Node node){
    if(node != null && node.item != null){
        posShow(node.left);
        posShow(node.right);
        System.out.print(node.item + "  ");
    }
}

/**
 * 非递归后序遍历二叉树
 */
public void posShow(){
    Stack<Node> stack = new Stack<>();
    Node node = root;
    while(true){
        while(node != null && node.item != null){
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        while(node.isVisited == true){
            System.out.print(node.item + "  ");
            if(stack.empty() == true){
                System.out.println();
                return;
            }
            node = stack.pop();
        }
        if(node.isVisited == false){
            node.isVisited = true;
            stack.push(node);
            node = node.right;
        }
    }
}

求树的高度

思想：树的高度为根节点左右子树当中最高的一个加一,根据图例树的高度为4
代码实现：

/**
 * 求树的深度
 * @param node
 * @return
 */
private int depth(Node node){
    int deepl = 0;
    int deepr = 0;
    if(node == null || node.item == null){
        return 0;
    }
    deepl = depth(node.left);
    deepr = depth(node.right);
    return 1+(deepl > deepr ? deepl : deepr);
}

整体代码

import java.util.Scanner;
import java.util.Stack;

/**
 * 二叉链表 表示法
 * 输入#表示当前分支节点为空
 * @author dell
 *
 */
public class Tree {
//用来表示树的根节点
Node root;
//用来存储树的高度
private int deep;
private Scanner scanner;

/**
 * 初始化树
 */
public void init(){
    root = new Node();
    deep = 0;
}

/**
 * 获得树的高度
 * @return
 */
public int getDeep() {
    deep = depth(root);
    return deep;
}

/**
 * 通过递归方法先序 创建二叉树
 * @param node
 */
public void creatTree(Node node){
    scanner = new Scanner(System.in);
    System.out.println("请输入节点的值： ");
    String value = scanner.next();
    scanner.nextLine();
    if(value.equals("#")){
        node = null;
    }else {
        node.item = value;
        node.left = new Node();
        node.right = new Node();
        creatTree(node.left);
        creatTree(node.right);
    }
}

/**
 * 递归 先序遍历二叉树
 * @param node
 */
public void preShow(Node node){
    if(node != null && node.item != null){
        System.out.print(node.item + "  ");
        preShow(node.left);
        preShow(node.right);
    }
}

/**
 * 递归 中序遍历二叉树
 * @param node
 */
public void inorderShow(Node node){
    if(node != null && node.item != null){
        inorderShow(node.left);
        System.out.print(node.item + "  ");
        inorderShow(node.right);
    }
}

/**
 * 递归 后序遍历二叉树
 * @param node
 */
public void posShow(Node node){
    if(node != null && node.item != null){
        posShow(node.left);
        posShow(node.right);
        System.out.print(node.item + "  ");
    }
}

/**
 * 非递归先序遍历二叉树
 */
public void preShow(){
    Stack<Node> stack = new Stack<>();
    Node node = root;
    while((node.item != null && node != null) || stack.empty() != true){
        if(node.item != null && node != null){
            System.out.print(node.item + "  ");
            stack.push(node);
            node = node.left;
        }else{
            node = stack.pop();
            node = node.right;
        }
    }
    System.out.println();
}

/**
 * 非递归中序遍历二叉树
 */
public void inorderShow(){
    Stack<Node> stack = new Stack<>();
    Node node = root;
    while(true){
        while(node != null && node.item != null){
            stack.push(node);
            node = node.left;
        }
        if(stack.empty() == true){
            System.out.println();
            return;
        }
        node = stack.pop();
        System.out.print(node.item + "  ");
        node = node.right;
    }
}

/**
 * 非递归后序遍历二叉树
 */
public void posShow(){
    Stack<Node> stack = new Stack<>();
    Node node = root;
    while(true){
        while(node != null && node.item != null){
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        while(node.isVisited == true){
            System.out.print(node.item + "  ");
            if(stack.empty() == true){
                System.out.println();
                return;
            }
            node = stack.pop();
        }
        if(node.isVisited == false){
            node.isVisited = true;
            stack.push(node);
            node = node.right;
        }
    }
}

/**
 * 求树的深度
 * @param node
 * @return
 */
private int depth(Node node){
    int deepl = 0;
    int deepr = 0;
    if(node == null || node.item == null){
        return 0;
    }
    deepl = depth(node.left);
    deepr = depth(node.right);
    return 1+(deepl > deepr ? deepl : deepr);
}

/**
 * 内部类构建树的节点
 * @author dell
 *
 */
static class Node{
    String item;
    Node left;
    Node right;
    boolean isVisited = false;

    Node(){}
    Node(String element, Node left, Node right){
        this.item = element;
        this.left = left;
        this.right = right;
    }
 }
}

欢迎一起学习讨论QQ：3529601371

秒客网

二叉树之java实现

二叉树之java实现

先序遍历

中序遍历

后序遍历

求树的高度

整体代码

相关文章