二叉树的数据结构以及前序、中序、后续遍历
import java.util.ArrayList;
class BinaryTreeNode {
char value;
BinaryTreeNode left;
BinaryTreeNode right;
BinaryTreeNode(char value){
this.value=value;
}
}
public class binaryTree {
ArrayList<Character> list = new ArrayList<>();
//前序遍历
//中序遍历
private ArrayList<Character> midOrderTraver(BinaryTreeNode t){
if(t!=null) {
midOrderTraver(t.left);
list.add(t.value);
midOrderTraver(t.right);
}
return list;
}
//后序遍历
private ArrayList<Character> postOrderTraver(BinaryTreeNode t){
if(t!=null) {
postOrderTraver(t.left);
postOrderTraver(t.right);
list.add(t.value);
}
return list;
}
public static void main(String[] args) {
char[] a = {'a','b','c','d','e','f','g','h','i'};
BinaryTreeNode[] b = new BinaryTreeNode[a.length];
for (int i = 0;i < a.length; i++){
b[i] = new BinaryTreeNode(a[i]);
}
b[0].left = b[1];
b[0].right = b[2];
b[1].left = b[3];
b[1].right = b[4];
b[2].left = b[5];
b[2].right = b[6];
b[4].left = b[7];
b[4].right = b[8];
System.out.println("========This is preOrderTraver========");
for( char x:new binaryTree().preOrderTraver(b[0])){
System.out.println(x);
}
System.out.println("========This is midOrderTraver========");
for( char x:new binaryTree().midOrderTraver(b[0])){
System.out.println(x);
}
System.out.println("========This is PostOrderTraver========");
for( char x:new binaryTree().postOrderTraver(b[0])){
System.out.println(x);
}
}
}
二叉树的下一个节点
不管是找前序、中序还是后续遍历的下一个节点，只要有了遍历的集合，再查表一次就行了。
import java.util.ArrayList;
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
TreeLinkNode(){
}
ArrayList<TreeLinkNode> list = new ArrayList<>();
private void midOrderTraver(TreeLinkNode t){
if(t!=null) {
midOrderTraver(t.left);
list.add(t);
midOrderTraver(t.right);
}
}
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
TreeLinkNode curNode = new TreeLinkNode();
curNode = pNode;
while (pNode.next!=null){
pNode=pNode.next;
}
midOrderTraver(pNode);
for(TreeLinkNode t:list){
if (t==curNode){
System.out.println(list.indexOf(t));
if (list.indexOf(t)==list.size()-1) return null;
return list.get(list.indexOf(t)+1);
}
}
return pNode;
}
public static void main(String[] args) {
char[] a = {'a','b','c','d','e','f','g','h','i'};
TreeLinkNode[] b = new TreeLinkNode[a.length];
for (int i = 0;i < a.length; i++){
b[i] = new TreeLinkNode(a[i]);
}
b[0].left = b[1];
b[0].right = b[2];
b[1].left = b[3];
b[1].right = b[4];
b[1].next = b[0];
b[2].left = b[5];
b[2].right = b[6];
b[2].next = b[0];
b[3].next = b[1];
b[4].left = b[7];
b[4].right = b[8];
b[4].next = b[1];
b[5].next = b[2];
b[6].next = b[2];
b[7].next = b[4];
b[8].next = b[4];
System.out.println(new TreeLinkNode().GetNext(b[6]).val);
}
}
二叉树的宽度优先遍历
private ArrayList<Character> BFS(BinaryTreeNode root){
ArrayList<Character> lists=new ArrayList<Character>();
if(root==null)
return lists;
Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
//把起始点放入对列
queue.offer(root);
//重复以下的步骤知道对列为空为止
while (!queue.isEmpty()){
// 从队列中取出对列头
BinaryTreeNode node = queue.poll();
//将其放入已访问列表
lists.add(node.value);
//找到与队列头连接的点，将其放入queue中
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
return lists;
}
按之字形顺序打印二叉树
偶数层从右往左遍历，符合栈先进后出的特点
虽然奇数层从左向右遍历符合队列的特点，但是偶数层是从右向左遍历的插入的，不符合队列特性。
所以需要两个栈
令s1存奇数层，s2存偶数层。
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
Stack<TreeNode> s1 = new Stack<>();//奇数层
Stack<TreeNode> s2 = new Stack<>();//偶数层
int layer = 1;
if (pRoot==null)
return lists;
s1.push(pRoot);
//每层不管是s1还是s2，只要不为空就继续向下层遍历
while (!s1.empty() || !s2.empty()){
//每一层都初始化一个列表用来存储每列打印顺序
ArrayList<Integer> list = new ArrayList<>();
//判断当前层是奇数层
if (layer % 2 !=0){
while(!s1.empty()){
TreeNode t = s1.pop();
list.add(t.val);
//栈是先进后出的，偶数层是从右向左遍历，所以向偶数层添加节点是先推入左孩子，再推入右孩子
//如果该节点有左孩子，将左孩子放入s2
if(t.left != null) s2.push(t.left);
//如果该节点有右孩子，将右孩子放入s2
if(t.right != null) s2.push(t.right);
}
//当前层是偶数层
}else{
while(!s2.empty()){
//从右向左的顺序，往奇数层添节点时不能使用队列，要实现奇数层从左往右遍历先把右孩子推进去，再推左孩子
TreeNode t = s2.pop();
list.add(t.val);
if(t.right != null) s1.push(t.right);
if(t.left != null) s1.push(t.left);
}
}
//把每层遍历的结果放入总列表
lists.add(list);
对下一层进行遍历
layer++;
}
return lists;
序列化二叉树
public class Solution {
int index = -1; //计数变量
//将前序遍历结果序列化存到string中
String Serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if(root == null){
sb.append("#,");
//递归出口，遍历如果碰到节点为空就返回#，
return sb.toString();
}
//根
sb.append(root.val + ",");
//对左节点进行遍历
sb.append(Serialize(root.left));
//对右节点进行遍历
sb.append(Serialize(root.right));
return sb.toString();
}
// 反序列化不知道怎么做的
TreeNode Deserialize(String str) {
index++;
//int len = str.length();
//if(index >= len){
// return null;
// }
String[] strr = str.split(",");
TreeNode node = null;
if(!strr[index].equals("#")){
//创建根节点
node = new TreeNode(Integer.valueOf(strr[index]));
//创建左孩子
node.left = Deserialize(str);
//创建右孩子
node.right = Deserialize(str);
}
return node;
}
}
二叉搜索树的第k个节点
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
思路：二叉搜索树的中序遍历就是排好序的，第k小的节点在遍历结果的（k-1)
public class Solution {
ArrayList<TreeNode> list = new ArrayList<>();
TreeNode KthNode(TreeNode pRoot, int k)
{
list = midOrderTraver(pRoot);
if (k-1>=0&&(k-1)<list.size()) return list.get(k-1);
return null;
}
ArrayList<TreeNode> midOrderTraver(TreeNode t){
if(t!=null) {
midOrderTraver(t.left);
list.add(t);
midOrderTraver(t.right);
}
return list;
}
}
重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路
前序遍历的第一个节点肯定是根节点，中序遍历根节点左边的是左子树，右边的是右子树 ，题干中说了不含重复数字就代表可以通过对中序遍历的结果进行遍历以找出根节点所在的index。找出根节点后根节点的左右子树 root.left root.right 就可以通过递归找出（root.left = reConstructBinaryTree()）返回的即是左子树的根节点，也就是根节点的左节点。
代码
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
//数组长度为0
if(pre.length == 0){
return null;
}
int rootVal = pre[0];
TreeNode root = new TreeNode(rootVal);
//递归出口
if(pre.length == 1){
return root;
}
int rootIndex = 0;
for (int i=0; i<in.length; i++){
if (in[i] == rootVal){
rootIndex = i;
break;
}
}
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,rootIndex+1),Arrays.copyOfRange(in,0,rootIndex));
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,rootIndex+1,pre.length),Arrays.copyOfRange(in,rootIndex+1,in.length));
return root;
}
将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是答案不唯一：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
可以看出每次都是设置的是mid值
0
/ \
-3 9
/ /
-10 5
public TreeNode sortedArrayToBST(int[] nums) {
// 左右等分建立左右子树，中间节点作为子树根节点，递归该过程
return nums == null ? null : buildTree(nums, 0, nums.length - 1);
}
private TreeNode buildTree(int[] nums, int l, int r) {
if (l > r) {
return null; // 递归出口
}
int m = (l + r) / 2;
TreeNode root = new TreeNode(nums[m]);
root.left = buildTree(nums, l, m - 1);
root.right = buildTree(nums, m + 1, r);
return root;
}
