二叉树的建立
public class TreeNode {
public TreeNode left;
public TreeNode right;
public int value;
public TreeNode next;
}
public class 二叉树的建立 {
private static int counter = 0;//定义一个静态计数变量
public static void main(String[] args) {
int[] a = {1, 2, 3, 0, 0, 4, 0, 0, 5, 0, 0};
createBiTree(a);
}
public static TreeNode createBiTree(int[] a) {
TreeNode root = new TreeNode();
createBiTree(root, a, counter);
return root;
}
/**
* 构造二叉树
*
* @param root 根节点
* @param a 数据源
* @param i 计数器
* @return 根节点
*/
private static TreeNode createBiTree(TreeNode root, int[] a, int i) {
if (i < a.length) {
if (a[i] == 0) {
root = null;
} else {
TreeNode left = new TreeNode();
TreeNode right = new TreeNode();
root.left = createBiTree(left, a, ++counter);
root.right = createBiTree(right, a, ++counter);
root.value = a[i];
}
}
return root;
}
}
建立二叉树，利用了递归的原理，也就是在打印二叉树的前中后序遍历算法中打印结点的地方，改成了生成结点，给结点赋值的操作而已。
二叉树的遍历
二叉树前中后序遍历
public class 二叉树前中后遍历 {
static void recursionPreoderTree(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.value + " ");
recursionPreoderTree(root.left);
recursionPreoderTree(root.right);
}
static void recursionInoderTree(TreeNode root) {
if (root == null) {
return;
}
recursionInoderTree(root.left);
System.out.print(root.value + " ");
recursionInoderTree(root.right);
}
static void recursionPostorderTree(TreeNode root) {
if (root == null) {
return;
}
recursionPostorderTree(root.left);
recursionPostorderTree(root.right);
System.out.print(root.value + " ");
}
public static void main(String[] args) {
int[] a = {1, 2, 0, 4, 0, 0, 3, 0, 0};
TreeNode root = 二叉树的建立.createBiTree(a);
recursionPreoderTree(root);
System.out.println();
recursionInoderTree(root);
System.out.println();
recursionPostorderTree(root);
}
}
二叉树层序遍历(广度优先)
public class 二叉树层序遍历 {
static void levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
System.out.print(current.value + " ");
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
}
public static void main(String[] args) {
int[] a = {1, 2, 0, 4, 0, 0, 3, 0, 0};
TreeNode root = 二叉树的建立.createBiTree(a);
levelOrder(root);
}
}
用队列，每次遍历当前节点的时候，把该节点从队列拿出来，并且把它的子节点全部加入到队列中
题目
设置二叉树的next节点
public class 二叉树的next结点 {
static void nextSiblings(TreeNode treeNode) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(treeNode);
//这个level没有实际用处，但是可以告诉大家怎么判断当前node是第几层。
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode current = queue.poll();
System.out.print(current.value + " ");
if (current.left != null) {
queue.offer(current.left);
}
if (current.right != null) {
queue.offer(current.right);
}
if (i != size - 1) {
current.next = queue.peek();
}
}
level++;
}
}
public static void main(String[] args) {
int[] a = {1, 2, 0, 4, 0, 0, 3, 0, 0};
TreeNode root = 二叉树的建立.createBiTree(a);
nextSiblings(root);
}
}
其实这个题目就是典型的层序遍历，使用队列就可以轻松解决，每次poll出来一个节点，判断是不是当前层的最后一个，如果不是，把其next设置成queue中的下一个节点就ok了。至于怎么判断当前节点是哪一层呢？使用当前queue的size做for循环。
翻转二叉树
public class 翻转二叉树 {
static TreeNode reverseBinaryTree(TreeNode root) {
if (root == null) {
return null;
} else {
//左子树已翻转好
TreeNode left = reverseBinaryTree(root.left);
//右子树已翻转好
TreeNode right = reverseBinaryTree(root.right);
//交换左右子树
root.right = left;
root.left = right;
return root;
}
}
}
分而治之 和 递归 的思想
铺平二叉树
public class 铺平二叉树_链表 {
static TreeNode inflateBinaryTree(TreeNode root) {
if (root == null) {
return root;
}
//用递归的思想，把左右先铺平
TreeNode left = inflateBinaryTree(root.left);
TreeNode right = inflateBinaryTree(root.right);
//把左指针和右指针先指向空。
root.left = null;
root.right = null;
//假如左子树生成的链表为空，那么忽略它，把右子树生成的链表指向根节点的右指针
if (left == null) {
root.right = right;
return root;
}
//如果左子树生成链表不为空，那么用while循环获取最后一个节点，并且它的右指针要指向右子树生成的链表的头节点
root.right = left;
TreeNode lastLeft = left;
while (lastLeft.right != null) {
lastLeft = lastLeft.right;
}
lastLeft.right = right;
return root;
}
public static void main(String[] args) {
int[] a = {1, 2, 0, 4, 0, 0, 3, 0, 0};
TreeNode root = 二叉树的建立.createBiTree(a);
inflateBinaryTree(root);
}
}
android的findViewById
View searchViewById(ViewGroup viewGroup, int id) {
if (viewGroup == null) {
return null;
}
int childCount = viewGroup.getChildCount();
for (int i = 0; i < childCount; i++) {
View view = viewGroup.getChildAt(i);
if (view.getId() == id) {
return view;
}
if (view instanceof ViewGroup) {
View temp = searchViewById((ViewGroup) view, id);
if (temp != null) {
return temp;
}
}
}
return null;
}
线索二叉树
中序线索化二叉树
public class 中序线索化二叉树 {
private Node preNode; //线索化时记录前一个节点
//节点存储结构
static class Node {
String data; //数据域
Node left; //左指针域
Node right; //右指针域
boolean isLeftThread = false; //左指针域类型 false：指向子节点、true：前驱或后继线索
boolean isRightThread = false; //右指针域类型 false：指向子节点、true：前驱或后继线索
Node(String data) {
this.data = data;
}
}
/**
* 通过数组构造一个二叉树（完全二叉树）
*
* @param array
* @param index
* @return
*/
static Node createBinaryTree(String[] array, int index) {
Node node = null;
if (index < array.length) {
node = new Node(array[index]);
node.left = createBinaryTree(array, index * 2 + 1);
node.right = createBinaryTree(array, index * 2 + 2);
}
return node;
}
public static void main(String[] args) {
String[] array = {"A", "B", "C", "D", "E", "F", "G", "H"};
Node root = createBinaryTree(array, 0);
中序线索化二叉树 tree = new 中序线索化二叉树();
tree.inThreadOrder(root);
}
private void inThreadOrder(Node root) {
inThreadOrder(root.left);
//左指针为空，将指针指向刚才访问过的结点
//若preNode为null，则当前结点时第一个结点
if (root.left == null) {
root.isLeftThread = true;
root.left = preNode;
}
// 前一个结点的后继结点指向当前结点
// 当前结点的后继点只能由父节点指定
if (preNode != null && preNode.right == null) {
preNode.isRightThread = true;
preNode.right = root;
}
preNode = root;
inThreadOrder(root.right);
}
}
和二叉树中序遍历的递归代码几乎完全一样。只不过将本是打印的结点的功能改成了线索化的功能。
