二叉树是一种动态的数据结构
二叉树的特点：
1.二叉树具有唯一的根结点
2.二叉树每一个结点最多有两个孩子（叶子结点没有孩子）
3.二叉树每一个结点至多有一个父亲
4.二叉树具有天然递归结构
5.每个结点的左右子树也是二叉树
6.一个层数为k的满二叉树总节点数为2的k次方减一
7.第i层的节点数为2的（i-1）次方
8.层数为k的满二叉树的叶子结点个数为2的k次方减一
class Node{
Integer val;
Node leftNode;//左孩子
Node rightNode;//右孩子
//构造方法初始化结点
public Node(Integer val) {
this.val = val;
this.leftNode=null;
this.rightNode=null;
}
public Node() {
}
}
二分搜索树
二分搜索树是一种二叉树；
二分搜索树的特点：
1.二分搜索树每一个结点的值大于其左节点的值；小于其右节点的值
2.二叉搜索树的每一个子树也是二叉搜索树
简言之，二叉搜索树是一个有插入规则的二叉树
Node root;
public void add(T val){
root = add(root,val);
}
private Node add(Node root, T val) {
//递归到底情况
if(null == root){
Node node = new Node(val);
return node;
}
//递归操作
if(val.compareTo(root.data) > 0){
root.right = add(root.right,val);
}else{
root.left = add(root.left, val);
}
return root;
}
查找二叉树中的元素并返回与目标值同值的子树
public Node isContains(T data){
return isContains(root,data);
}
private Node isContains(Node root, T data) {
//递归到底的情况
if(root == null){
return null;
}
if(data.compareTo(root.data) ==0){
return root;
}else if(data.compareTo(root.data)>0){
return isContains(root.right,data);
}else{
return isContains(root.left,data);
}
}
查找最大最小值结点
//查找最小结点,一直向左找
public Node getMin(){
return getMin(root);
}
private Node getMin(Node node) {
if (node.leftNode==null){
return node;
}else {
getMin(node.leftNode);
}
return node;
}
//查找最大值结点
public Node getMax(){
return getMax(root);
}
private Node getMax(Node node) {
if (node.rightNode==null){
return node;
}else {
getMin(node.rightNode);
}
return node;
}
public Node mixNodeDG(){
if(root==null){
return null;
}
return mixNodeDG(root);
}
private Node mixNodeDG(Node root) {
//递归到底
if(root.left ==null){
return root;
}
return mixNodeDG(root.left);
}
遍历
//前序遍历
private void prevOrderDG(Node root) {
if(root ==null){
return ;
}
System.out.print(root.data +" ");
prevOrderDG(root.left);
prevOrderDG(root.right);
}
//中序遍历
private void midOrderDG(Node root) {
//递归到底
if(root==null){
return ;
}
midOrderDG(root.left);
System.out.print(root.data +" ");
midOrderDG(root.right);
}
//后序遍历
public void backOrder(){
backOrderDG(root);
}
private void backOrderDG(Node root) {
if(root ==null){
return;
}
backOrderDG(root.left);
backOrderDG(root.right);
System.out.print(root.data+" ");
}
删除
删除大致分为四种情况
1.删除的值为叶子结点——直接删除
解决方法：
直接将要删除的结点置为null
2.删除只有左孩子的结点
解决办法：
使待删除结点被其左孩子替换
3.删除只有右孩子的结点
解决办法：
使待删除结点被其左孩子替换
4.删除左右孩子都有的结点
解决办法：
1.找到d的后继s
s—>s为其右子树中的最小值
2.将s的值与待删除结点的值所交换
3.将原s位置的结点置为空
public Node remove(T data){
if(root ==null){
return null;
}
Node delNode = isContains(data);
if(delNode !=null){
//删除操作
root = remove(data,root);
return delNode;
}else{
return null;
}
}
private Node remove(T data, Node node) {
//递归到底
if(data.equals(node.data)){
//1.要删除的节点只有左子树
if(node.right ==null){
Node delNode = node.left;
node.left =null;
return delNode;
}else if(node.left ==null){
//2.要删除的节点只有右子树
Node delNode = node.right;
node.right = null;
return delNode;
}else{
//3.要删除的节点左子树和右子树都不为空
Node backNode = mixNodeDG(node.right);
Node rootRight = mixNodeRemove(node.right);
backNode.left =node.left;
backNode.right = node.right;
node.left = node.right = null;
return backNode;
}
}
//递归操作
if(data.compareTo(node.data)>0){
node.right = remove(data,node.right);
}else {
node.left = remove(data,node.left);
}
return node;
}
private Node mixNodeRemove(Node node) {
if (node.left ==null){
Node rightNode = node.right;
node.right = null;
return rightNode;
}
node.left = mixNodeRemove(node.left);
return node;
}
完整代码
import java.util.LinkedList; import java.util.Stack; public class BinarySearchTree> { class Node { T data; Node left; Node right; public Node(T data){ this.data = data; this.right = this.left = null; } } Node root; public void add(T val){ root = add(root,val); } private Node add(Node root, T val) { //递归到底情况 if(null == root){ Node node = new Node(val); return node; } //递归操作 if(val.compareTo(root.data) > 0){ root.right = add(root.right,val); }else{ root.left = add(root.left, val); } return root; } public Node isContains(T data){ return isContains(root,data); } private Node isContains(Node root, T data) { //递归到底的情况 if(root == null){ return null; } if(data.compareTo(root.data) ==0){ return root; }else if(data.compareTo(root.data)>0){ return isContains(root.right,data); }else{ return isContains(root.left,data); } } public void midOrder(){ midOrderDG(root); System.out.println("n**********n"); minOrder(root); } public void minOrder(Node root){ Node node = root; Stack stack = new Stack<>(); while(node!=null || !stack.isEmpty()){ while(node !=null){ stack.push(node); node = node.left; } if(!stack.isEmpty()){ node = stack.pop(); System.out.print(node.data +" "); node = node.right; } } } private void midOrderDG(Node root) { //递归到底 if(root==null){ return ; } midOrderDG(root.left); System.out.print(root.data +" "); midOrderDG(root.right); } public void prevOrder(){ prevOrderDG(root); System.out.println("n----------"); prevOrder(root); } private void prevOrderDG(Node root) { if(root ==null){ return ; } System.out.print(root.data +" "); prevOrderDG(root.left); prevOrderDG(root.right); } public void prevOrder(Node root){ Node node = root; Stack stack = new Stack<>(); while (node!=null || !stack.isEmpty()) { while (node != null) { System.out.print(node.data + " "); stack.push(node); node = node.left; } if (!stack.isEmpty()) { node = stack.pop(); node = node.right; } } } public void backOrder(){ backOrderDG(root); } private void backOrderDG(Node root) { if(root ==null){ return; } backOrderDG(root.left); backOrderDG(root.right); System.out.print(root.data+" "); } public void layerOrder(){ Node node = root; LinkedList linkedList = new LinkedList<>(); linkedList.offer(node); while(!linkedList.isEmpty()){ node = linkedList.poll(); System.out.print(node.data+" "); if(node.left!=null){ linkedList.offer(node.left); } if(node.right!=null){ linkedList.offer(node.right); } } } public Node mixNodeDG(){ if(root==null){ return null; } return mixNodeDG(root); } private Node mixNodeDG(Node root) { //递归到底 if(root.left ==null){ return root; } return mixNodeDG(root.left); } public Node mixNode(){ if(root ==null){ return null; } Node node = root; while(node.left!=null){ node = node.left; } return node; } public Node remove(T data){ if(root ==null){ return null; } Node delNode = isContains(data); if(delNode !=null){ //删除操作 root = remove(data,root); return delNode; }else{ return null; } } private Node remove(T data, Node node) { //递归到底 if(data.equals(node.data)){ //1.要删除的节点只有左子树 if(node.right ==null){ Node delNode = node.left; node.left =null; return delNode; }else if(node.left ==null){ //2.要删除的节点只有右子树 Node delNode = node.right; node.right = null; return delNode; }else{ //3.要删除的节点左子树和右子树都不为空 Node backNode = mixNodeDG(node.right); Node rootRight = mixNodeRemove(node.right); backNode.left =node.left; backNode.right = node.right; node.left = node.right = null; return backNode; } } //递归操作 if(data.compareTo(node.data)>0){ node.right = remove(data,node.right); }else { node.left = remove(data,node.left); } return node; } private Node mixNodeRemove(Node node) { if (node.left ==null){ Node rightNode = node.right; node.right = null; return rightNode; } node.left = mixNodeRemove(node.left); return node; } }
