快捷搜索:  汽车  科技

java多叉树创建及遍历完整代码(Java数据结构什么是树)

java多叉树创建及遍历完整代码(Java数据结构什么是树)/* BitTree.java */ package com.java.tree; import java.util.LinkedList; import java.util.Queue; /** * Created by Jaco.Young. * 2018-06-13 18:26 */ public class BitTree { //代表由先序和中序唯一确定的树的根结点 private TreeNode root; /** * 提供给外部调用的方法 * 字符数组pre表示先序遍历序列,mid表示中序遍历序列 */ public void build(char[] pre char[] mid){ //将创建树的根结点赋值给 root root = buildTree(pre

目录:

一、树
1. 概述
2. 一些基本术语
二、二叉树
1. 概述
2. 重要特性
三、二叉树的存储结构
1. 顺序存储
2. 链式存储
四、二叉树的遍历
1. 由遍历序列确定二叉树
2. 根据遍历序列估计二叉树
3. 遍历和建树代码


一、树1. 概述
  • 与线性表表示的一一对应的线性关系不同,树表示的是更为复杂的数据元素之间的非线性关系
  • 直观来看,树是以分支关系定义的层次结构,是 一对多 的关系
  • 树的定义:树 (Tree) 是 n( n>=0 ) 个结点的有限集合
  • 有且仅有一个 根结点 (Root)
  • 当n>1的时,其余结点可分为 m( m>0 ) 个互不相交的有限集T1,T2,... Tm,其中每一个集合本身又是一棵树,并且称之为根的子树

树的定义本身是一个递归定义,即在树的定义中又用到树的概念

2. 一些基本术语
  • 树的结点:包含一个数据元素和若干指向其子树的分支
  • (degree):结点拥有的子树的数目
  • 度为** 0 的结点称为 叶子,或 终端结点。度不为 0** 的结点称为 非终端结点分支节点
  • 结点的子树的根,称为该结点的 孩子(child),相应的该结点称为孩子的 双亲(parent)
  • 同一个双亲的孩子之间互称兄弟(sibling)
  • 结点的 祖先 是从根到该结点所经分支上所有的结点。
  • 以某结点为根的子树中的任意一结点都称为该结点的 子孙
  • 结点的 层次(Level)从根开始定义,根为第一层,根的孩子为第二层,以此类推
  • 树中结点的最大层次称为树的 深度(depth)或 高度

二、二叉树1. 概述
  • 定义:对一般的树加了约束:
  • 每个结点最多两棵子树,即二叉树中不存在 度大于2 的结点
  • 子树有 左右次序 之分
  • 有 5 种形态

java多叉树创建及遍历完整代码(Java数据结构什么是树)(1)

  • 满二叉树完全二叉树(对满二叉树最底层,从右至左删除结点)
2. 重要特性
  • 二叉树,在第 i 层至多有 2i-1 个结点
  • 深度为 k 的二叉树至多有 2k-1 个结点
  • 高度(或深度)为 K完全二叉树至少有 2k-2叶子结点
  • 非空二叉树的 叶子结点数 等于度为 2 的结点数加 1,即:n0 = n2 1

完全二叉树的 n1 只能是 0 或者 1

  • 一颗度为 m 的二叉树,度为 1 的结点为 n1,度为 2 的结点为 n2,... ...,度为 m 的结点数为 nm,则叶子结点数:n0****= 1 n2**** 2n3**** ... (m-1)nm
  • 具有 n 个结点的完全二叉树,深度为 log2n 1
  • 编号性质:n 个结点的完全二叉树(其深度为 log2n 1),对各结点从上到下,从左到右依次编号(1~n)则:若 i 是某结点 a 的编号:
  • 如果 i 不等于 1,则 a 的双亲结点的编号为: ⌊ i/2 ⌋
  • 如果 2i ≤ n 则 a 的左孩子编号为 2i;如果** 2i > n 则 a 无左孩子**;
  • 如果** 2i 1 ≤ n 则 a 的右孩子编号为 2i 1;如果 2i 1> n 则 a 无右孩子**;

三、二叉树的存储结构1. 顺序存储
  • 数组 来存储数据元素
  • 从存储的角度来看,这种顺序存储结构,仅适用于 完全二叉树

因为在最坏的情况下,一个深度为 k 且只有 k 个结点的单支树( 树中不存在度为 2 的结点 ),却需要长度为 2k-1 的一维数组。

2. 链式存储
  • 链表 的形式,存储数据元素以及数据元素之间的关系。

java多叉树创建及遍历完整代码(Java数据结构什么是树)(2)


四、二叉树的遍历1. 由遍历序列确定二叉树
  • 先序和中序,可以确定
  • 后序和中序,可以确定(但是注意后序最后一个为根下一个是右子树根
  • 层次和中序,可以确定
2. 根据遍历序列估计二叉树
  • 前序 遍历序列 和 后序 遍历序列 相同 的树:只有根结点
  • 前序 遍历 和 中序 遍历 相同 的二叉树:所有结点没有左子树(右单分支树
  • 中序 遍历 和 后序 遍历 相同 的二叉树:所有结点没有右子树(左单分支树)
  • 前序遍历 和 后序 遍历 相反 的二叉树:没有左子树或者没有右子树(只有一个叶子结点<u style="text-decoration: none; border-bottom: 1px dashed grey;">高度等于其结点数</u>
  • 前序 遍历 和 中序 遍历 相反 的二叉树:所有结点没有右子树(左单分支树)
  • 中序 遍历 和 后序 遍历 相反 的二叉树:所有结点没有左子树(右单分支树)
3. 遍历和建树代码
  • 二叉树的建树
  • 深度优先遍历(先序,中序和后序)
  • 广度优先遍历(先序,后序)

/* BitTree.java */ package com.java.tree; import java.util.LinkedList; import java.util.Queue; /** * Created by Jaco.Young. * 2018-06-13 18:26 */ public class BitTree { //代表由先序和中序唯一确定的树的根结点 private TreeNode root; /** * 提供给外部调用的方法 * 字符数组pre表示先序遍历序列,mid表示中序遍历序列 */ public void build(char[] pre char[] mid){ //将创建树的根结点赋值给 root root = buildTree(pre 0 pre.length-1 mid 0 mid.length-1); } /** * 前提条件,树中不存在重复元素 * 由先序遍历序列和中序遍历序列,构造二叉树的方法 * 我们建树的过程总是将序列不断地分割成左子树、右子树 * lPre、rPre和lMid、rMid,分别就表示要对先序和中序的哪一部分进行建树 */ private TreeNode buildTree(char[] pre int lPre int rPre char[] mid int lMid int rMid){ //在先序遍历序列中,找到当前这棵树的根结点 char root = pre[lPre]; //在中序遍历序列中,根据先序中的根结点来查找在中序中的位置 int rootIndex = getRootIndex(mid lMid rMid root); //如果没有找到,说明所给的参数异常 if(rootIndex == -1){ throw new IllegalArgumentException("Illegal Argument!"); } //计算当前这棵树,左右子树的个数 //整个中序序列:[左子树(lMid) root(rootIndex) 右子树(rMid)] //左子树[lMid rootIndex-1] int lNum = rootIndex - lMid; //rootIndex-1 -lMid 1 //右子树[rootIndex 1 rMid] int rNum = rMid - rootIndex; //rMid - (rootIndex 1) 1 //开始构建当前根结点的左子树和右子树 //先构建左子树 TreeNode lchild; //作为左子树的根结点 //以当前结点为根的树,没有左子树 if(lNum == 0){ lchild = null; }else{ //当前这个树的左子树,仍然是一棵树,递归构造这棵树的左子树 //设x为当前树先序中左子树最后一个元素的下标,则:x - (lpre 1) = lNum //得:x = lPre lNum lchild = buildTree(pre lPre 1 lPre lNum mid lMid rootIndex - 1); } //构建右子树 TreeNode rchild; if(rNum == 0){ rchild = null; }else{ //当前结点的右子树,仍然包含很多节点,需要递归的构造其右子树 rchild = buildTree(pre lPre lNum 1 rPre mid rootIndex 1 rMid); } //构造完整的二叉树 return new TreeNode(root lchild rchild); } //在中序遍历序列中,根据先序中的根结点来查找在中序中的位置 private int getRootIndex(char[] mid int lMid int rMid char root) { for(int i = lMid; i <= rMid; i ){ if(mid[i] == root){ return i; } } return -1; } //二叉树每一个结点的结构 private class TreeNode{ //结点中存储的数据 char item; //指向左孩子结点 TreeNode lChild; //指向右孩子结点 TreeNode rChild; //构造方法 完成初始化 public TreeNode(char item TreeNode lChild TreeNode rChild){ this.item = item; this.lChild = lChild; this.rChild = rChild; } } //提供三个让外界调用的方法 public void preTraverse() { preOrder(root); } public void midTraverse() { midOrder(root); } public void postTraverse() { postOrder(root); } //先序遍历 DLR private void preOrder(TreeNode root) { if( root != null) { //先访问根节点 System.out.print(root.item " "); //递归访问左子树 preOrder(root.lChild); //递归访问右子树 preOrder(root.rChild); } } //中序遍历 LDR private void midOrder(TreeNode root) { if(root != null) { //递归访问左子树 midOrder(root.lChild); //访问根 System.out.print(root.item " "); //递归访问右子树 midOrder(root.rChild); } } //后续遍历 // LRD private void postOrder(TreeNode root) { if(root != null) { //递归访问左子树 postOrder(root.lChild); //递归访问右子树 postOrder(root.rChild); //访问根 System.out.print(root.item " "); } } //广度优先遍历 BFS public void BFS() { //创建一个能放TreeNode对象的队列 Queue<TreeNode> queue = new LinkedList<>(); //将树的根节点入队列 queue.add(root); //循环执行广度优先遍历 while(!queue.isEmpty()) { //将当前的队头元素出队列 TreeNode node = queue.remove(); //访问出队列的节点 System.out.print(node.item " "); //出队列的节点是否有左孩子,有则将其左孩子入队列 if(node.lChild != null) { //有左孩子 queue.add(node.lChild); } //出队列的节点是否有右孩子,如果右,将其右孩子如队列 if(node.rChild != null) { queue.add(node.rChild); } } } }

/* Test.java*/ package com.java.tree; /** * 测试类 * Created by Jaco.Young. * 2018-06-13 20:16 */ public class Test { public static void main(String[] args){ //构造先序遍历序列和中序遍历序列 char[] pre = {'A' 'B' 'E' 'K' 'L' 'F' 'D' 'H' 'J'}; char[] mid = {'K' 'E' 'L' 'B' 'F' 'A' 'H' 'D' 'J'}; BitTree bitTree = new BitTree(); //根据遍历序列构建二叉树 bitTree.build(pre mid); //先序遍历 bitTree.preTraverse(); System.out.println(); //中序遍历 bitTree.midTraverse(); System.out.println(); //后序遍历 bitTree.postTraverse(); System.out.println(); //广度优先遍历 bitTree.BFS(); } }

运行结果为:
A B E K L F D H J
K E L B F A H D J
K L E F B H J D A
A B D E F H J K L

java多叉树创建及遍历完整代码(Java数据结构什么是树)(3)

猜您喜欢: