学习笔记——二叉树相关算法的实现(Java语言版)

二叉树遍历概念和算法遍历(Traverse):所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:⑴访问结点本身(D),⑵遍历该结点的左子树(L),⑶遍历该结点的右子树(R)。先序/根遍历DLR:根左子树右子树中序/根遍历LD...

学习笔记——二叉树相关算法的实现(Java语言版)

二叉树遍历概念和算法

遍历(Traverse):

  所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。

  从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。

  因此,在任一给定结点上,可以按某种次序执行三个操作:

    ⑴ 访问结点本身(D),
    ⑵ 遍历该结点的左子树(L),
    ⑶ 遍历该结点的右子树(R)。
  先序/根遍历DLR:根 左子树 右子树
  中序/根遍历LDR:左子树 根 右子树
  后根/序遍历LRD:左子树 右子树 根
  注意:由于树的递归定义,其实对三种遍历的概念其实也是一个递归的描述过程

算法实现:

二叉树结点类

/** * 二叉链表的结点 * @author shangyang * */public class Node {  Object value;  // 结点值 Node leftChild;  // 左子树的引用 Node rightChild; // 右子树的引用  public Node(Object value) {  super();  this.value = value; } public Node(Object value, Node leftChild, Node rightChild) {  super();  this.value = value;  this.leftChild = leftChild;  this.rightChild = rightChild; } @Override public String toString() {  return "Node [value="value", leftChild="leftChild", rightChild="rightChild"]"; }}

二叉树方法接口类

/** * 二叉树的接口 * 可以有不同的实现类,每个类可以使用不同的存储结构,比如顺序结构、链式结构 * @author shangyang * */public interface BinaryTree { /**  * 是否为空树  */ public boolean isEmpty();  /**  * 树结点数量  */ public int size();  /**  * 获取树的高度  */ public int getHeight();  /**  * 查询指定值的结点  * @param value  * @return  */ public Node findKey(Object value);  /**  * 前序递归遍历  */ public void preOrderTraverse(); /**  * 中序递归遍历  */ public void inOrderTraverse(); /**  * 后序递归遍历  */ public void postOrderTraverse(); /**  * 按照层次遍历(借助队列)  */ public void levelOrderByStack(); /**  * 中序非递归遍历  */ public void inOrderByStack();}
二叉树接口类

实现二叉树接口类

创建树的根对象,并写出构造函数。

public class LinkedBinaryTree implements BinaryTree { private Node root; // 根结点  public LinkedBinaryTree() { } public LinkedBinaryTree(Node root) {  this.root = root; }
}

创建二叉树

 // 创建一个二叉树 Node nodeF = new Node("F",null,null); Node nodeE = new Node("E",null,null); Node nodeD = new Node("D",null,null); Node nodeC = new Node("C",nodeF,null); Node nodeB = new Node("B",nodeD,nodeE); Node nodeA = new Node("A",nodeB,nodeC); // 声明nodeA为根结点 BinaryTree btree = new LinkedBinaryTree(nodeA);  

判断二叉树是否为空

为空返回true,不为空返回false

public boolean isEmpty() { return root == null;}

输出二叉树结点数量

运用递归的思想,二叉树结点树 = 左子树结点数量右子树结点数量1

  public int size() {  System.out.println("二叉树结点数量: ");  return this.size(root); } private int size(Node root) {  if(root == null) {return 0;  } else {// 获取左子树的数量int nl = this.size(root.leftChild);// 获取右子树的数量int nr = this.size(root.rightChild);// 返回左子树、右子树size之和并加1return nlnr1;  } }

二叉树的深度(高度)

如果二叉树为空,则其深度为0。

如果二叉树只有根结点,无左右子树,则其深度为1。

如果二叉树结点数大于1,则用递归的思想计算其深度。二叉树的深度 = 左右子树的最大深度1。

 public int getHeight() {  System.out.println("二叉树的高度是 :");  return this.getHeight(root); } private int getHeight(Node root) {  if(root == null) {return 0;  } else {// 获取左子树的高度int nl = this.getHeight(root.leftChild);// 获取右子树的高度int nr = this.getHeight(root.rightChild);// 返回左子树、右子树较大高度并加1return nl > nr ? nl1 : nr1;  } }

在二叉树中查找某个值

运用递归的思想,将要查找的值逐个与根结点,根结点的左子树和右子树的值进行比较,并进行返回。

 public Node findKey(Object value) {  return this.findKey(value,root); } private Node findKey(Object value,Node root) {  <
源文地址:http://www.guoxiongfei.cn/cntech/12287.html