树的相关术语

树的度： 树中所有结点的度的最大值树的高度(深度)： 树中结点的最大层次结点的度： 一个结点含有的子树的个数称为该结点的度；叶结点： 度为0的结点称为叶结点，也可以叫做终端结点分支结点： 度不为0的结点称为分支结点，也可以叫做非终端结点结点的层次： 从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推孩子结点： 一个结点的直接后继结点称为该结点的孩子结点双亲结点(父结点)： 一个结点的直接前驱称为该结点的双亲结点兄弟结点： 同一双亲结点的孩子结点间互称兄弟结点

二叉树

度不超过2的树(每个结点最多有两个子结点)

满二叉树

一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。（叶子节点一定在最下层）

完全二叉树

叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

二叉搜索树

又叫二叉排序树，二叉查找树

定义 （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；

简单讲： 每一个分支树必须保证的大小顺序是，左子节点<跟节点<右子节点

左子树的所有节点比根节点小，右子树的所有节点比根节点大

建树的代码实现过程依据定义

如果根节点为空，此数据作为根节点如果根节点不为空，比较此数据与根节点的值 如果大于根节点的值，判断根节点的右子树否则，判断根节点的左子树

代码中有详细注释

Java代码

构建二叉搜索树

public void put(T item){ root = put(root,item); } private Node<T> put(Node<T> x , T item){ if(x==null){ size++; return new Node<T>(item,null,null); }else{ int cmp = item.compareTo(x.item); if(cmp>0){ //传入数据大于当前根节点的值,写入右子树 x.right = put(x.right,item); }else{ //传入数据小于当前根节点的值,写入右子树 x.left = put(x.left,item); } return x; } }

查找元素

//查找某个元素 public Node<T> get(T target){ return find(root,target); } private Node<T> find(Node<T> x,T target){ if(x == null) return null; if(target.compareTo(x.item)==0){ //找到目标值 return x; }else if(target.compareTo(x.item)>0){ //目标值比当前节点大，查找右子树 return find(x.right,target); }else{ //目标值比当前节点小，查找左子树 return find(x.left,target); } }

前序遍历

//前序遍历 public void prePrint(){ prePrint(root); System.out.println(); } public void prePrint(Node<T> x){ if(x==null){ return ; } System.out.print(x.item+" "); prePrint(x.left); prePrint(x.right); }

中序遍历

二叉搜索树的中序遍历是升序的

//中序遍历 public void midPrint(){ midPrint(root); System.out.println(); } private void midPrint(Node<T> x){ if(x==null){ return ; } midPrint(x.left); System.out.print(x.item+" "); midPrint(x.right); }

后续遍历

//后序遍历 public void afterPrint(){ afterPrint(root); System.out.println(); } public void afterPrint(Node<T> x){ if(x==null){ return ; } afterPrint(x.left); afterPrint(x.right); System.out.print(x.item+" "); }

层序遍历

创建一个队列，存入根节点判断队列是否为空， 队列为空，结束队列不为空，弹出队列第一个节点，并输出 如果当前节点的左子节点不为空，将左子节点存入队列如果当前节点的右子节点不为空，将右子节点存入队列递归调用 ，判断队列是否为空。 //层序遍历 public void layerPrint(){ ArrayList<Node<T>> ts = new ArrayList<>(); ts.add(root); layerPrint(ts); System.out.println(); } private void layerPrint(List<Node<T>> ts){ if(!ts.isEmpty()){ Node<T> remove = ts.remove(0); System.out.print(remove.item+" "); if(remove.left!=null){ ts.add(remove.left); } if(remove.right!=null){ ts.add(remove.right); } layerPrint(ts); } }

二叉搜索树完整代码

import java.util.ArrayList; import java.util.List; //节点类 class Node<T>{ T item; Node<T> left; Node<T> right; public Node(T item,Node<T> left,Node<T> right){ this.item = item; this.left = left; this.right = right; } } //二叉搜索树 public class BinaryTree<T extends Comparable<T>> { private Node<T> root; private int size; public void put(T item){ root = put(root,item); } private Node<T> put(Node<T> x , T item){ if(x==null){ size++; return new Node<T>(item,null,null); }else{ int cmp = item.compareTo(x.item); if(cmp>0){ //传入数据大于当前根节点的值,写入右子树 x.right = put(x.right,item); }else{ //传入数据小于当前根节点的值,写入右子树 x.left = put(x.left,item); } return x; } } //查找某个元素 public Node<T> get(T target){ return find(root,target); } private Node<T> find(Node<T> x,T target){ if(x == null) return null; if(target.compareTo(x.item)==0){ //找到目标值 return x; }else if(target.compareTo(x.item)>0){ //目标值比当前节点大，查找右子树 return find(x.right,target); }else{ //目标值比当前节点小，查找左子树 return find(x.left,target); } } //中序遍历 public void midPrint(){ midPrint(root); System.out.println(); } private void midPrint(Node<T> x){ if(x==null){ return ; } midPrint(x.left); System.out.print(x.item+" "); midPrint(x.right); } //前序遍历 public void prePrint(){ prePrint(root); System.out.println(); } public void prePrint(Node<T> x){ if(x==null){ return ; } System.out.print(x.item+" "); prePrint(x.left); prePrint(x.right); } //后序遍历 public void afterPrint(){ afterPrint(root); System.out.println(); } public void afterPrint(Node<T> x){ if(x==null){ return ; } afterPrint(x.left); afterPrint(x.right); System.out.print(x.item+" "); } //层序遍历 public void layerPrint(){ ArrayList<Node<T>> ts = new ArrayList<>(); ts.add(root); layerPrint(ts); System.out.println(); } private void layerPrint(List<Node<T>> ts){ if(!ts.isEmpty()){ Node<T> remove = ts.remove(0); System.out.print(remove.item+" "); if(remove.left!=null){ ts.add(remove.left); } if(remove.right!=null){ ts.add(remove.right); } layerPrint(ts); } } public static void main(String[] args) { BinaryTree<Integer> binaryTree = new BinaryTree<>(); binaryTree.put(3); binaryTree.put(5); binaryTree.put(8); binaryTree.put(7); binaryTree.put(1); binaryTree.put(4); binaryTree.put(2); System.out.print("中序遍历："); binaryTree.midPrint(); System.out.print("前序遍历："); binaryTree.prePrint(); System.out.print("后序遍历："); binaryTree.afterPrint(); System.out.print("层序遍历："); binaryTree.layerPrint(); System.out.println("==============查找================="); Node<Integer> node1 = binaryTree.get(4); if(node1!=null){ System.out.println(node1.item); }else{ System.out.println("没找到4"); } Node<Integer> node2 = binaryTree.get(9); if(node2!=null){ System.out.println(node2.item); }else{ System.out.println("没找到9"); } Node<Integer> node3 = binaryTree.get(6); if(node3!=null){ System.out.println(node3.item); }else{ System.out.println("没找到6"); } Node<Integer> node4 = binaryTree.get(0); if(node4!=null){ System.out.println(node4.item); }else{ System.out.println("没找到0"); } Node<Integer> node5 = binaryTree.get(5); if(node1!=null){ System.out.println(node5.item); }else{ System.out.println("没找到5"); } } }

测试结果

对 3，5，8，7，1，4，2 建树