JAVA应用程序开发之二叉树

【本文详细介绍了JAVA应用开发中的二叉树,欢迎读者朋友们阅读、转发和收藏!】

1 基本概念

1.1 二叉树的定义

二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。

二叉树 (BinaryTree) 是 n(n ≥ 0) 个结点的有限集,它或者是空集 (n=0) ,或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

这个定义是递归的。由于左、右子树也是二叉树, 因此子树也可为空树。下图中展现了五种不同基本形态的二叉树。

其中 (a) 为空树, (b) 为仅有一个结点的二叉树, (c) 是仅有左子树而右子树为空的二叉树, (d) 是仅有右子树而左子树为空的二叉树, (e) 是左、右子树均非空的二叉树。这里应特别注意的是,二叉树的左子树和右子树是严格区分并且不能随意颠倒的,图 (c) 与图 (d) 就是两棵不同的二叉树。

1.2 二叉树的遍历

对于二叉树来讲最主要、最基本的运算是遍历。

遍历二叉树 是指以一定的次序访问二叉树中的每个结点。所谓 访问结点 是指对结点进行各种操作的简称。例如,查询结点数据域的内容,或输出它的值,或找出结点位置,或是执行对结点的其他操作。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。假设遍历二叉树时访问结点的操作就是输出结点数据域的值,那么遍历的结果得到一个线性序列。

1.3 二叉树有 3 种遍历方式 :

1, 前序遍历 :

首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树

2, 中序遍历 :

首先中序遍历左(右)子树,再访问根,最后中序遍历右(左)子树

3, 后序遍历 :

首先后序遍历左(右)子树,再后序遍历右(左)子树,最后访问根

2 二叉树的 java 实现

首先创建一棵二叉树如下图,然后对这棵叉树进行遍历操作(遍历操作的实现分为递归实现和非递归实现),同时还提供一些方法如获取双亲结点、获取左孩子、右孩子等。

import java.util.Stack;

/**

* 二叉树的链式存储

*/

public class BinaryTree {

private TreeNode root=null;

public BinaryTree(){

root=new TreeNode(1,"rootNode(A)");

}

/**

* 创建一棵二叉树

*

* A

* B C

* D E F

*

* @param root

* @author WWX

*/

public void createBinTree(TreeNode root){

TreeNode newNodeB = new TreeNode(2,"B");

TreeNode newNodeC = new TreeNode(3,"C");

TreeNode newNodeD = new TreeNode(4,"D");

TreeNode newNodeE = new TreeNode(5,"E");

TreeNode newNodeF = new TreeNode(6,"F");

root.leftChild=newNodeB;

root.rightChild=newNodeC;

root.leftChild.leftChild=newNodeD;

root.leftChild.rightChild=newNodeE;

root.rightChild.rightChild=newNodeF;

}

public boolean isEmpty(){

return root==null;

}

// 树的高度

public int height(){

return height(root);

}

// 节点个数

public int size(){

return size(root);

}

private int height(TreeNode subTree){

if(subTree==null)

return 0;// 递归结束:空树高度为 0

else{

int i=height(subTree.leftChild);

int j=height(subTree.rightChild);

return (i

}

}

private int size(TreeNode subTree){

if(subTree==null){

return 0;

}else{

return 1+size(subTree.leftChild)+size(subTree.rightChild);

}

}

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20200511A0CILV00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券