二叉树遍历

实现二叉树的先序、中序、后序遍历，包括递归方式和非递归方式
1.递归方法

    //定义二叉树public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}//先序遍历public static void preOrderRecur(Node head) {if (head == null) {return;}System.out.print(head.value + " ");preOrderRecur(head.left);preOrderRecur(head.right);}//中序遍历public static void inOrderRecur(Node head) {if (head == null) {return;}inOrderRecur(head.left);System.out.print(head.value + " ");inOrderRecur(head.right);}//后序遍历public static void posOrderRecur(Node head) {if (head == null) {return;}posOrderRecur(head.left);posOrderRecur(head.right);System.out.print(head.value + " ");}

2.非递归方法

//利用栈
import java.util.Stack;
public class hello {//定义二叉树public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}//先序遍历（中左右）public static void preOrderUnRecur(Node head) {System.out.print("pre-order: ");if (head != null) {Stack<Node> stack = new Stack<Node>();stack.add(head);while (!stack.isEmpty()) {head = stack.pop();System.out.print(head.value + " ");//利用栈先进后出的特点if (head.right != null) {stack.push(head.right);}if (head.left != null) {stack.push(head.left);}}}System.out.println();}//中序遍历（左中右）public static void inOrderUnRecur(Node head) {System.out.print("in-order: ");if (head != null) {Stack<Node> stack = new Stack<Node>();while (!stack.isEmpty() || head != null) {//一直向左走，找到最左端if (head != null) {stack.push(head);head = head.left;} else {head = stack.pop();System.out.print(head.value + " ");head = head.right;//检查右子树}}}System.out.println();}//后序遍历：（左右中）利用两个栈public static void posOrderUnRecur1(Node head) {System.out.print("pos-order: ");if (head != null) {Stack<Node> s1 = new Stack<Node>();Stack<Node> s2 = new Stack<Node>();s1.push(head);while (!s1.isEmpty()) {head = s1.pop();//s2入栈的顺序为中右左s2.push(head);if (head.left != null) {s1.push(head.left);}if (head.right != null) {s1.push(head.right);}}s2出栈的顺序为左右中while (!s2.isEmpty()) {System.out.print(s2.pop().value + " ");}}System.out.println();}public static void main(String[] args) {Node head = new Node(5);head.left = new Node(3);head.right = new Node(8);head.left.left = new Node(2);head.left.right = new Node(4);head.left.left.left = new Node(1);head.right.left = new Node(7);head.right.left.left = new Node(6);head.right.right = new Node(10);head.right.right.left = new Node(9);head.right.right.right = new Node(11);// unrecursiveSystem.out.println("============unrecursive=============");preOrderUnRecur(head);inOrderUnRecur(head);posOrderUnRecur1(head);}
}

在二叉树中找到一个节点的后继节点

【题目】 现在有一种新的二叉树节点类型如下：

 public class Node {public int value; public Node left; public Node right;public Node parent;public Node(int data) { this.value = data; }}

该结构比普通二叉树节点结构多了一个指向父节点的parent指针。假设有一 棵Node类型的节点组成的二叉树，树中每个节点的parent指针 都正确地指向 自己的父节点，头节点的parent指向null。只给一个在 二叉树中的某个节点 node，请实现返回node的后继节点的函数。在二叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点。
思路：
中序遍历一个结点时，后继结点有三种情况：
1：如果当前结点有右结点，则下一个遍历的是右子树的最左结点；
2：如果当前结点无右结点，若它是父节点的左儿子，则下一遍历的是父节点；
3：如果当前结点无右结点，且它是父节点的右儿子，则所在子树遍历完了。向上寻找一个作为左儿子的祖先结点，那么下一遍历的就是该祖先结点的父节点；（一直找到根节点为止）
如果上面三种情况都没找到，则该节点是树的最后一个结点，无后继结点。

   //定义二叉树public static class Node {public int value;public Node left;public Node right;public Node parent;public Node(int data) {this.value = data;}}//寻找后继节点public static Node getSuccessorNode(Node node) {if (node == null) {return node;}//右子树不为空if (node.right != null) {return getLeftMost(node.right);} else {//右子树为空Node parent = node.parent;//parent != null是为了保证中序遍历最后一个节点无后继节点while (parent != null && parent.left != node) {node = parent;parent = node.parent;}return parent;}}//获得右子树的最左节点public static Node getLeftMost(Node node) {if (node == null) {return node;}while (node.left != null) {node = node.left;}return node;}public static void main(String[] args) {Node head = new Node(6);head.parent = null;head.left = new Node(3);head.left.parent = head;head.left.left = new Node(1);head.left.left.parent = head.left;head.left.left.right = new Node(2);head.left.left.right.parent = head.left.left;head.left.right = new Node(4);head.left.right.parent = head.left;head.left.right.right = new Node(5);head.left.right.right.parent = head.left.right;head.right = new Node(9);head.right.parent = head;head.right.left = new Node(8);head.right.left.parent = head.right;head.right.left.left = new Node(7);head.right.left.left.parent = head.right.left;head.right.right = new Node(10);head.right.right.parent = head.right;Node test = head.left.left;//1's next is 2System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.right.right; // 10's next is nullSystem.out.println(test.value + " next: " + getSuccessorNode(test));}

