二叉树链式结构实现与遍历详解

二叉树链式结构实现与遍历

概述

在了解二叉树顺序结构（堆）的基础上，本节重点学习二叉树的链式结构实现。

链式结构实现

用链表来表示一棵二叉树，即用链表来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结构如下：

typedef int BTDataType;
// 二叉链
typedef struct BinaryTreeNode {
    struct BinaryTreeNode* left;   // 指向当前结点左孩子
    struct BinaryTreeNode* right;  // 指向当前结点右孩子
    BTDataType data;               // 当前结点值域
} BTNode;

今天先不来了解怎么创建二叉树，因为这个相对而言比较麻烦，等学完了二叉树的遍历，我们再来深究二叉树的创建。所以这里我们先手动创建一颗链式二叉树。

BTNode* BuyBTNode(int val) {
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if(newnode == NULL) {
        perror("malloc fail");
        return NULL;
    }
    newnode->data = val;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

BTNode* CreateTree() {
    BTNode* n1 = BuyBTNode(1);
    BTNode* n2 = BuyBTNode(2);
    BTNode* n3 = BuyBTNode(3);
    BTNode* n4 = BuyBTNode();
    BTNode* n5 = ();
    BTNode* n6 = ();
    
    n1->left = n2;
    n1->right = n4;
    n2->left = n3;
    n4->left = n5;
    n4->right = n6;
     n1;
}