二叉樹存儲

1. 簡介

根據(jù)前文的介紹，我們知道了二叉樹的性值，其就是一種每一個結點中只允許擁有左右孩子（或為空）的樹，這種數(shù)據(jù)結構在我們的實際設計中非常常用，如前文提到的STL中的set集合，其底層就是一顆標準的紅黑樹（二叉樹的一種），我們這里以創(chuàng)建一顆二叉樹并實現(xiàn)通過特定的插入順序和讀取順序達成讀取為順序為例子進行簡介。

2. 結點設計

一顆二叉樹的結點設計一定要有如下內容：

a)結點元素，data域，用來存儲數(shù)據(jù)，其可以是int，char等基本的類型，同時也可以是struct等這些復雜的復合數(shù)據(jù)類型。

b)左孩子結點，left指針，總是用來指向當前結點的下一層的左邊結點，其屬于一種指針。

c)右孩子結點，right指針，總是用來指向當前結點的下一層的右邊結點，其屬于一種指針。

d)父結點（可選），parent指針，總是指向當前結點的前一個結點，簡稱父親結點，其不屬于必須結點設計，省略掉可以打擾節(jié)省內存的效果，而使用則可以更方便進行定向搜索，本案例中不使用父節(jié)點。

以上就是一顆二叉樹的結點設計，除此之外，我們使用一棵樹的時候需要建立一顆樹根，由這個“根”，來進行逐步的向下構建。

其設計代碼可以表示為：

//樹的結點
typedef struct node{
    int data;
    struct node* left;
    struct node* right;
} Node;
 
//樹根
typedef struct {
    Node* root;
} Tree;

3.樹的創(chuàng)建

如同當時學習鏈表的創(chuàng)建，首先，我們創(chuàng)建一個空的結點再進行連接，首先將這個空的結點中的date域賦予數(shù)據(jù)，再判斷tree中是否是一個空樹，如果為空，只需要將整個根指向這一個結點即可，如果不為空，再進行兩個判斷，判斷輸入的數(shù)據(jù)是否大于或者小于當前比對的結點數(shù)據(jù)，根據(jù)其大小進行相應的排列，這樣存儲進入的數(shù)據(jù)總是有一定規(guī)律的，在輸出的時候根據(jù)這個規(guī)律進行輸出就可以達到想要的效果。

其代碼可以顯示為：

//創(chuàng)建樹--插入數(shù)據(jù)
void insert(Tree* tree, int value){
    //創(chuàng)建一個節(jié)點，讓左右指針全部指向空，數(shù)據(jù)為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 {//繼續(xù)往下搜尋
                    temp = temp->left;
                }
            } else { //否則進右兒子
                if (temp->right == NULL){
                    temp->right = node;
                    return;
                }
                else {//繼續(xù)往下搜尋
                    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.相關試題

二叉樹的基本創(chuàng)建

本文代碼

#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;
 
//創(chuàng)建樹--插入數(shù)據(jù)
void insert(Tree* tree, int value){
    //創(chuàng)建一個節(jié)點，讓左右指針全部指向空，數(shù)據(jù)為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 {//繼續(xù)往下搜尋
                    temp = temp->left;
                }
            } else { //否則進右兒子
                if (temp->right == NULL){
                    temp->right = node;
                    return;
                }
                else {//繼續(xù)往下搜尋
                    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;//創(chuàng)建一個空樹
    int n;
    scanf("%d",&n);
 
    //輸入n個數(shù)并創(chuàng)建這個樹
    for (int i = 0; i < n; i++){
        int temp;
        scanf("%d",&temp);
        insert(&tree, temp);
    }
 
    inorder(tree.root);//中序遍歷
 
    return 0;
}