二叉树的序列化和反序列化

二叉树的序列化：假设序列化的结果字符串为str，初始时str等于空字符串。先序遍历二叉树，如果遇到空节点，就在str的末尾加上“#!”，“#”表示这个节点为空，节点值不存在，当然你也可以用其他的特殊字符，“!”表示一个值的结束。如果遇到不为空的节点，假设节点值为3，就在str的末尾加上“3!”。

import java.util.LinkedList;
import java.util.Queue;
public class hello {//定义节点public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}//先序序列化public static String serialByPre(Node head) {//空节点为#if (head == null) {return "#!";}String res = head.value + "!";res += serialByPre(head.left);res += serialByPre(head.right);return res;}//先序反序列化public static Node reconByPreString(String preStr) {String[] values = preStr.split("!");Queue<String> queue = new LinkedList<String>();//可以不用队列，直接对数组下表进行操作for (int i = 0; i != values.length; i++) {queue.offer(values[i]);//offer（）添加元素，功能类似add()}return reconPreOrder(queue);}//反序列化队列（按先序）public static Node reconPreOrder(Queue<String> queue) {String value = queue.poll();//出队//空if (value.equals("#")) {return null;}Node head = new Node(Integer.valueOf(value));//中head.left = reconPreOrder(queue);//左head.right = reconPreOrder(queue);//右return head;}//按层遍历序列化：从上到下，从左到右public static String serialByLevel(Node head) {if (head == null) {return "#!";}String res = head.value + "!";Queue<Node> queue = new LinkedList<Node>();queue.offer(head);while (!queue.isEmpty()) {head = queue.poll();if (head.left != null) {res += head.left.value + "!";queue.offer(head.left);} else {res += "#!";}if (head.right != null) {res += head.right.value + "!";queue.offer(head.right);} else {res += "#!";}}return res;}//按层遍历反序列化：从上到下，从左到右public static Node reconByLevelString(String levelStr) {String[] values = levelStr.split("!");int index = 0;Node head = generateNodeByString(values[index++]);//创建头结点Queue<Node> queue = new LinkedList<Node>();//将头结点加入队列if (head != null) {queue.offer(head);}Node node = null;while (!queue.isEmpty()) {node = queue.poll();//出队node.left = generateNodeByString(values[index++]);node.right = generateNodeByString(values[index++]);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}return head;}public static Node generateNodeByString(String val) {if (val.equals("#")) {return null;}return new Node(Integer.valueOf(val));}
}

注：序列化和反序列化不能忽略空

判断一棵二叉树是否是平衡二叉树

判断平衡二叉树的方法：
（1）左子树平衡
（2）右子树平衡
（3）左右子树高度差不超过1

   //定义节点public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}//判断是否平衡public static boolean isBalance(Node head) {int lh; /* for height of left subtree */int rh; /* for height of right subtree *//* If tree is empty then return true */if(head == null)     return true;/* Get the height of left and right sub trees */lh = height(head.left);rh = height(head.right);if(Math.abs(lh-rh) <= 1 && isBalance(head.left) && isBalance(head.right))return true;/* If we reach here then tree is not height-balanced */return false;}/*  The function Compute the "height" of a tree. Height is thenumber of nodes along the longest path from the root nodedown to the farthest leaf node.*/public static int height(Node node) {/* base case tree is empty */if (node == null)return 0;/* If tree is not empty then height = 1 + max of leftheight and right heights */return 1 + Math.max(height(node.left), height(node.right));}public static void main(String[] args) {Node head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.left.right = new Node(5);head.right.left = new Node(6);head.right.right = new Node(7);System.out.println(isBalance(head));}

