1、二叉树的定义:
二叉树是每个节点最多有两个子树的树结构。
特别地:
①除了最后一层节点外，其他节点的数目都达到了所在层的最大值，称为完全二叉树。同时，最后一层的所有节点必须从最后一层的左边开始。而不是说左边一个，右边一个，中间一个。(运用 : 二叉堆)
②除最后一层外，每一层上的所有结点都有两个子结点。这样的二叉树称为满二叉树。在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m－1个结点。(中外定义有所不同)
2、实现二叉树:
①定义一个节点类Node:
public class Node { int value; Node leftChild; Node rightChild; public Node(int value) { // TODO Auto-generated constructor stub this.value = value; } public void display() { System.out.println(this.value); } @Override public String toString() { // TODO Auto-generated method stub return String.valueOf(this.value); }} ②实现基本的二叉树操作:
public class BinaryTree { Node root = null; public BinaryTree(int rootValue) { // TODO Auto-generated constructor stub root = new Node(rootValue); root.leftChild = null; root.rightChild = null; } public Node findKey(int value) {} //查找 public String insert(int value) {} //插入 public void inOrderTraverse() {} //中序遍历递归操作 public void inOrderByStack() {} //中序遍历非递归操作 public void preOrderTraverse() {} //前序遍历 public void preOrderByStack() {} //前序遍历非递归操作 public void postOrderTraverse() {} //后序遍历 public void postOrderByStack() {} //后序遍历非递归操作 public int getMinValue() {} //得到最小(大)值 public boolean delete(int value) {} //删除 } ③查找操作:
public Node findKey(int value) { Node current = root; while(true) { if(value == current.value) return current; else if(value < current.value) current = current.leftChild; else // vale > current.value current = current.rightChild; if(current == null) return null; } } //查找 ④插入操作
public void insert(int value) { /** * 核心思想: * 1、如果不存在节点，则直接插入。 * 2、从根开始查找一个节点，即新节点的父节点，当父节点找到后，根据节点的值来确定插入左节点还是右节点。 */ Node node = new Node(value); if(root == null) { root = node; root.leftChild = null; root.rightChild = null; } else { Node current = root; while(true) { if(value < current.value) { current = current.leftChild; if(current == null) { current = node; break; } } else if(value > current.value) { current = current.rightChild; if(current == null) { current = node; break; } } else { System.out.println("having value in this BinaryTree"); break; } } } } //插入 ⑤中序遍历:
public void inOrderTraverse() { /** * //中序遍历(递归)： * 1、调用自身来遍历节点的左子树 * 2、访问这个节点 * 3、调用自身来遍历节点的右子树 */ System.out.print("中序遍历:"); inOrderTraverse(root); System.out.println(); } //中序遍历递归操作 private void inOrderTraverse(Node node) { if(node == null) return; inOrderTraverse(node.leftChild); node.display(); inOrderTraverse(node.rightChild); }
⑥前序遍历:
public void preOrderTraverse() { /** * //前序遍历(递归)： * 1、访问这个节点 * 2、调用自身来遍历节点的左子树 * 3、调用自身来遍历节点的右子树 */ System.out.println("前序遍历:"); preOrderTraverse(root); System.out.println(); } //前序遍历 private void preOrderTraverse(Node node) { if(node == null) return; node.display(); preOrderTraverse(node.leftChild); preOrderTraverse(node.rightChild); } ⑦后序遍历:
public void postOrderTraverse() { /** * //后序遍历(递归)： * 1、调用自身来遍历节点的左子树 * 2、调用自身来遍历节点的右子树 * 3、访问这个节点 */ System.out.println("后序遍历:"); postOrderTraverse(root); System.out.println(); } //后序遍历 private void postOrderTraverse(Node node) { if(node == null) return; postOrderTraverse(node.leftChild); postOrderTraverse(node.rightChild); node.display(); } ⑧得到最小值
public int getMinValue() { Node current = root; while(true) { if(current.leftChild == null) return current.value; else current = current.leftChild; } } //得到最小(大)值 ⑨删除操作
后补...