在JAVA中实现的二叉树结构

在JAVA中实现的二叉树结构

*
　　* 讲解：
　　* 二个方法函数，一个寻找关键字--searchkey 另一个是插入一个结点：insertTree
　　* 另外这是一个完全的先序遍历二叉树的语法。先根结点，再左结点，如无再右结点，
　　* 如此递归至搜索完毕。
　　*
　　*/
　　       public class BinaryTreeTest {
　　private BinaryTree root = null;
　　public BinaryTreeTest() {
　　init();
　　}
　　/**
　　* 初始化给定数据的二叉树结构
　　*
　　*/
　　private void init() {
　　int data[] = { 12, 11, 34, 45, 67, 38, 56, 43, 22, 8 };
　　root = new BinaryTree(data[0]);
　　System.out.println("二叉树的中的数据结构：");
　　System.out.println("------------------------------------");
　　System.out.println(data[0] + "：root");
　　for (int i = 1; i < data.length; i++) {
　　System.out.print(data[i] + "：");
　　root.insertTree(root, data[i]);
　　}
　　System.out.println("------------------------------------");
　　}
　　public void serach(int key) {
　　if (searchkey(root, key)) {
　　System.out.println("找到了:" + key);
　　} else {
　　System.out.println("没有找到：" + key);
　　}
　　}
　　private boolean searchkey(BinaryTree root, int key) {
　　if (root == null) {
　　return false;
　　} else if (root.data == key) {
　　return true;
　　} else if (key >= root.data) {
　　return searchkey(root.rightpoiter, key);
　　}
　　return searchkey(root.leftpoiter, key);
　　}
　　class BinaryTree {
　　int data;
　　BinaryTree leftpoiter;
　　BinaryTree rightpoiter;
　　BinaryTree(int data) {
　　this.data = data;
　　leftpoiter = null;
　　rightpoiter = null;
　　}
　　private void insertTree(BinaryTree root, int data) {
　　if (data >= root.data) {
　　if (root.rightpoiter == null) {
　　System.out.println(" -> new rightpoiter");
　　root.rightpoiter = new BinaryTree(data);
　　} else {
　　System.out.print(" -> rightpoiter");
　　insertTree(root.rightpoiter, data);
　　}
　　} else {
　　if (root.leftpoiter == null) {
　　System.out.println(" -> new leftpoiter");
　　root.leftpoiter = new BinaryTree(data);
　　} else {
　　System.out.print(" -> leftpoiter");
　　insertTree(root.leftpoiter, data);
　　}
　　}
　　}
　　}
　　public static void main(String args[]) {
　　BinaryTreeTest b = new BinaryTreeTest();
　　int key = 8; //key：任意数值
　　b.serach(key); //到二叉树中查找
　　}
　　}
　　运行结果：
　　C:\java>java BinaryTreeTest
　　二叉树的中的数据结构：
　　------------------------------------
　　12：root
　　11： -> new leftpoiter
　　34： -> new rightpoiter
　　45： -> rightpoiter -> new rightpoiter
　　67： -> rightpoiter -> rightpoiter -> new rightpoiter
　　38： -> rightpoiter -> rightpoiter -> new leftpoiter
　　56： -> rightpoiter -> rightpoiter -> rightpoiter -> new leftpoiter
　　43： -> rightpoiter -> rightpoiter -> leftpoiter -> new rightpoiter
　　22： -> rightpoiter -> new leftpoiter
　　8： -> leftpoiter -> new leftpoiter
　　------------------------------------
　　找到了:8