二叉树的一些基础算法

开始准备面试了，不定期更新一下更种各样的数据结构，记录一下吧。

1. 先序遍历，递归算法。
2. 中序遍历，递归算法。
3. 后序遍历，递归算法。
4. 先序遍历，非递归算法。
5. 中序遍历，非递归算法。
6. 后序遍历，非递归算法。
7. 二叉树的层次遍历。
8. 求二叉树的宽度
9. 求二叉树的深度
10. 求二叉树最远两个节点的距离。

0.二叉树节点

public class Node {    public int value;    public Node leftNode;    public Node rightNode;        //深度 用于求二叉树深度    public int deep;        //是否访问 用于后序遍历二叉树    public int visit;        //左右最远距离 用于求二叉树最远两个节点间距离    public int leftLen;    public int rightLen;        public Node(int value) {        this.value = value;    }        public Node(int value, Node left, Node right) {        this.value = value;        this.leftNode = left;        this.rightNode = right;    }    @Override    public String toString() {        return "Node [value="         + value + ", visit=" + visit + "]";    }}

1.先序遍历，递归算法

public static void preOrder(Node n) {    if(n == null) {        return;    }    System.out.println(n);    preOrder(n.leftNode);    preOrder(n.rightNode);}

2.中序遍历，递归算法

public static void InOrder(Node n) {    if(n == null) {        return;    }    InOrder(n.leftNode);    System.out.println(n);    InOrder(n.rightNode);}

3.中序遍历，递归算法

public static void postOrder(Node n) {    if(n == null) {        return;    }       postOrder(n.leftNode);    postOrder(n.rightNode);    System.out.println(n);}

4.先序遍历，非递归算法

非递归算法运用了栈的思想。

public static void preOrderStack(Node n) {    Stack
    
      stack = new Stack
     
      ();        while(n != null || !stack.isEmpty()) {        while(n != null) {            System.out.println(n);            stack.push(n);            n = n.leftNode;        }        if(!stack.isEmpty()) {            n = stack.pop();            n = n.rightNode;        }            }}
     
    

5.中序遍历，非递归算法

public static void inOrderStack(Node n) {    Stack
    
      stack = new Stack
     
      ();    while(n != null || !stack.isEmpty()) {        while(n != null) {            stack.push(n);            n = n.leftNode;        }        if(!stack.isEmpty()) {            n = stack.pop();            System.out.println(n);            n = n.rightNode;        }    }}
     
    

6.后序遍历，非递归算法

设置一个访问变量来判断节点的右子树是否已经访问。

public static void postOrderStack(Node n) {    Stack
    
      stack = new Stack
     
      ();    while(n != null || !stack.isEmpty()) {        while(n != null) {            stack.push(n);            n = n.leftNode;        }        while(!stack.empty()             && stack.peek().visit == 1) {            System.out.println(stack.pop());        }                if(!stack.empty()) {            n = stack.peek();            n.visit = 1;            n = n.rightNode;        }    }}
     
    

7.二叉树的层次遍历

二叉树的层次遍历运用队列的思想。

public static void levelOrder(Node n) {    if(n == null) {        return;    }    Queue
    
      queue = new ArrayDeque
     
      ();    queue.add(n);        while(queue.size() > 0) {        n = queue.poll();        System.out.println(n);        if(n.leftNode != null) {            queue.add(n.leftNode);        }        if(n.rightNode != null) {            queue.add(n.rightNode);        }    }}
     
    

8.求二叉树宽度

二叉树的宽度指的是，二叉树的每一层的节点数最多有多少。

思想与二叉树层次遍历相似。

public static int width(Node n) {    Queue
    
      queue = new ArrayDeque
     
      ();    int maxWidth = 1;    queue.add(n);        while(queue.size() > 0) {        int len = queue.size();        while(len > 0) {            n = queue.poll();            len--;            if(n.leftNode != null) {                queue.add(n.leftNode);            }            if(n.rightNode != null) {                queue.add(n.rightNode);            }        }        maxWidth = Math.max(maxWidth, queue.size());    }    return maxWidth;}
     
    

9.求二叉树深度

public static int deep(Node n) {    if(n == null) {        return 0;    }    int l = deep(n.leftNode);    int r = deep(n.rightNode);    if(l > r) {        return l + 1;    }    return r + 1;}

10.求二叉树最远两个节点的距离

求每个节点的左右长度，相加+1与最大距离相比。

public static int len(Node n, int maxValue) {    if(n == null) {        return 0;    }    if(n.leftNode == null) {        n.leftLen = 0;    }    if(n.rightNode == null) {        n.leftLen = 0;    }    if(n.leftNode != null) {        len(n.leftNode, maxValue);    }    if(n.rightNode != null) {        len(n.rightNode, maxValue);    }        if(n.leftNode != null) {        if(n.leftNode.leftLen > n.leftNode.rightLen) {            n.leftLen = n.leftNode.leftLen + 1;        } else {            n.leftLen = n.leftNode.rightLen + 1;        }    }        if(n.rightNode != null) {        if(n.rightNode.leftLen > n.rightNode.rightLen) {            n.rightLen = n.rightNode.leftLen + 1;        } else {            n.rightLen = n.rightNode.rightLen + 1;        }    }        if(n.leftLen + n.rightLen + 1 > maxValue) {        maxValue = n.leftLen + n.rightLen + 1;    }    return maxValue;}