CareerCup_4.3@1point3acres

main.cpp

//
//  main.cpp
//  cc4_3
//
//  Created by gsw on 12-5-9.
//  Copyright (c) 2012年 __MyCompanyName__. All rights reserved.
//

/******************************************************************************
 * Given a sorted (increasing order) array, write an algorithm to create a 
 * binary tree with minimal height
 ******************************************************************************/

// 没有实现计算层数
// 如果要记录层数，需要手工操作队列

#include <iostream>
#include <queue>

template <class T>
struct Node {
    T data;
    Node *lchild;
    Node *rchild;
    Node(T &a): data(a), lchild(NULL), rchild(NULL) {}
};

template <class T>
class Tree {
 public:
    Tree(): root(NULL), height(0) {}
    ~Tree();
    void buildtree(T a[], int n);
    
 private:
    Node<T> *root;
    int height;
    void cleartree(Node<T> *node);
};

template <class T>
void Tree<T>::buildtree(T a[], int n) {
    if (n < 1) {
        return;
    }
    std::queue<Node<T> *> q;
    if (root == NULL) {
        root = new Node<T>(a[0]);
        q.push(root);
    } else {
        Node<T> *temp;
        int i = 1;
        while (true) {
            if (i < n) {
                temp = q.front();
                q.pop();
                temp->lchild = new Node<T>(a[i++]);
                q.push(temp->lchild);
            } else {
                break;
            }
            if (i < n) {
                temp->rchild = new Node<T>(a[i++]);
                q.push(temp->rchild);
            } else {
                break;
            }
        }
    }
}

template <class T>
Tree<T>::~Tree<T>() {
    cleartree(root);
}

template <class T>
void Tree<T>::cleartree(Node<T> *node) {
    if(node != NULL) {
        cleartree(node->lchild);
        cleartree(node->rchild);
        delete node;
    }
}

int main(int argc, char *argv[]) {
    int a[7] = {1, 2, 3, 4, 5, 6, 7};
    Tree<int> tree;
    tree.buildtree(a, 7);
    return 0;
}