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

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

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

题目

根据二叉树前序遍历序列例如：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));

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。