- 一般二叉树
普通二叉树，前、中、后序遍历以及搜索
public class BinaryTree {
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
TreeNode root = new TreeNode(1, "Ralap01");
TreeNode ralap02 = new TreeNode(2, "Ralap02");
TreeNode ralap03 = new TreeNode(3, "Ralap03");
TreeNode ralap04 = new TreeNode(4, "Ralap04");
TreeNode ralap05 = new TreeNode(5, "Ralap05");
root.left = ralap02;
root.right = ralap03;
ralap03.left = ralap05;
ralap03.right = ralap04;
bt.setRoot(root);
System.out.println("前序");
bt.preOrder();
System.out.println("中序");
bt.infixOrder();
System.out.println("后续");
bt.laterOrder();
System.out.println("==================================================");
int serach = 5;
TreeNode treeNode = bt.preSerach(serach);
System.out.println(treeNode);
treeNode = bt.infixSerach(serach);
System.out.println(treeNode);
treeNode = bt.laterSerach(serach);
System.out.println(treeNode);
System.out.println("=====================");
TreeNode del = bt.del(5);
System.out.println(del);
System.out.println("-----------");
bt.preOrder();
}
private TreeNode root;
public BinaryTree setRoot(TreeNode root) {
this.root = root;
return this;
}
public void preOrder() {
if (root != null) {
root.preOrder();
}
}
public void infixOrder() {
if (root != null) {
root.infixOrder();
}
}
public void laterOrder() {
if (root != null) {
root.laterOrder();
}
}
public TreeNode preSerach(int no) {
return root.preSerach(no);
}
public TreeNode infixSerach(int no) {
return root.infixSerach(no);
}
public TreeNode laterSerach(int no) {
return root.laterSerach(no);
}
public void dfsOrderDG(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.no);
dfsOrderDG(node.left);
dfsOrderDG(node.right);
}
public void dfsOrder() {
List<TreeNode> nodeList = new ArrayList<>();
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
System.out.println(node.no);
}
}
public void dfsOrder(TreeNode node) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
TreeNode poll = queue.poll();
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
System.out.println(poll.val);
}
}
public TreeNode del(int no) {
TreeNode delNode = null;
if (root != null) {
if (root.no != no) {
delNode = root.del(no);
} else {
delNode = root;
root = null;
}
} else {
System.out.println("数不能为空");
}
return delNode;
}
}
class TreeNode {
public int no;
public String name;
public TreeNode left;
public TreeNode right;
public TreeNode(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
final StringBuilder sb = new StringBuilder("TreeNode{");
sb.append("no=").append(no);
sb.append(", name='").append(name).append('\'');
sb.append('}');
return sb.toString();
}
public void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
public void laterOrder() {
if (this.left != null) {
this.left.laterOrder();
}
if (this.right != null) {
this.right.laterOrder();
}
System.out.println(this);
}
public TreeNode preSerach(int no) {
TreeNode resNode = null;
System.out.println("一一一一一一一一一");
if (this.no == no) {
return this;
}
if (this.left != null) {
resNode = this.left.preSerach(no);
}
if (resNode != null) {
return resNode;
}
if (this.right != null) {
resNode = this.right.preSerach(no);
}
return resNode;
}
public TreeNode infixSerach(int no) {
TreeNode resNode = null;
if (this.left != null) {
resNode = this.left.infixSerach(no);
}
if (resNode != null) {
return resNode;
}
System.out.println("二二二二二二二二");
if (this.no == no) {
return this;
}
if (this.right != null) {
resNode = this.right.infixSerach(no);
}
return resNode;
}
public TreeNode laterSerach(int no) {
TreeNode resNode = null;
if (this.left != null) {
resNode = this.left.laterSerach(no);
}
if (resNode != null) {
return resNode;
}
if (this.right != null) {
resNode = this.right.laterSerach(no);
}
if (resNode != null) {
return resNode;
}
System.out.println("三三三三三三");
if (this.no == no) {
return this;
}
return resNode;
}
TreeNode delNode = null;
public TreeNode del(int no) {
if (this.left != null) {
if (this.left.no == no) {
delNode = this.left;
this.left = null;
} else {
delNode = this.left.del(no);
}
}
if (delNode != null) {
return delNode;
}
if (this.right != null) {
if (this.right.no == no) {
delNode = this.right;
this.right = null;
} else {
delNode = this.right.del(no);
}
}
return delNode;
}
}
- 顺序存储二叉树
将数组以树的思想标识，包括前、中、后续遍历
public class BinaryOrderTree {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 6, 7};
BinaryOrderTree bot = new BinaryOrderTree(array);
bot.preOrder(0);
System.out.println("-----------------------");
bot.infixOrder(0);
System.out.println("-----------------------");
bot.laterOrder(0);
}
private int[] array;
public BinaryOrderTree(int[] array) {
this.array = array;
}
public void preOrder(int index) {
if (array == null || array.length <= 0) {
System.out.println("数组为空");
return;
}
System.out.println(array[index]);
if (index * 2 + 1 < array.length) {
preOrder(index * 2 + 1);
}
if (index * 2 + 2 < array.length) {
preOrder(index * 2 + 2);
}
}
public void infixOrder(int index) {
if (array == null || array.length <= 0) {
System.out.println("数组为空");
return;
}
if (index * 2 + 1 < array.length) {
infixOrder(index * 2 + 1);
}
System.out.println(array[index]);
if (index * 2 + 2 < array.length) {
infixOrder(index * 2 + 2);
}
}
public void laterOrder(int index) {
if (array == null || array.length <= 0) {
System.out.println("数组为空");
return;
}
if (index * 2 + 1 < array.length) {
laterOrder(index * 2 + 1);
}
if (index * 2 + 2 < array.length) {
laterOrder(index * 2 + 2);
}
System.out.println(array[index]);
}
}
- 线索化二叉树
将普通二叉树中，左右节点为空的节点，赋值上前驱和后继节点
public class ThreadBinaryOrder {
public static void main(String[] args) {
ThreadBinaryOrder tbo = new ThreadBinaryOrder();
ThreadTreeNode root = new ThreadTreeNode(1, "Ralap01");
ThreadTreeNode ralap03 = new ThreadTreeNode(3, "Ralap03");
ThreadTreeNode ralap06 = new ThreadTreeNode(6, "Ralap06");
root.left = ralap03;
root.right = ralap06;
ThreadTreeNode ralap08 = new ThreadTreeNode(8, "ralap08");
ThreadTreeNode ralap10 = new ThreadTreeNode(10, "ralap10");
ThreadTreeNode ralap14 = new ThreadTreeNode(14, "ralap14");
ralap03.left = ralap08;
ralap03.right = ralap10;
ralap06.left = ralap14;
tbo.setRoot(root);
tbo.thread();
System.out.println(ralap08.left);
System.out.println(ralap08.right);
tbo.preThreadOrder(root);
}
private ThreadTreeNode root;
private ThreadTreeNode pre;
public ThreadBinaryOrder setRoot(ThreadTreeNode root) {
this.root = root;
return this;
}
public void thread() {
thread(root);
}
public void thread(ThreadTreeNode node) {
if (node == null) {
return;
}
thread(node.left);
if (node.left == null) {
node.left = pre;
node.leftType = 1;
}
if (pre != null && pre.right == null) {
pre.right = node;
pre.rightType = 1;
}
pre = node;
thread(node.right);
}
public void preThreadOrder(ThreadTreeNode node) {
while (node != null) {
while (node.leftType == 0) {
node = node.left;
}
System.out.println(node);
while (node.rightType == 1) {
node = node.right;
System.out.println(node);
}
node = node.right;
}
}
}
class ThreadTreeNode {
public int no;
public String name;
public ThreadTreeNode left;
public ThreadTreeNode right;
public int leftType;
public int rightType;
public ThreadTreeNode(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
final StringBuilder sb = new StringBuilder("ThreadTreeNode{");
sb.append("no=").append(no);
sb.append(", name='").append(name).append('\'');
sb.append(", leftType=").append(leftType);
sb.append(", rightType=").append(rightType);
sb.append('}');
return sb.toString();
}
}
网友评论