数据结构与算法“play with tree”

Question

Given a binary tree, your task is to get the height and size(number of nodes) of the tree.
The Node is defined as follows.

struct Node {
Node *lc, *rc;
char data;
};

Implement the following function.

void query(const Node *root, int &size, int &height)
{
// put your code here
}

提示

In this problem, we assume that the height of the tree with only one node is 1.

求完整代码

Answer 1

#include<iostream>
using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))

struct Node {
    struct Node* lc, * rc;
    char data;
};

void query(const Node* root, int& size, int& height) {
    if (root == NULL) return;
    int leftHeight = 0, rightHeight = 0;
    query(root->lc, size, leftHeight);
    query(root->rc, size, rightHeight);
    size += 1;
    height = 1 + max(leftHeight, rightHeight);
}

int main() {
    //测试案例:
    //            root 
    //        lc            rc
    Node* root = (Node*)malloc(sizeof(Node));
    if (root != NULL) {
        root->rc = (Node*)malloc(sizeof(Node));
        if (root->rc != NULL) {
            root->rc->lc = root->rc->rc = NULL;
        }

        root->lc = (Node*)malloc(sizeof(Node));
        if (root->lc != NULL) {
            root->lc->lc = root->lc->rc = NULL;
        }
    }
    int size = 0, height = 0;
    query(root, size, height);
    cout << size << "\t" << height << endl;
}