Java中二叉树数据结构的实现示例

时间:2021-05-20

来看一个具体的习题实践:

题目
根据二叉树前序遍历序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,构建二叉树,并且用前序、中序、后序进行遍历

代码

import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 静态内部类,定义二叉树节点 */ static class TreeNode { public String data; TreeNode lchild; TreeNode rchild; public TreeNode(String x) { this.data = x; } } /** * 根据前序序列递归构建二叉树 * * @return */ public static TreeNode createBtree() { TreeNode root = null; if (count >= str.length || str[count++].equals("#")) { root = null; } else { root = new TreeNode(str[count - 1]); root.lchild = createBtree(); root.rchild = createBtree(); } return root; } /** * 前序遍历 * * @param root */ public static void preTraverse(TreeNode root) { if (root != null) { System.out.print(root.data + " "); preTraverse(root.lchild); preTraverse(root.rchild); } } /** * 中序遍历 * * @param root */ public static void inTraverse(TreeNode root) { if (root != null) { inTraverse(root.lchild); System.out.print(root.data + " "); inTraverse(root.rchild); } } /** * 后序遍历 * * @param root */ public static void postTraverse(TreeNode root) { if (root != null) { postTraverse(root.lchild); postTraverse(root.rchild); System.out.print(root.data + " "); } } public static void main(String args[]) { Scanner cin = new Scanner(System.in); while (cin.hasNext()) { String s = cin.nextLine(); str = s.split(","); count = 0; TreeNode root = createBtree(); // 前序遍历 preTraverse(root); System.out.println(); // 中序遍历 inTraverse(root); System.out.println(); // 后序遍历 postTraverse(root); System.out.println(); } } }

二叉树的深度

下面是是实现二叉树的递归算法的实现,其思想就是,若为空,则其深度为0,否则,其深度等于左子树和右子树的深度的最大值加1:

class Node{ String name; Node left; Node right; public Node(String name) { this.name = name; } @Override public String toString() { return name; }}//定义二叉树class BinaryTree{ Node root; public BinaryTree(){ root = null; } //为了方便起见,我就直接写个初始化的二叉树,详细的可以见以前的日志 public void initTree(){ Node node1 = new Node("a"); Node node2 = new Node("b"); Node node3 = new Node("c"); Node node4 = new Node("d"); Node node5 = new Node("e"); root = node1; node1.left = node2; node2.right = node3; node1.right = node4; node3.left = node5; } //求二叉树的深度 int length(Node root){ int depth1; int depth2; if(root == null) return 0; //左子树的深度 depth1 = length(root.right); //右子树的深度 depth2 = length(root.left); if(depth1>depth2) return depth1+1; else return depth2+1; }}public class TestMatch{ public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.initTree(); System.out.println(tree.length(tree.root)); }}

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章