手机版
你好,游客 登录 注册
背景:
阅读新闻

二叉树的代码实现

[日期:2017-10-02] 来源:Linux社区  作者:chen0547 [字体: ]

二叉树是一种非线性的结构,但是在计算机中存储时,却要按照线性来存储。二叉树也是由一个一个结点构成,只不过是,一个结点中既要存放数据,又要存放左孩子的指针和右孩子的指针。所以,我们想要实现二叉树,首先就得有一个二叉树的结构,根据刚才的分析,那么二叉树结构中的变量应该要有三个。代码如下:

struct BiTNode{
 
    int data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
};

  有了这么一个二叉树的结构之后,我们可以开始动态的创建结点。比如,我们要创建的这棵树有5个元素,A、B、C、D、E。那么,创建结点的代码如下:

struct BiTNode *A = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *B = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *C = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *D = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );
struct BiTNode *E = ( struct BiTNode * ) malloc ( sizeof ( struct BiTNode ) );

接下来,就是要对这些结点进行初始化,并且生成一棵树。这棵树,先序遍历结果为:
A->B->C->D->E

中序遍历结果为:
B->A->D->C->E

有了树的理论上的形状之后,我们要开始对这些结点进行联接。代码如下:

A->data = 'A';
A->lchild = B;
A->rchild = C;
B->data = 'B';
B->lchild = B->rchild = NULL;
C->data = 'C';
C->lchild = D;
C->rchild = E;
D->data = 'D';
D->lchild = D->rchild = NULL;
E->data = 'E';
E->lchild = E->rchild = NULL;

二叉树创建好之后,就是要开始遍历二叉树了。二叉树的遍历有三种,前序,中序和后序。二叉树的遍历事实上是通过递归实现的。那么,先来实现,先序遍历。代码如下:
void PreOrderTraverse ( struct BiTNode *T ){
 
    if ( T == NULL )
        return;
         
    if ( T != NULL )
    printf ( "%c", T->data );    //先访问根结点
    if ( T != NULL )
    PreOrderTraverse ( T->lchild );  //访问左子树
    if ( T != NULL )
    PreOrderTraverse ( T->rchild );  //访问右子树
     
}

接着是中序遍历,中序遍历不过是先访问左子树,再访问根结点,最后访问右子树。代码如下:
 void InOrderTraverse ( struct BiTNode *T ){
 
    if ( T == NULL )
        return;
         
    if ( T != NULL )
        InOrderTraverse ( T->lchild );
    if ( T != NULL )
        printf ( "%c", T->data );
    if ( T != NULL )
        InOrderTraverse ( T->rchild );
 
}

最后一种,就是后序遍历。后序遍历就是先访问左子树,再访问右子树,最后访问根结点。代码如下:
 void PostOrderTraverse ( struct BiTNode *T ){
 
    if ( T == NULL )
        return;
         
    if ( T != NULL )
        PostOrderTraverse ( T->lchild );
    if ( T != NULL )
        PostOrderTraverse ( T->rchild );
    if ( T != NULL )
        printf ( "%c", T->data );
 
}

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-10/147250.htm

linux
相关资讯       二叉树 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款