树
数组存储：
优点：访问数据速度很快，可以随机访问，也可以通过二分法来提高检索速度。
缺点：增删数据数组会整体移动，效率很低。扩容困难
链表存储：
优点：插入删除简单，扩容简单
缺点：查询数据，需要检索整个链表，效率低
树存储：
树是以链表的形式存储数据
优点：
- 插入删除简便
- 扩容简单
- 查询数据效率高（其实就是二分检索的形式）
实现：二叉树
- 前中后序遍历
- 删除节点（简单版本）
- 这里默认删除的是叶子节点。
- 如果是父节点直接删除这棵子树。
- 查找对应的节点
Node：节点
class Node{
private int no;
private String name;
private Node left;
private Node right;
public Node(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
//前序遍历
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 postOrder(){
if (this.left!=null){
this.left.postOrder();
}
if (this.right!=null){
this.right.postOrder();
}
System.out.println(this);
}
//前序查找
public Node preOrderSearch(int no){
System.out.println("前序查找~~~");
//先检查父节点
if (this.getNo()==no){
return this;
}
//左节点
Node temp = null;
if (this.left!=null){
temp = this.left.preOrderSearch(no);
}
//判断做边是否已经找到对应的节点，如果没有找到就遍历右节点。
if (temp!=null){
return temp;
}
//右节点
if (this.right!=null){
temp = this.right.preOrderSearch(no);
}
return temp;
}
//中序查找
public Node infixOrderSearch(int no){
//左节点
Node temp = null;
if (this.left!=null){
temp = this.left.infixOrderSearch(no);
}
//判断做边是否已经找到对应的节点，如果没有找到就遍历右节点。
if (temp!=null){
return temp;
}
System.out.println("中序查找~~~");
//先检查父节点
if (this.getNo()==no){
return this;
}
//右节点
if (this.right!=null){
temp = this.right.infixOrderSearch(no);
}
return temp;
}
//后序查找
public Node postOrderSearch(int no){
//左节点
Node temp = null;
if (this.left!=null){
temp = this.left.postOrderSearch(no);
}
//判断做边是否已经找到对应的节点，如果没有找到就遍历右节点。
if (temp!=null){
return temp;
}
//右节点
if (this.right!=null){
temp = this.right.postOrderSearch(no);
}
//判断做边是否已经找到对应的节点，如果没有找到就遍历右节点。
if (temp!=null){
return temp;
}
System.out.println("后序查找~~~");
//先检查父节点
if (this.getNo()==no){
return this;
}
return temp;
}
}
BinaryTree：二叉树
//定义二叉树
class BinaryTree{
private Node root;
public BinaryTree(Node root) {
this.root = root;
}
//前序遍历
public void preOrder(){
if (this.root!=null){
this.root.preOrder();
}else {
System.out.println("树为空");
}
}
//中序遍历
public void infixOrder(){
if (this.root!=null){
this.root.infixOrder();
}else {
System.out.println("树为空");
}
}
//后序遍历
public void postOrder(){
if (this.root!=null){
this.root.postOrder();
}else {
System.out.println("树为空");
}
}
//前序遍历搜索
public Node preOrderSearch(int no){
if (this.root!=null){
return this.root.preOrderSearch(no);
}else {
return null;
}
}
//中序遍历搜索
public Node infixOrderSearch(int no){
if (this.root!=null){
return this.root.infixOrderSearch(no);
}else {
return null;
}
}
//后序遍历搜索
public Node postOrderSearch(int no){
if (this.root!=null){
return this.root.postOrderSearch(no);
}else {
return null;
}
}
}
测试：
public class BinaryTreeDemo {
public static void main(String[] args) {
Node node1 = new Node(1,"1");
Node node2 = new Node(2,"2");
Node node3 = new Node(3,"3");
Node node4 = new Node(4,"4");
Node node5 = new Node(5,"5");
node1.setLeft(node2);
node1.setRight(node3);
node3.setLeft(node4);
node3.setRight(node5);
BinaryTree binaryTree = new BinaryTree(node1);
System.out.println("前序遍历");
binaryTree.preOrder();
System.out.println("中序遍历");
binaryTree.infixOrder();
System.out.println("后序遍历");
binaryTree.postOrder();
System.out.println("查找5号");
System.out.println(binaryTree.preOrderSearch(3));
System.out.println(binaryTree.infixOrderSearch(3));
System.out.println(binaryTree.postOrderSearch(3));
}
}
image-20200729213302142.png
顺序存储二叉树
以数组的形式来存储二叉树
image-20200729213724567.png
顺序存储二叉树的特点：
- 一般我们只考虑完全二叉树
- 第n个节点的左子节点为2*n+1
- 第n个节点的右子节点为2*n+2
- 第N个节点父节点（n-1）/2
- 由于我们的数组中的下标从0开始所以左右节点的表示方式发生点改变
实现：数组存储的树 实现 前序遍历
ArrBinaryTree：
class ArrBinaryTree{
private int[] arr;
public ArrBinaryTree(int[] arr) {
this.arr = arr;
}
//重载preOrder
public void preOrder(){
this.preOrder(0);
}
public void preOrder(int index){
if (arr.length==0){
System.out.println("数组为空");
return;
}
System.out.print(arr[index]+" ");
if (2*index+1<arr.length){
preOrder(2*index+1);
}
if (2*index+2<arr.length){
preOrder(2*index+2);
}
}
}
测试：
public class ArrBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7};
ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
arrBinaryTree.preOrder();
}
}
image-20200729214304775.png
线索化二叉树
用来充分利用空闲的指针
- n个节点的二叉链表中含有n+1个空指针域
- 利用二叉树的空指针域指向该节点再某种遍历次序下的前驱和后继节点的指针
- 这种加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树
threadNode:线索化节点
public void threadNode(Node node){
if (node==null){
return;
}
//递归左节点
threadNode(node.getLeft());
//处理前驱节点
if (node.getLeft()==null){
node.setLeft(pre);
node.setLeftType(1);
}
// 处理后继节点
if (pre!=null && pre.getRight()==null){
pre.setRight(node);
pre.setRightType(1);
}
pre = node;
//递归右节点
threadNode(node.getRight());
}
threadList:遍历线索二叉树
image-20200729211215844.png
public void threadList(){
Node node = root;
while (node!=null){
while (node.getLeftType()==0){
node = node.getLeft();
}
System.out.println(node);
while (node.getRightType()==1){
node = node.getRight();
System.out.println(node);
}
//!!!!
node = node.getRight();
}
}
测试
public class ThreadBinaryTreeDemo {
public static void main(String[] args) {
Node node1 = new Node(1,"1");
Node node2 = new Node(2,"2");
Node node3 = new Node(3,"3");
Node node4 = new Node(4,"4");
Node node5 = new Node(5,"5");
Node node6 = new Node(6,"6");
node1.setLeft(node2);
node1.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setRight(node6);
ThreadBinaryTree threadBinaryTree = new ThreadBinaryTree(node1);
threadBinaryTree.threadNode();
threadBinaryTree.threadList();
}
}
网友评论