三个问题
- 二叉树按层遍历
- 给定指定n个节点，二叉树有多少种组合
- 二叉树插入删除，保持顺序
思路
- 通过队列保存缓存结果，从root节点开始，然后进队出队，输出结果同时左节点进队右节点进队，直到队列为空。
public void printByLayer() {
Queue<TreeStruct> queue = new LinkedList<>();
queue.offer(this);
TreeStruct temp;
while (queue.size() > 0) {
temp = queue.poll();
assert temp != null;
System.out.println(temp.value);
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
}
-
对于第二个问题，已看到就会想到n！。但是二叉树不是完全二叉树。
卡特兰数
f(0)=1;f(1) = 1;
n个数字，1个在根节点其他可能情况。0个在左，n-1个在右；1个在左，n-2个在右；2个在左，n-3个在右。。。
f(n) = f(0)f(n-1) + f(1)f(n-2) + ... + f(n-2)f(1) + f(n-1)f(0)
Cn = (2n)!/((n+1)!*n!) -
插入node，大于等于在右叶子，小于根节点在左叶子。删除节点，1.左右节点空，直接删除；2.左节点空，右节点不为空，找到右节点中最小的替换到删除节点位置；3.左节点不为空，右节点为空，找到左节点中最大的替换到删除节点位置；4.左右节点都不为空，同3一样
Code
public class TreeStruct {
public TreeStruct() {
}
public TreeStruct(Integer value) {
this.value = value;
}
private Integer value;
private TreeStruct left;
private TreeStruct right;
/**
* 按层输出
*/
public void printByLayer() {
Queue<TreeStruct> queue = new LinkedList<>();
queue.offer(this);
TreeStruct temp;
while (queue.size() > 0) {
temp = queue.poll();
assert temp != null;
System.out.println(temp.value);
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
}
public void printByLayer(Consumer<Integer> consumer) {
Queue<TreeStruct> queue = new LinkedList<>();
queue.offer(this);
TreeStruct temp;
while (queue.size() > 0) {
temp = queue.poll();
assert temp != null;
consumer.accept(temp.value);
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
}
/**
* 遍历
*/
public void travel() {
travelRecursion(this);
}
/**
* 前序遍历
*/
private void travelRecursion(TreeStruct node) {
if (node != null) {
System.out.println(node.value);
travelRecursion(node.getLeft());
travelRecursion(node.getRight());
}
}
/**
* 查找
*/
public TreeStruct find(Integer value) {
TreeStruct node = this;
while (node != null) {
if (node.getValue() > value) {
node = node.getLeft();
} else if (node.getValue() < value) {
node = node.getRight();
} else {
return node;
}
}
return null;
}
/**
* 插入node，大于等于在右叶子，小于根节点在左叶子
*/
public void insertNode(Integer value) {
TreeStruct node = this;
while (node != null) {
if (node.getValue() == null) {
node.setValue(value);
break;
}
if (node.getValue() < value) {
if (node.getRight() == null) {
node.setRight(new TreeStruct(value));
node = null;
} else {
node = node.getRight();
}
} else {
if (node.getLeft() == null) {
node.setLeft(new TreeStruct(value));
node = null;
} else {
node = node.getLeft();
}
}
}
}
/**
* 删除1个节点，不删除重复数据
*/
public void deleteNode(Integer value) {
TreeStruct pre = null;
TreeStruct node = this;
while (node != null) {
if (node.getValue() > value) {
pre = node;
node = node.getLeft();
} else if(node.getValue() < value) {
pre = node;
node = node.getRight();
} else {
if (node.getLeft() == null) {
if (node.getRight() == null) {
if (pre == null) {
this.value = null;
} else {
if (pre.getLeft() == node) {
pre.setLeft(null);
} else if (pre.getRight() == node){
pre.setRight(null);
}
}
} else {
// left == null && right != null
// find right minimum element
TreeStruct tempPre = null;
TreeStruct temp = node.getRight();
while (temp.getLeft() != null) {
tempPre = temp;
temp = temp.getLeft();
}
// remove temp
if (tempPre != null) {
tempPre.setLeft(null);
} else {
node.setRight(null);
}
// move temp to node
temp.setLeft(node.getLeft());
temp.setRight(node.getRight());
if (pre != null) {
if (pre.getLeft() == node) {
pre.setLeft(temp);
} else if (pre.getRight() == node) {
pre.setRight(temp);
}
}
}
} else {
// left != null && right == null || left != null && right != null
// find left maximum element
TreeStruct tempPre = null;
TreeStruct temp = node.getLeft();
while (temp.getRight() != null) {
tempPre = temp;
temp = temp.getRight();
}
// remove temp
if (tempPre != null) {
tempPre.setRight(null);
} else {
node.setLeft(null);
}
// move temp to node
temp.setLeft(node.getLeft());
temp.setRight(node.getRight());
if (pre != null) {
if (pre.getLeft() == node) {
pre.setLeft(temp);
} else if (pre.getRight() == node) {
pre.setRight(temp);
}
} else {
this.value = temp.getValue();
}
}
break;
}
}
}
/**
* 数高
*/
public Integer height() {
return height(this);
}
private Integer height(TreeStruct treeStruct) {
if (treeStruct == null) {
return 0;
} else {
Integer leftHeight = height(treeStruct.getLeft());
Integer rightHeight = height(treeStruct.getRight());
return leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1;
}
}
}
网友评论