数据结构七

一、二叉树的存储

说明：树的存储分为链式存储和顺序存储两种，然而顺序存储简单，实际中的使用少之又少，因此，这里只使用链式

1.二叉树的链式存储

#include "stdio.h"
#include "stdlib.h"

typedef char ElemType;
struct BiTNode{
    ElemType data;
    struct BiTNode* lChild,* rChild;
};
//创建一个节点
struct BiTNode* CreateNode(ElemType data){
    struct BiTNode* p=(struct BiTNode*) malloc(sizeof(struct BiTNode));
    if(!p){
        printf("No enough memory to allocate!\n");
        exit(0);
    }
    p->data=data;
    p->lChild=NULL;
    p->rChild=NULL;
    return p;
}
//插入元素
struct BiTNode* InsertNode(struct BiTNode* T,ElemType data){
    if(T==NULL){
        return CreateNode(data);
    }
    if(T->data>data)//在左孩子位置上插入
        T->lChild=InsertNode(T->lChild,data);
    else//在右孩子位置上插入
        T->rChild=InsertNode(T->rChild,data);
    return T;
}
//打印
void Visit(struct BiTNode* T){
    printf("The data of the binary-tree which is listed is %d\n",T->data);
}
//先序遍历
void PreOrder(struct BiTNode* T){
    if(T!=NULL){
        Visit(T);
        PreOrder(T->lChild);
        PreOrder(T->rChild);
    }
}
//中序遍历
void InOrder(struct BiTNode* T){
    if(T!=NULL){
        InOrder(T->lChild);
        Visit(T);
        InOrder(T->rChild);
    }
}
//后序遍历
void PostOrder(struct BiTNode* T){
    if(T!=NULL){
        PostOrder(T->lChild);
        PostOrder(T->rChild);
        Visit(T);
    }
}
//获取树的深度
int TreeDepth(struct BiTNode* T){
    if(T==NULL){
        return 0;
    } else{
        int l= TreeDepth(T->lChild);
        int r= TreeDepth(T->rChild);
        return l>r?l+1:r+1;
    }
}
int main(){
    //1.定义一个空树
    struct BiTNode* root= CreateNode(5);
    //2.插入新节点
    //3.插入一个新节点
    root= InsertNode(root,1);
    root= InsertNode(root,6);
    root= InsertNode(root,2);
    root= InsertNode(root,3);
    root= InsertNode(root,7);
    root= InsertNode(root,9);
    root= InsertNode(root,8);
    root= InsertNode(root,4);
    //4.先序遍历
    printf("-----pre-order-----\n");
    PreOrder(root);
    //5.中序遍历
    printf("-----in-order-----\n");
    InOrder(root);
    //6.后序遍历
    printf("-----post-order-----\n");
    PostOrder(root);
    //7.树的深度
    printf("The height of binary-tree which is listed is %d\n", TreeDepth(root));
    return 0;
}

实现效果

D:\project\clion\ch3\cmake-build-debug\binary_tree_list.exe
-----pre-order-----
The data of the binary-tree which is listed is 5
The data of the binary-tree which is listed is 1
The data of the binary-tree which is listed is 2
The data of the binary-tree which is listed is 3
The data of the binary-tree which is listed is 4
The data of the binary-tree which is listed is 6
The data of the binary-tree which is listed is 7
The data of the binary-tree which is listed is 9
The data of the binary-tree which is listed is 8
-----in-order-----
The data of the binary-tree which is listed is 1
The data of the binary-tree which is listed is 2
The data of the binary-tree which is listed is 3
The data of the binary-tree which is listed is 4
The data of the binary-tree which is listed is 5
The data of the binary-tree which is listed is 6
The data of the binary-tree which is listed is 7
The data of the binary-tree which is listed is 8
The data of the binary-tree which is listed is 9
-----post-order-----
The data of the binary-tree which is listed is 4
The data of the binary-tree which is listed is 3
The data of the binary-tree which is listed is 2
The data of the binary-tree which is listed is 1
The data of the binary-tree which is listed is 8
The data of the binary-tree which is listed is 9
The data of the binary-tree which is listed is 7
The data of the binary-tree which is listed is 6
The data of the binary-tree which is listed is 5
The height of binary-tree which is listed is 5

Process finished with exit code 0