三個(gè)問題
- 二叉樹按層遍歷
- 給定指定n個(gè)節(jié)點(diǎn)，二叉樹有多少種組合
- 二叉樹插入刪除竹握，保持順序
思路
- 通過隊(duì)列保存緩存結(jié)果画株，從root節(jié)點(diǎn)開始，然后進(jìn)隊(duì)出隊(duì)，輸出結(jié)果同時(shí)左節(jié)點(diǎn)進(jìn)隊(duì)右節(jié)點(diǎn)進(jìn)隊(duì)谓传，直到隊(duì)列為空蜈项。
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);
}
}
}
對(duì)于第二個(gè)問題，已看到就會(huì)想到n续挟！紧卒。但是二叉樹不是完全二叉樹。
卡特蘭數(shù)
f(0)=1;f(1) = 1;
n個(gè)數(shù)字诗祸，1個(gè)在根節(jié)點(diǎn)其他可能情況跑芳。0個(gè)在左，n-1個(gè)在右直颅；1個(gè)在左博个，n-2個(gè)在右；2個(gè)在左际乘，n-3個(gè)在右坡倔。。脖含。
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罪塔，大于等于在右葉子，小于根節(jié)點(diǎn)在左葉子养葵。刪除節(jié)點(diǎn)征堪，1.左右節(jié)點(diǎn)空，直接刪除关拒；2.左節(jié)點(diǎn)空佃蚜，右節(jié)點(diǎn)不為空，找到右節(jié)點(diǎn)中最小的替換到刪除節(jié)點(diǎn)位置着绊；3.左節(jié)點(diǎn)不為空谐算，右節(jié)點(diǎn)為空，找到左節(jié)點(diǎn)中最大的替換到刪除節(jié)點(diǎn)位置归露；4.左右節(jié)點(diǎn)都不為空洲脂，同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，大于等于在右葉子剧包，小于根節(jié)點(diǎn)在左葉子
*/
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個(gè)節(jié)點(diǎn)恐锦，不刪除重復(fù)數(shù)據(jù)
*/
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;
}
}
}
/**
* 數(shù)高
*/
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;
}
}
}
