/*
树：分治和递归的艺术 
使用链式存储，逻辑相邻，物理不一定相邻，
通过指针记录“下家”在哪里。 
*/
#include <bits/stdc++.h> 
using namespace std;

// 1.定义二叉树节点的结构
typedef struct TreeNode{
    char v;
    struct TreeNode *left;
    struct TreeNode *right;
} Node; 

// 辅助函数：创建一个新节点 
Node* createNode(char v) {
    Node* node = new Node;
    node->v = v;
    node->left = NULL;
    node->right = NULL;
    return node; 
}

// 2.前序遍历函数的 - 递归实现
void preOrder(Node* root) {
    // 递归的终止条件
    if(root == NULL) return;

    // 1. 访问根节点，在这一步进行打印 
    cout << root->v << " ";
    // 2. 遍历左子树
    preOrder(root->left);
    // 3. 遍历右子树
    preOrder(root->right);
}

int main(){
    // 根节点 
    Node* root = createNode('A');
    // 第二层 
    root->left = createNode('B');
    root->right = createNode('C');
    // 第三层 B的子节点
    root->left->left = createNode('D');
    root->left->right = createNode('E');
    // 第三层 C的子节点 
    root->right->left = createNode('F');
    root->right->right = createNode('G');

    cout << "二叉树的前序遍历结果："  <<  endl;
    preOrder(root);
    cout << endl;


    return 0;
}