首页 > 代码库 > C 数据结构之树

C 数据结构之树

树的遍历方式:

         前序遍历:前序遍历是先打印根节点,在打印左子树,最后打印右节点。在打印左右子树的时候,又将子树作为一个完整的数来进行打印。直到节点的子树为空。

         中序遍历:中序遍历是先打印左子树,再打印根节点,最后打印右节点。在打印左右子树的时候,又将子树作为一个完整的数来进行打印。直到节点的子树为空。

         后序遍历:后序遍历是先打印左子树,在打印右子树,最后打印根节点。在打印左右子树的时候,又将子树作为一个完整的数来进行打印。直到节点的子树为空。

 

 

//前序遍历

void fPrint(struct Node * node){

    printf("%c   ",node->data);         // 先打印的根节点

    if(node->left!=NULL){                

        struct Node * temp=node->left;

        fPrint(temp)                           // 再打印左子树

    }

    if(node->right!=NULL){

        struct Node * temp=node->right;

        fPrint(temp);                        //再打印右子树

    }

}

 

//中序遍历

void cPrint(struct Node * node){

    if(node->left!=NULL){

        struct Node * temp=node->left;

        cPrint(temp);

    }

    printf("%c   ",node->data);

    if(node->right!=NULL){

        struct Node * temp=node->right;

        cPrint(temp);

    }

}

 

//后序遍历

void ePrint(struct Node * node){

    if(node->left!=NULL){

        struct Node * temp=node->left;

        ePrint(temp);

    }

    if(node->right!=NULL){

        struct Node * temp=node->right;

        ePrint(temp);

    }

    printf("%c   ",node->data);

}

 下面是数结构的C语言实现过程:

 方法声明:

#ifndef __part_tree_h

#define __part_tree_h

#include <stdio.h>

struct Node{

    char data;

    struct Node * parent;

    struct Node * left;

    struct Node * right;

};

struct Node * newNode(char ch);

struct Node * initTree();

void fPrint(struct Node * node);

void cPrint(struct Node * node);

void ePrint(struct Node * node);

#endif /* __part_tree_h */

 

方法实现:

 

#include "2 part tree.h"

#include <stdlib.h>

 

struct Node * newNode(char ch){

    struct Node * node=(struct Node *)malloc(sizeof(struct Node));

    node->data=http://www.mamicode.com/ch;

    node->parent=NULL;

    node->left=NULL;

    node->right=NULL;

    return node;

}

 //实例化树

struct Node * initTree(){

    struct Node * a=newNode(‘A‘);

    struct Node * b=newNode(‘B‘);

    struct Node * c=newNode(‘C‘);

    struct Node * d=newNode(‘D‘);

    struct Node * e=newNode(‘E‘);

    struct Node * f=newNode(‘F‘);

    struct Node * g=newNode(‘G‘);

    a->left=b;

    a->right=c;

    b->left=d;

    b->right=e;

    b->parent=a;

    c->right=f;

    c->parent=a;

    d->parent=b;

    e->left=g;

    e->parent=b;

    f->parent=c;

    g->parent=e;

    return a;

}

 

//前序遍历

void fPrint(struct Node * node){

    printf("%c   ",node->data);          

    if(node->left!=NULL){

        struct Node * temp=node->left;

        fPrint(temp);

    }

    if(node->right!=NULL){

        struct Node * temp=node->right;

        fPrint(temp);

    }

}

 

//中序遍历

void cPrint(struct Node * node){

    if(node->left!=NULL){

        struct Node * temp=node->left;

        cPrint(temp);

    }

    printf("%c   ",node->data);

    if(node->right!=NULL){

        struct Node * temp=node->right;

        cPrint(temp);

    }

}

 

//后序遍历

void ePrint(struct Node * node){

    if(node->left!=NULL){

        struct Node * temp=node->left;

        ePrint(temp);

    }

    if(node->right!=NULL){

        struct Node * temp=node->right;

        ePrint(temp);

    }

    printf("%c   ",node->data);

}

 

主方法:

#include <stdio.h>

#include "2 part tree.h"

int main(int argc, const char * argv[]) {

    struct Node * node = initTree();

    printf("前序遍历: ");

    fPrint(node);

    printf("\n\n");

    printf("中序遍历: ");

    cPrint(node);

    printf("\n\n");

    printf("后序遍历: ");

    ePrint(node);

    printf("\n\n");

    return 0;

}

 

 

         二叉搜索树:二叉树中的每个节点都大于等于其左子树的中的任一节点,都小于等于其右子树的任意节点。

C 数据结构之树