判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树

1.搜索二叉树
搜索二叉树特点：
（1）搜索二叉树无重复节点
（2）搜索二叉树的中序遍历值依次升序。

//利用栈非递归遍历二叉树
import java.util.Stack;
public class hello {//定义节点public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}//只要树的中序遍历结果是升序的,那么就是搜索二叉树public static boolean InOrderJudgeSearch(Node head){//设计一个最小值int falg=Integer.MIN_VALUE;if (head!=null){Stack<Node> stack=new Stack<>();while (!stack.isEmpty()||head!=null){if (head!=null){stack.push(head);head=head.left;}else {head=stack.pop();if (head.value>falg){falg=head.value;}else {return false;}head=head.right;}}}return true;}public static void main(String[] args){Node head = new Node(5);head.left = new Node(3);head.right = new Node(8);head.left.left = new Node(2);head.left.right = new Node(4);head.right.left = new Node(7);head.right.right = new Node(10);System.out.println( InOrderJudgeSearch(head));}
}

2.完全二叉树
(1)完全二叉树某节点有右孩子无左孩子一定false
(2)如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树；

import java.util.LinkedList;
import java.util.Queue;public class hello {//定义节点public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}//是否为完全二叉树public static boolean isCBT(Node head) {//空树为完全二叉树if (head == null) {return true;}Queue<Node> queue = new LinkedList<Node>();//后续节点是否为叶节点boolean leaf = false;Node l = null;Node r = null;queue.offer(head);//头结点入队while (!queue.isEmpty()) {head = queue.poll();//节点出队l = head.left;r = head.right;//该节点之后的队列中的结点应都为叶子节点却不是叶子节点/左孩子为空右孩子不为空if ((leaf && (l != null || r != null)) || (l == null && r != null)) {return false;}if (l != null) {queue.offer(l);}if (r != null) {queue.offer(r);} else {//右子节点为空，该节点之后的队列中的结点应都为叶子节点leaf = true;}}return true;}public static void main(String[] args){Node head = new Node(5);head.left = new Node(3);head.right = new Node(8);head.left.left = new Node(2);head.left.right = new Node(4);head.right.left = new Node(7);head.right.right = new Node(10);System.out.println( isCBT(head));}
}

已知一棵完全二叉树，求其节点的个数

要求：时间复杂度低于O(N)，N为这棵树的节点个数
分析：如果是遍历得到节点数，则时间复杂度等于o(n)

public class hello {//定义节点public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}//结点数public static int nodeNum(Node head) {if (head == null) {return 0;}return bs(head, 1, mostLeftLevel(head, 1));}//le为当前所在高度（从上往下），h为Node最左节点所在高度public static int bs(Node node, int le, int h) {if (le == h) {return 1;}//1 << (h - le)相当于2^(h-le)，完全二叉树的结点个数为2^h-1(h为高度)//Node右子树的最左节点的高度与Node左子树的高度相同，说明Node左子树为完全二叉树if (mostLeftLevel(node.right, le + 1) == h) {//结点数为Node左子树结点数+Node本身个数1+Node右子树递归return (1 << (h - le)) + bs(node.right, le + 1, h);} else {//Node右子树的最左节点的高度与Node左子树的高度不同，说明Node右子树为完全二叉树（深度减1）//结点数为Node右子树结点数+Node本身个数1+Node左子树递归return (1 << (h - le - 1)) + bs(node.left, le + 1, h);}}//计算node最左节点所在高度public static int mostLeftLevel(Node node, int level) {while (node != null) {level++;node = node.left;}return level - 1;}public static void main(String[] args) {Node head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.left.right = new Node(5);head.right.left = new Node(6);System.out.println(nodeNum(head));}
}