1.二叉树的遍历：前序、中序、后序遍历
public class BinaryTree {
private TreeModle root;
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.createBinaryTree();
System.out.println("height:" + binaryTree.getHeight());
System.out.println("size:" + binaryTree.getSize());
// binaryTree.preorder(binaryTree.root);
// System.out.println("------------------");
// binaryTree.midorder(binaryTree.root);
// System.out.println("------------------");
// binaryTree.nextorder(binaryTree.root);
// System.out.println("------------------");
// binaryTree.noPreOrder(binaryTree.root);
ArrayList<String> data = new ArrayList<>();
String[] s = {"A", "B", "D", "#", "#", "E", "#", "#", "C", "#", "F","#","#"};
for (int i = 0; i < s.length; i++) {
data.add(s[i]);
}
binaryTree.createBinaryTreePre(data);
binaryTree.preorder(binaryTree.root);
}
public BinaryTree() {
root = new TreeModle(1, "A");
}
/**
* 构建二叉树
* <p>
* A
* B C
* D E F
*/
public void createBinaryTree() {
TreeModle nodeB = new TreeModle(2, "B");
TreeModle nodeC = new TreeModle(3, "C");
TreeModle nodeD = new TreeModle(4, "D");
TreeModle nodeE = new TreeModle(5, "E");
TreeModle nodeF = new TreeModle(6, "F");
root.leftTreeModle = nodeB;
root.rightTreeModle = nodeC;
nodeB.leftTreeModle = nodeD;
nodeB.rightTreeModle = nodeE;
nodeC.rightTreeModle = nodeF;
}
/**
* 返项创建二叉树（ABD##E##C#F##）
* @param data
*/
public void createBinaryTreePre(ArrayList<String> data) {
createBinaryTree(data.size(), data);
}
private TreeModle createBinaryTree(int size, ArrayList<String> data) {
if (data.size() == 0) {
return null;
}
String d = data.get(0);
int index = size - data.size();
TreeModle treeModle;
if (d.equals("#")) {
treeModle = null;
data.remove(0);
return treeModle;
}
treeModle = new TreeModle(index, d);
if (index == 0) {
//创建根节点
root = treeModle;
}
data.remove(0);
treeModle.leftTreeModle = createBinaryTree(size, data);
treeModle.rightTreeModle = createBinaryTree(size, data);
return treeModle;
}
/**
* 求二叉树的高度
*/
public int getHeight() {
return getHeight(root);
}
private int getHeight(TreeModle treeModle) {
if (treeModle == null) {
return 0;
} else {
int i = getHeight(treeModle.leftTreeModle);
int j = getHeight(treeModle.rightTreeModle);
return (i < j) ? j + 1 : i + 1;
}
}
/**
* 获取二叉树的节点数
*/
public int getSize() {
return getSize(root);
}
private int getSize(TreeModle treeModle) {
if (treeModle == null) {
return 0;
} else {
return 1 + getSize(treeModle.leftTreeModle) + getSize(treeModle.rightTreeModle);
}
}
/**
* 前序遍历二叉树---迭代(跟左右)
*/
public void preorder(TreeModle root) {
if (root == null) {
return;
}
System.out.println(root.getData());
preorder(root.leftTreeModle);
preorder(root.rightTreeModle);
}
/**
* 前序遍历二叉树---非迭代
*/
public void noPreOrder(TreeModle root) {
if (root == null) {
return;
}
Stack<TreeModle> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
//弹出和入栈
TreeModle pop = stack.pop();
System.out.println(pop.getData());
if (pop.rightTreeModle != null) {
stack.push(pop.rightTreeModle);
}
if (pop.leftTreeModle != null) {
stack.push(pop.leftTreeModle);
}
}
}
/**
* 中序遍历二叉树---迭代(左跟右)
*/
public void midorder(TreeModle treeModle) {
if (treeModle == null) {
return;
}
midorder(treeModle.leftTreeModle);
System.out.println(treeModle.getData());
midorder(treeModle.rightTreeModle);
}
/**
* 后续遍历---迭代（左右跟）
*/
public void nextorder(TreeModle treeModle) {
if (treeModle == null) {
return;
}
nextorder(treeModle.leftTreeModle);
nextorder(treeModle.rightTreeModle);
System.out.println(treeModle.getData());
}
class TreeModle {
public int index;
public String data;
public TreeModle leftTreeModle;
public TreeModle rightTreeModle;
public TreeModle(int index, String data) {
this.index = index;
this.data = data;
this.leftTreeModle = null;
this.rightTreeModle = null;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public TreeModle getLeftTreeModle() {
return leftTreeModle;
}
public void setLeftTreeModle(TreeModle leftTreeModle) {
this.leftTreeModle = leftTreeModle;
}
public TreeModle getRightTreeModle() {
return rightTreeModle;
}
public void setRightTreeModle(TreeModle rightTreeModle) {
this.rightTreeModle = rightTreeModle;
}
}
}
2.二叉树查找节点和删除节点的代码
public class SearchBinaryTree {
private TreeNode root;
public static void main(String[] args) {
SearchBinaryTree binaryTree = new SearchBinaryTree();
int[] arrays = {55, 22, 88, 66, 1, 5, 50};
for (int s : arrays) {
binaryTree.put(s);
}
binaryTree.midBinaryTree(binaryTree.root);
try {
binaryTree.deleteNode(22);
binaryTree.midBinaryTree(binaryTree.root);
} catch (Exception e) {
e.printStackTrace();
}
}
public SearchBinaryTree() {
}
/**
* 删除节点
*
* @param key
*/
public void deleteNode(int key) throws Exception {
//首先查找该节点是否存在
TreeNode node = searchNode(key);
if (node == null) {//不存在，拋异常
throw new Exception("该节点不存在");
} else {//存在，删除该节点
deleteKey(node);
}
}
/**
* 存在，删除该节点
*
* @param node
* @throws Exception
*/
private void deleteKey(TreeNode node) throws Exception {
if (node == null) {
throw new Exception("该节点不存在");
} else {
TreeNode parent = node.parent;
//第一种，无左无右
if (node.leftChild == null && node.rightChild == null) {
//如果父节点的左边等于删除节点，则将父节点的左边设置为空
if (parent.leftChild == node) {
parent.leftChild = null;
} else {
//如果父节点的右边等于删除节点，则将父节点的右边设置为空
parent.rightChild = null;
}
return;
}
//第二种，有左无右
if (node.leftChild != null && node.rightChild == null) {
if (parent.leftChild == node) {
parent.leftChild = node.leftChild;
} else {
parent.rightChild = node.leftChild;
}
return;
}
//第三种,有右无左
if (node.leftChild == null && node.rightChild != null) {
if (parent.leftChild == node) {
parent.leftChild = node.rightChild;
} else {
parent.rightChild = node.rightChild;
}
return;
}
//第四种，有左有右
TreeNode next = getNextNode(node);
deleteKey(next);
node.data = next.data;
}
}
/**
* 有左有右下获取后继节点
*
* @param node
* @return
*/
private TreeNode getNextNode(TreeNode node) {
if (node == null) {
return null;
} else {
if (node.rightChild != null) {
return getMinTreeNode(node.rightChild);
} else {
TreeNode parent = node.parent;
while (parent != null && node == parent.rightChild) {
node = parent;
parent = parent.parent;
}
return parent;
}
}
}
/**
* 当删除节点有左右节点，并且有节点不为空的情况下，找最小节点
*
* @param node
* @return
*/
private TreeNode getMinTreeNode(TreeNode node) {
//当删除节点的右节点不为空时，循环去查找节点的左节点，直到为空为止
if (node == null) {
return null;
} else {
while (node.leftChild != null) {
node = node.leftChild;
}
}
return node;
}
/**
* 查找该节点是否存在
*
* @param key
* @return
*/
private TreeNode searchNode(int key) {
TreeNode node = root;
if (node == null) {
return null;
} else {
while (node != null && key != node.data) {
if (key < node.data) {//如果该节点小于根节点,取左边
node = node.leftChild;
} else {//该节点大于根节点，取右边
node = node.rightChild;
}
}
}
return node;
}
/**
* 查找二叉树
*
* @param data
* @return
*/
public TreeNode put(int data) {
TreeNode node = null;
TreeNode parent = null;
if (root == null) {
//创建根节点,然后return掉，不走下面的了
node = new TreeNode(0, data);
root = node;
return node;
}
node = root;
while (node != null) {
parent = node;//作为父节点
//不为空去判断传进来的数据和其相比
if (data > node.data) {//传进来的数据大，放在根节点的右边，给TreeNode对象重新赋值后再去遍历
node = node.rightChild;
} else if (data < node.data) {//传来的数据小于父节点，放在左边，给TreeNode对象重新赋值后再去遍历
node = node.leftChild;
} else if (data == node.data) {
return node;
}
}
//循环结束后，代表要存放该数据
//创建新的节点
node = new TreeNode(0, data);
if (data > parent.data) {
parent.rightChild = node;
} else if (data < parent.data) {
parent.leftChild = node;
}
node.parent = parent;
return node;
}
public void midBinaryTree(TreeNode node) {
if (node == null) {
return;
}
midBinaryTree(node.leftChild);
System.out.println(node.data);
midBinaryTree(node.rightChild);
}
class TreeNode {
public int data;
public TreeNode leftChild;
public TreeNode rightChild;
public TreeNode parent;
private int key;
public TreeNode(int key, int data) {
this.data = data;
this.key = key;
this.leftChild = null;
this.rightChild = null;
this.parent = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
}
}
网友评论