二叉树结构

二叉树可以用顺序存储或链式存储两种结构，顺序存储需要借助一维数组，然后通过内存之间位置找到相应元素，访问速度和内存将会大大提升。顺序存储结构只适用于完全二叉树，一般二叉树不宜用顺序表示。下面将着重讲解二叉树的链式存储结构。

链式存储结构提供了二叉树在计算机内的一种表示方法，称为二叉链表。

// An highlighted block
//节点结构体
typedef struct btnode
{
    char element;
    struct btnode *lChild;
    struct btnode *rChild;
}BTNode;
//二叉树结构体
typedef struct binarytree
{
    BTNode *root;
}BinaryTree;

二叉树基本运算

1. void Create(BinaryTree *bt)；构造一棵空二叉树bt
2. BTNode *NewNode(char x, BTNode *ln, BTNode *rn)；创建一个新节点
3. bool Root(BinaryTree *bt, char *x)；判断二叉树是否为空，非空通过指针x返回根节点的值
4. void MakeTree(BinaryTree *bt, char e, BinaryTree *left, BinaryTree *right)；构造二叉树，根节点的值为e，left和right为左右子树

代码

// An highlighted block
#include<iostream>
using namespace std;
typedef struct btnode
{
    char element;
    struct btnode *lChild;
    struct btnode *rChild;
}BTNode;
typedef struct binarytree
{
    BTNode *root;
}BinaryTree;
//构造一棵空二叉树
void Create(BinaryTree *bt) {
    bt->root = NULL;
}
//创建一个新节点
BTNode *NewNode(char x, BTNode *ln, BTNode *rn) {
    BTNode *p = (BTNode *) malloc (sizeof(BTNode));
    p->element = x;
    p->lChild = ln;
    p->rChild = rn;
    return p;
}
//判断二叉树是否为空，非空通过指针x返回根节点的值
bool Root(BinaryTree *bt, char *x) {
    if(bt->root) {
        x = &bt->root->element;
        return true;
    } else {
        return false;
    }
}
//构造二叉树，根节点的值为e，left和right为左右子树
void MakeTree(BinaryTree *bt, char e, BinaryTree *left, BinaryTree *right) {
    if(bt->root || left == right) {
        return ;
    }
    bt->root = NewNode(e, left->root, right->root);
    left->root = NULL;
    right->root = NULL;
}
//
void PreOrder(BTNode *t) {
    if(!t) return;
    printf(\"\\t%c\\t\\n\", t->element);
    PreOrder(t->lChild);
    PreOrder(t->rChild);
}
//先序遍历二叉树
void PreOrderTree(BinaryTree *bt) {
    PreOrder(bt->root);
}
void Clear(BTNode *t) {
    if(!t) return;
    Clear(t->lChild);
    Clear(t->rChild);
    free(t);
}
void TreeClear(BinaryTree *bt) {
    Clear(bt->root);
}

int main() {
    BinaryTree a, b, x, y, z;
    //阶段I
    //构造5个空节点  
    Create(&a);
    Create(&b);
    Create(&x);
    Create(&y);
    Create(&z);
    //将节点连接为二叉树，注意节点a和b始终为空节点
    MakeTree(&y, \'E\', &a, &b);	//阶段II
    MakeTree(&z, \'F\', &a, &b);
    MakeTree(&x, \'C\', &y, &z);	//阶段III
    MakeTree(&y, \'D\', &a, &b);	//阶段IV
    MakeTree(&z, \'B\', &y, &x);	//阶段V
    printf(\"PreOrderTree: \\n\");
    PreOrderTree(&z);			//先序遍历打印二叉树
    TreeClear(&z);
    system(\"pause\");
    return 0;
}

图例（main函数执行过程如下：）

阶段I

阶段II

阶段III

阶段IV

阶段V

先序遍历输出过程