C++数据结构-二叉树的存储方法（基础篇）

1. 简介

根据前文的介绍，我们知道了二叉树的性值，其就是一种每一个结点中只允许拥有左右孩子（或为空）的树，这种数据结构在我们的实际设计中非常常用，如前文提到的STL中的set集合，其底层就是一颗标准的红黑树（二叉树的一种），我们这里以创建一颗二叉树并实现通过特定的插入顺序和读取顺序达成读取为顺序为例子进行简介。

2. 结点设计

一颗二叉树的结点设计一定要有如下内容：

a)结点元素，data域，用来存储数据，其可以是int，char等基本的类型，同时也可以是struct等这些复杂的复合数据类型。

b)左孩子结点，left指针，总是用来指向当前结点的下一层的左边结点，其属于一种指针。

c)右孩子结点，right指针，总是用来指向当前结点的下一层的右边结点，其属于一种指针。

d)父结点（可选），parent指针，总是指向当前结点的前一个结点，简称父亲结点，其不属于必须结点设计，省略掉可以打扰节省内存的效果，而使用则可以更方便进行定向搜索，本案例中不使用父节点。

以上就是一颗二叉树的结点设计，除此之外，我们使用一棵树的时候需要建立一颗树根，由这个“根”，来进行逐步的向下构建。

其设计代码可以表示为：

//树的结点
typedef struct node{
    int data;
    struct node* left;
    struct node* right;
} Node;
  
//树根
typedef struct {
    Node* root;
} Tree;

3.树的创建

如同当时学习链表的创建，首先，我们创建一个空的结点再进行连接，首先将这个空的结点中的date域赋予数据，再判断tree中是否是一个空树，如果为空，只需要将整个根指向这一个结点即可，如果不为空，再进行两个判断，判断输入的数据是否大于或者小于当前比对的结点数据，根据其大小进行相应的排列，这样存储进入的数据总是有一定规律的，在输出的时候根据这个规律进行输出就可以达到想要的效果。

其代码可以显示为：

//创建树--插入数据
void insert(Tree* tree, int value){
    //创建一个节点，让左右指针全部指向空，数据为value
    Node* node=(Node*)malloc(sizeof(Node));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
  
    //判断树是不是空树，如果是，直接让树根指向这一个结点即可
    if (tree->root == NULL){
        tree->root = node;
    } else {//不是空树
        Node* temp = tree->root;//从树根开始
        while (temp != NULL){
            if (value < temp->data){ //小于就进左儿子
                if (temp->left == NULL){
                    temp->left = node;
                    return;
                } else {//继续往下搜寻
                    temp = temp->left;
                }
            } else { //否则进右儿子
                if (temp->right == NULL){
                    temp->right = node;
                    return;
                }
                else {//继续往下搜寻
                    temp = temp->right;
                }
            }
        }
    }
    return;
}

4. 遍历，显示树（要用到递归）

具体的内容将会在后文面的文章细讲，先直接提供一份代码做参考：

//树的中序遍历 In-order traversal
void inorder(Node* node){
    if (node != NULL)
    {
        inorder(node->left);//递归函数，自己调用自己，必须有一个判断方式来结束递归
        printf("%d ",node->data);
        inorder(node->right);
    }
}
//递归在栈段里

5.二叉树的基本创建代码

#include <cstdlib>
#include <stdio.h>
#include <iostream>
  
using namespace std;
  
//树的结点
typedef struct node{
    int data;
    struct node* left;
    struct node* right;
} Node;
  
//树根
typedef struct {
    Node* root;
} Tree;
  
//创建树--插入数据
void insert(Tree* tree, int value){
    //创建一个节点，让左右指针全部指向空，数据为value
    Node* node=(Node*)malloc(sizeof(Node));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
  
    //判断树是不是空树，如果是，直接让树根指向这一个结点即可
    if (tree->root == NULL){
        tree->root = node;
    } else {//不是空树
        Node* temp = tree->root;//从树根开始
        while (temp != NULL){
            if (value < temp->data){ //小于就进左儿子
                if (temp->left == NULL){
                    temp->left = node;
                    return;
                } else {//继续往下搜寻
                    temp = temp->left;
                }
            } else { //否则进右儿子
                if (temp->right == NULL){
                    temp->right = node;
                    return;
                }
                else {//继续往下搜寻
                    temp = temp->right;
                }
            }
        }
    }
    return;
}
  
//树的中序遍历 In-order traversal
void inorder(Node* node){
    if (node != NULL)
    {
        inorder(node->left);
        printf("%d ",node->data);
        inorder(node->right);
    }
}
  
int main(){
    Tree tree;
    tree.root = NULL;//创建一个空树
    int n;
    scanf("%d",&n);
  
    //输入n个数并创建这个树
    for (int i = 0; i < n; i++){
        int temp;
        scanf("%d",&temp);
        insert(&tree, temp);
    }
  
    inorder(tree.root);//中序遍历
  
    return 0;
}