数据结构Java8二叉树与树

this.left = left; this.right = right; }

public BinaryNode(T data) //构造元素为data的叶子结点 {

this(data, null, null); }

public String toString() //返回结点数据域的描述字符串 {

return this.data.toString(); }

public boolean isLeaf() //判断是否叶子结点 {

return this.left==null && this.right==null; } }

2) 构造二叉树

(1)new一个根结点;

(2)new这个结点的左右结点,并把它和父结点建立链接; (3)对左右结点重复(2)的步骤;

构造二叉树测试代码

public class Main { public static void main(String[] args) { BinaryTree bt = new BinaryTree(); bt.create(); System.out.println(bt.root.data+\ } }

class BinaryNode //二叉树的二叉链表结点类，T指定结点的元素类型 {

public T data; //数据域，存储数据元素 public BinaryNode left, right; //链域，分别指向左、右孩子结点 //构造结点，data指定元素，left、right分别指向左孩子和右孩子结点 public BinaryNode(T data, BinaryNode left, BinaryNode right) {

this.data = data; this.left = left; this.right = right; }

public BinaryNode(T data) //构造元素为data的叶子结点 {

this(data, null, null); }

public String toString() //返回结点数据域的描述字符串 {

return this.data.toString(); }

public boolean isLeaf() //判断是否叶子结点 {

return this.left==null && this.right==null; } }

class BinaryTree{

public BinaryNode root=null;

public BinaryTree() //构造空二叉树 { }

public void create()

{

root=new BinaryNode('A');//根结点，结点结构为二叉链表 root.left = new BinaryNode('B');//

root.right = new BinaryNode('C'); } }

设comlist表示一棵二叉树标明空子树”.”的数组存储完全二叉树序列，构造二叉链式的递归算法描述如下：

①comlist[0]一定是二叉树的根，创建根结点；comlist[1]一定是根的左孩子。

②若comlist[i]是空子树null，则当前子树为空，返回上一层结点；否则创建一个结点，该结点的左孩子结点元素是comlist[2*i+1]，但父母与孩子之间的链还未建立。

③返回到当前结点时，下一个元素comlist[2*i+2]是当前结点的右孩子结点；当一个结点的左右孩子链都已建立，则以当前结点为根的一棵子树就已建好，返回上一层结点。 ④重复执行②③，直到返回根结点，则二叉树建成，使root指向根结点。

图（a）中标明空子树的数组存储完全二叉树序列为ABCD.EF.G....H

构造二叉树测试代码

private BinaryNode create(T[] comlist, int i) { BinaryNode p = null; if (i < comlist.length) { if (comlist[i]!= null) //题目中”.”转换为null { p = new BinaryNode(comlist[i]); // 创建一个结点，左孩子右孩子暂为空 p.left = create(comlist, 2 * i + 1); // 创建p的左子树，递归调用，实际参数与形式参数相同 p.right = create(comlist, 2 * i + 2);// 创建p的右子树，递归调用，实际参数与形式参数相同 } } return p; //返回 }

public BinaryTree(T[] comlist) //构造方法创建二叉树，并初始化二叉树的成员root { this.root = create(comlist, 0); }

6.二叉链表存储的二叉树递归遍历和非递归遍历

“遍历”是二叉树各种操作的基础。二叉树是一种非线性结构，其遍历不像线性链表那样容易，无法通过简单的循环实现。

二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。

二叉树遍历通常借用“栈”这种数据结构实现，有两种方式：递归方式及非递归方式。 在递归方式中，栈是由操作系统维护的，用户不必关心栈的细节操作，用户只需关心“访问顺序”即可。因而，采用递归方式实现二叉树的遍历比较容易理解，算法简单，容易实现。

1) 先序遍历递归算法

public void preorder() // 输出先根次序遍历序列

{ System.out.print(\先根次序遍历二叉树： \ preorder(this.root); // 调用先根次序遍历二叉树的递归方法 System.out.println(); }

private void preorder(BinaryNode p) // 先根次序遍历以p结点为根的子树，递归方法 { if (p != null) // 若二叉树不空 { System.out.print(p.data.toString()); // 先访问当前结点元素 preorder(p.left); // 按先根次序遍历p的左子树，递归调用，参数为左孩子 preorder(p.right); // 按先根次序遍历p的右子树，递归调用，参数为右孩子 } }

2) 中序遍历递归算法

public void inorder() //输出中根次序遍历序列 {

System.out.print(\中根次序遍历二叉树： \ inorder(this.root); System.out.println(); }

private void inorder(BinaryNode p) //中根次序遍历以p结点为根的子树，递归方法 {

if (p!=null) {

inorder(p.left); //中根次序遍历p的左子树，递归调用 if(p.isleaf())

System.out.print(p.data.toString()+\

inorder(p.right); //中根次序遍历p的右子树，递归调用 } }

3) 后序遍历递归算法

public void postorder() //输出后根次序遍历序列 {

// System.out.print(\后根次序遍历二叉树： \ postorder(this.root); System.out.println(); }

private void postorder(BinaryNode p) //后根次序遍历以p结点为根的子树，递归方法{ if (p!=null)