Java实现查找二叉树&C++的做法

写了个Java的查找二叉树，用递归做的，不用递归的还没弄出来。先贴一下。回头再研究。

BTreeTest.java:

public class BTreeTest{
    class Node{
        Node left, right;
        int data;
        
        Node(int newData){
            left = null;
            right = null;
            data = newData;
        }
    }
    Node root = null;
    int count = 0;
    boolean canFind = false;
    public void insert(int data){
        root = insert(root, data);
    }
    
    private Node insert(Node node, int data){
        if(node == null){
            node = new Node(data);
        }else if(data <= node.data){
            node.left = insert(node.left, data);
        }else{
            node.right = insert(node.right, data);
        }
        
        return node;
    }
    
    public void preOrder(){
        preOrder(root);
    }
    private void preOrder(Node node){
        if(node != null){
            System.out.print(node.data + ",");
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    
    public void inOrder(){
        inOrder(root);
    }
    private void inOrder(Node node){
        if(node != null){
            inOrder(node.left);
            System.out.print(node.data + ",");
            inOrder(node.right);
        }
    }
    
    public void postOrder(){
        postOrder(root);
    }
    private void postOrder(Node node){
        if(node != null){
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.data + ",");
        }
    }
    
    public boolean search(int data){
        search(data, root);
        return canFind;
    }
    
    private void search(int data, Node node)
    {
        if(node != null){
            if(data == node.data){
                canFind = true;
            }else if(data < node.data){
                count++;
                search(data, node.left);
                
            }else if(data > node.data){
                count++;
                search(data, node.right);            
            }
        }                    
    }
    
    public void showCount(){
        System.out.print("Count times: " + count);
    }
    
    public static void main(String[] args){
        BTreeTest tree = new BTreeTest();
        int a[] = {6,5,7,1,9,8,10};
        for(int i=0; i< 7; i++){
            //printf("%d", a[i]);
            System.out.println("Insert data=" + a[i]);
            tree.insert(a[i]);
        }
        System.out.print("先序
");
        tree.preOrder();
        System.out.print("
中序
");
        tree.inOrder();
        System.out.print("
后序
");
        tree.postOrder();
        
        int value = 4;
        if(tree.search(value)){
            System.out.println("Can find " + value);
        }else{
            System.out.println("Cannot find " + value);
        }
        tree.showCount();
    }
}/** out put: ******
Insert data=6
Insert data=5
Insert data=7
Insert data=1
Insert data=9
Insert data=8
Insert data=10
前序:
6,5,1,7,9,8,10,
中序
1,5,6,7,8,9,10,
后序
1,5,8,10,9,7,6,
层次
6,5,7,1,9,8,10,
14 is not in the tree,search for 4
*/

参考了C++实现的代码：http://www.cppblog.com/emptysoul/archive/2008/11/24/67747.html，其实以上的代码基本就是看了之后敲成Java代码...

转帖一下：

BTree.h:

#ifndef BTREE_H
#define BTREE_H
#include <iostream>
#include <queue>
using namespace std;

static int findcounts; //用于测试查找某节点的次数
template<class T>
class BTree
{
    //定义树节点，包括一个数据，两个指针
    struct BNode
    {
        BNode(T dat, BNode* l, BNode* r) : data(dat), left(l), right(r){};
        T data;
        BNode *left, *right;
    }* root;

    //插入一个节点，
    void Insert(const T& data, BNode*& p)
    {
        if(p == 0)
        {
            p = new BNode(data, 0, 0);
            std::cout << "Insert data=" << data << std::endl;
        }
        else if(data < p->data)
        {
            //插入数据小于父节点数据，插入左子树
            Insert(data, p->left);
        }
        else if(data > p->data)
        {
            //插入数据小于父节点数据，插入右子树
            Insert(data, p->right);
        }
    }

    //先序遍历
    void PreOrder (BNode* p)
    {
        if(p != 0)
        {
            Print(p);
            PreOrder (p->left);
            PreOrder (p->right);
        }
    }

    //中序遍历
    void InOrder (BNode* p)
    {
        if(p != 0)
        {
            InOrder (p->left);
            Print(p);
            InOrder (p->right);
        }
    }

    //后序遍历
    void PostOrder (BNode* p)
    {
        if(p != 0)
        {
            PostOrder (p->left);
            PostOrder (p->right);
            Print(p);
        }
    }

    //查找节点
    bool Find(const T& data, BNode* p)
    {
        if(p != 0)
        {
            if(data == p->data)
            {
                return true;
            }
            else if(data < p->data)
            {
                findcounts ++;
                Find(data, p->left);
            }
            else
            {
                findcounts ++;
                Find(data, p->right);
            }
        }
        else
        {
            return false;
        }
    }

    //删除整棵树
    void MakeEmpty(BNode* p)
    {
        if(p != 0)
        {
            MakeEmpty(p->left);
            MakeEmpty(p->right);
            std::cout << "del " << p->data << ",";
            delete p;
        }
    }
public:
    BTree() : root(0){}

    ~BTree()
    {
        MakeEmpty(root);
    }

    void Insert(const T& data)
    {
        Insert(data, root);
    }

    void PreOrder()
    {
        //递归，前序遍历
        PreOrder(root);
    }

    void InOrder()
    {
        //递归，中序遍历
        InOrder(root);
    }

    void PostOrder()
    {
        //递归，后序遍历
        PostOrder(root);
    }

    //层次遍历，使用队列的特性实现树的非递归遍历
    void LevelOrder ()
    {
        queue<BNode*> q;
        BNode* p = root;
        while(p)
        {
            Print(p);
            if(p->left != 0)
            {
                q.push(p->left);
            }
            if(p->right != 0)
            {
                q.push(p->right);
            }
            if (q.empty())
            {
                break;
            }
            p = q.front();
            q.pop();
        }
    }

    //打印一个节点值
    void Print(BNode* p)
    {
        if(p != 0)
        {
            std::cout << p->data << ",";
        }
    }

    //打印一个节点的查找次数
    void PrintStatic()
    {
        std::cout << findcounts;
    }

    //递归查找一个节点
    bool Find(const T& data)
    {
        findcounts = 0;
        return Find(data, root);
    }
};
#endif

Test.cpp:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <stdio.h>
#include "BTree.h"

using namespace std;

int main(int argc, char *argv[])
{
    //随机生成一棵树
    BTree<int> tree;
    srand((unsigned)time(NULL));
    //for(int i=0; i<20; ++i)
//    {
//        int var = rand() / 20;
//        printf("%d", var);
//        tree.Insert(var);
//    }
    int a[7] = {6,5,7,1,9,8,10};
    for(int i=0; i< 7; i++){
        //printf("%d", a[i]);
        tree.Insert(a[i]);
    }

    cout << "前序:" << endl;
    tree.PreOrder();
    cout << endl;
    cout << "中序" << endl;
    tree.InOrder();
    cout << endl;
    cout << "后序" << endl;
    tree.PostOrder();
    cout << endl;
    cout << "层次" << endl;
    tree.LevelOrder();
    cout << endl;

    if(tree.Find(6))
    {
        cout << "6 is in the tree,search for " ;
        tree.PrintStatic();
        cout << endl;
    }
    else
    {
        cout << "14 is not in the tree,search for " ;
        tree.PrintStatic();
        cout << endl;
    }
system("PAUSE");
    //return 0;
}
/** out put: ******
Insert data=6
Insert data=5
Insert data=7
Insert data=1
Insert data=9
Insert data=8
Insert data=10
前序:
6,5,1,7,9,8,10,
中序
1,5,6,7,8,9,10,
后序
1,5,8,10,9,7,6,
层次
6,5,7,1,9,8,10,
14 is not in the tree,search for 4
*/