目录

一：树的介绍

二：二叉树的概念

三：二叉树的特点

3.1 二叉树的度

3.2 满二叉树

3.3 完全二叉树

四：树的存储结构

五：二叉树的应用案例

5.1 二叉排序树

5.2 二叉树遍历​

5.3 平衡二叉树

​六：链树（非顺序树）的案例实现

6.1 创建树的结点

6.2：树的操作（争对root）

6.3：树的测试

---

一：树的介绍

大的数组插入和删除的话需要进行大规模的数据移动

大的链表检索最后一个也需要进行大量的程序运行

所以：

二：二叉树的概念

结点的权：结点的值

结点的路径：从根找到目标结点的路线

树的高度：最大层数

森林：多棵子树 

三：二叉树的特点

3.1 二叉树的度

3.2 满二叉树

叶子结点都在最后一层，并且叶子结点的个数 = 2^(层数-1)

3.3 完全二叉树

叶子节点在倒数第一层或者倒数第二层，倒数第一层的叶子结点左边连续，倒数第二层的叶子结点右边连续

四：树的存储结构

满二叉树存储到数组中不浪费空间

非满二叉树适合采用链表进行存储

五：二叉树的应用案例

5.1 二叉排序树5.2 二叉树遍历5.3 平衡二叉树

将平衡因子改变的结点拿出来

六：链树（非顺序树）的案例实现

6.1 创建树的结点

package tree;
 
public class Node {
	private int id;
	private String name;
	private Node left;
	private Node right;
	public Node(int id, String name) {
		this.id = id;
		this.name = name;
	}
	
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}
	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 [id=" + id + ", name=" + name + ", left=" + left + ", right=" + right + "]";
	}
	
	
	//前序
	public void preSelect() {
		System.out.println(this);
		if(this.getLeft() != null) {
			this.getLeft().preSelect();
		}
		if(this.getRight() != null) {
			this.getRight().preSelect();
		}
	}
	//中序遍历
	public void indexSelect() {
		if(this.getLeft() != null) {
			this.getLeft().indexSelect();
		}
		System.out.println(this);
		if(this.getRight() != null) {
			this.getLeft().indexSelect();
		}
	}
	//后续遍历
	public void postSelect() {
		if(this.getLeft() != null) {
			this.getLeft().postSelect();
		}
		if(this.getRight() != null) {
			this.getLeft().postSelect();
		}
		System.out.println(this);
	}
	//前序遍历查找
	public Node preSearch(int no) {
		if(this.getId() == no) {
			return this;
		}
		Node node = null;
		if(this.getLeft() != null) {
			node = this.getLeft().preSearch(no);
		}
		if(node != null) {
			return node;
		}
		if(this.getRight() != null) {
			node = this.getRight().preSearch(no);
		}
		return node;
	}
	//中序遍历查找
	public Node indexSearch(int no) {
		Node node = null;
		if(this.getLeft() != null) {
			node = this.getLeft().indexSearch(no);
		}
		if(node != null) {
			return node;
		}
		if(this.getId() == no) {
			return this;
		}
		if(this.getRight() != null) {
			node = this.getRight().indexSearch(no);
		}
		return node;
	}
	//后序遍历查找
	public Node postSearch(int no) {
		Node node = null;
		if(this.getLeft() != null) {
			node = this.getLeft().postSearch(no);
		}
		if(node != null) {
			return node;
		}
		if(this.getRight() != null) {
			node = this.getRight().postSearch(no);
		}
		
		if(node != null) {
			return node;
		}
		
		if(this.getId() == no) {
			return this;
		}
		return node;
	}
	
	public void delNode(int no) {
		if(this.getLeft() != null && this.getLeft().id == no) {
			this.left = null;
			return;
		}
		if(this.getRight() != null && this.getRight().id == no) {
			this.right = null;
			return;
		}
		if(this.left != null) {
			this.getLeft().delNode(no);
		}
		if(this.right != null) {
			this.getRight().delNode(no);
		}
	}
	
}

6.2：树的操作（争对root）

此处删除只是类似文件删除操作，没有详细分解

package tree;
 
public class TreeNode {
	private Node root;
	
	public void setRoot(Node head) {
		this.root = head;
	}
	
	public void preSelect() {
		if(root == null) {
			System.out.println("该树为空，无法遍历...");
			return;
		}else {
			this.root.preSelect();
		}
	}
	public void indexSelect() {
		if(root == null) {
			System.out.println("该树为空，无法遍历...");
			return;
		}else {
			this.root.indexSelect();
		}
	}
	public void postSelect() {
		if(root == null) {
			System.out.println("该树为空，无法遍历...");
			return;
		}else {
			this.root.postSelect();
		}
	}
	
	public Node preSearch(int no) {
		if(root == null) {
			System.out.println("该树为空，无法遍历...");
			return null;
		}else {
			return root.preSearch(no);
		}
	}
	
	public Node indexSearch(int no) {
		if(root == null) {
			System.out.println("该树为空，无法遍历...");
			return null;
		}else {
			return root.indexSearch(no);
		}
	}
	public Node postSearch(int no) {
		if(root == null) {
			System.out.println("该树为空，无法遍历...");
			return null;
		}else {
			return root.postSearch(no);
		}
	}
	
	public void delNode(int no) {
		if(root == null) {
			System.out.println("该树为空，无法遍历...");
		}else {
			if(root.getId() == no) {
				root = null;
			}else {
				root.delNode(no);
			}
		}
	}
}

6.3：树的测试

package tree;
 
public class Test {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeNode tree = new TreeNode();
		Node n1 = new Node(1,"孙尚香");
		Node n2 = new Node(2,"吕布");
		Node n3 = new Node(3,"貂蝉");
		Node n4 = new Node(4,"关羽");
		Node n5 = new Node(5,"张飞");
		Node n6 = new Node(6,"刘备");
		
		tree.setRoot(n1);
		
		n1.setLeft(n2);
		n1.setRight(n3);
		n2.setLeft(n4);
		n2.setRight(n5);
		n3.setLeft(n6);
		
		tree.preSelect();
		Node node = tree.preSearch(6);
		if(node != null) {
			System.out.printf("查到该结点：id = " + node.getId() + ", name = " + node.getName() + "\n");
		}else {
			System.out.printf("未查到该节点\n");
		}
		
		tree.delNode(6);
		tree.preSelect();
		
	}
 
}