美文网首页
二叉树（C实现）

二叉树（C实现）

作者: 大成小栈 | 来源:发表于2021-04-23 21:44 被阅读0次

    假设要生成的二叉树如下图；

    1. 二叉树的数据结构

    如图，在树的每个节点中，需要保存的数据只有一个整数；

    struct BinaryTree {
    int data; // Data area
    //TODO
};

    所以在结构体里面，我们的代码应该类似上面的写法；通过观察我们还发现，每一个节点都指向左右两边（除了最后的叶子节点外）。
    因此，我们需要让它有两个指针域：

    struct BinaryTree {
    int data;   // Data area
    void *left;
    void *right;
};

    上面的定义格式似乎是正确的，但是，类型好像并不是我们想要的；
    例如：当left指向左边的子节点时，子节点应该也是一个包含数据域的节点，因此我们需要再定义一个与它本身相同的结构体：

    struct BinaryTree {
    int data;   // Data area
    struct BinaryTree *left;
    struct BinaryTree *right;
};

    所以，我们会这样去定义它，显然，这是一个递归定义。如果我们要实例化一个节点，我们可以:

    struct BinaryTree *tree;

    显然，我们需要定义一个实例时写那么长的类型名字，实在让人难受，因此，我们可以这样：

    typedef struct BinaryTree TreeNode;
TreeNode *tree;

    到此为止我们的数据结构就定义好了！
    你现在的代码应该是下面的样子：

    struct BinaryTree {
    int data;   // Data area
    struct BinaryTree * left;
    struct BinaryTree * right;
};  

typedef struct BinaryTree TreeNode;

    2. 二叉树的生成

    接下来我们需要把数据插入到对应的位置上，我们希望树左边分支的的数据总是比树右边分支的要小。因此，我们代码会像下面这样写：

    void insert(TreeNode ** tree, int val) {
    TreeNode * temp = NULL;
    if(!(*tree)) {
        //TODO
        return ;
    }
    
    if (val < (*tree)->data) {
        //TODO
    } else if (val > (*tree)->data) {
        //TODO
    }
}

    第一个if语句判断这个树节点是否存在；
    若是不存在，我们应该生成一个节点，然后添加到树上来；
    第二个if-else呢，则是判断目标数据是大于当前节点还是小于，若小于，存左分支，若大于存右分支。

    if(!(*tree)) {
        temp = (TreeNode *)malloc(sizeof(TreeNode));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return ;
    }

    temp的作用是临时变量正如其名；
    malloc分配内存，初始化节点左右指针域为空，以及数据域为val；
    最后*tree=temp 把节点安装到树上；
    并且返回上一级；
    对于已经存在的树节点，我们需要往左右两分子扩展；

     if (val < (*tree)->data) {
        insert(&(*tree)->left,val);
  } else if (val > (*tree)->data) {
        insert(&(*tree)->right,val);
  }

    可以看出，只对小于和大于两个方向的数据进行操作；
    你也许会考虑到万一等于呢？注意，在这里应该是数据的唯一性有要求的，它类似于数学里的集合，不会有重复的。

    那么这个函数的所有代码如下：

    void insert(TreeNode ** tree, int val) {
    node * temp = NULL;
    if(!(*tree)) {
        temp = (TreeNode *)malloc(sizeof(TreeNode));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return ;
    }
    
    if (val < (*tree)->data) {
        insert(&(*tree)->left,val);
    }else if (val > (*tree)->data) {
        insert(&(*tree)->right,val);
    }
}

    节点创建好了（此处用malloc创建），在堆中分配的内存，我们需要手动释放，那显然需要用到free函数与之对应。

    所以，我们释放节点的函数应该是这样：

    void deltree(TreeNode * tree) {
    if(tree) {
        free(tree);
    }
}

    但是，仔细观察发现直接释放free就只是释放了根节点，
    因此，我们需要这样做：

    void deltree(TreeNode * tree) {
    if(tree) {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}

    这样我们找到左边的根啦，又继续往左边找；
    找不到啦，就往右边找；
    再找不到啦，就执行到free释放节点然后返回上一级；
    好啦！树也有函数建，也有办法“砍”了！
    接下来是怎么展示我们的树啦！

    3. 二叉树的递归遍历

    树的遍历有三种：前序、中序、后序。首先，我们需要判断tree是否空；

    void preOrder(TreeNode * tree) {
    if(tree) {
        //TODO
    }
}

// 前序
void preOrder(TreeNode * tree) {
    if(tree) {
        printf("%d ",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }
}
// 中序
void inOrder(TreeNode * tree) {
    if(tree) {
        print_inorder(tree->left);
        printf("%d ",tree->data);
        print_inorder(tree->right);
    }
}
// 后序
void postOrder(TreeNode * tree) {
    if(tree) {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d ",tree->data);
    }
}

// 测试方法
int main(void) {

    TreeNode * root;
    TreeNode * tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root,9);
    insert(&root,4);
    insert(&root,15);
    insert(&root,6);
    insert(&root,12);
    insert(&root,17);
    insert(&root,2);

    printf("Pre Order Display\n");
    preOrder(root);
    printf("\n");

    printf("In Order Display\n");
    inOrder(root);
    printf("\n");

    printf("Post Order Display\n");
    postOrder(root);
    printf("\n");

    /* Deleting all nodes of tree */
    deltree(root);
}

////运行结果如下：
//Pre Order Display
//9 4 2 6 15 12 17
//In Order Display
//2 4 6 9 12 15 17
//Post Order Display
//2 6 4 12 17 15 9

    4. 二叉树的迭代遍历

    简单的递归遍历如下：

    void preOrder(Tree  *root){
    if(root){
        Visit(root->data);  //printf
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
} 

void inOrder(Tree  *root){
    if(root){
        inOrder(root->lchild);
        Visit(root->data);  //printf
        inOrder(root->rchild);
    }
} 

void postOrder(Tree  *root){
    if(root){
        postOrder(root->lchild);
        postOrder(root->rchild);
        Visit(root->data); //printf
    }
}

    迭代遍历：

    //// 前序遍历
void preOrder(Tree *root){
    Stack s;
    Tree *cur=root;
    Tree *top=NULL;
    
    
    if(root==NULL) return ;
    Init(&s);
    
    while(cur || !StackEmpty(&s)){
        while(cur){
            Visit(cur->data);
            Push(&s,cur);
            cur=cur->lchild;
        }
        top=StackTop(&s);
        Pop(&s);
        cur=top->rchild;

    }
}

//// 中序遍历
void inOrder(Tree *root){
    Stack s;
    Tree *cur=root;
    Tree *top=NULL;
    
    
    if(root==NULL) return ;
    Init(&s);
    
    while(cur || !StackEmpty(&s)){
        while(cur){
            
            Push(&s,cur);
            cur=cur->lchild;
        }
        top=StackTop(&s);
        Visit(cur->data);
        Pop(&s);
        cur=top->rchild;

    }
}

//// 后序遍历
void postOrder(Tree *root){
    Stack s;
    Tree *cur=root;
    Tree *top=NULL;
    Tree *prev=NULL;
    
    
    if(root==NULL) return ;
    Init(&s);
    
    while(cur || !StackEmpty(&s)){
        while(cur){
            
            Push(&s,cur);
            cur=cur->lchild;
        }
        top=StackTop(&s);
        
        if(top->rchild==NULL || top->rchild==prev){
            Visit(top->data);
            prev=top;
            Pop(&s);
        }
        else{
            cur=top->rchild;
        }

    }
}

    5. 二叉树的广度遍历

    ？？

    6. 计算二叉树的高度

    递归的方式来计算二叉树高度（只有一个根节点的二叉树高为1）。

    //二叉树节点定义
typedef int ElementType;
typedef struct bitnode
{
    ElementType data;  //数据域 
    struct bitnode *left, *right; //指针域 
} bitnode, *bitree;  //bitnode为结构体，bitree为指向结构体bitnode的指针 
 
 
//先序创建一棵二叉树
bitree CreateTree() {
    bitree T;
    ElementType item;
    
    cin >> item;
    if( item == 0 )  {
        T = NULL;                    //T为空树 
    }
    else {
        T = (bitree)malloc(sizeof(bitnode));
        T->data = item;
        
        T->left = CreateTree();              //递归创建左子树 
        T->right = CreateTree();             //递归创建右子树 
    } 
    
    return T;                              //返回根节点 
} 

//释放树的空间 
bitree FreeTree(bitree T) {
    if( T ) {
        FreeTree(T->left);                  //递归释放其左子树 
        FreeTree(T->right);                 //递归释放其右子树 
        
        free(T);                            //释放掉根节点 
        T = NULL;                           //释放掉指向根节点的指针，避免野指针 
    }
    
    return T;
}
 
//计算一棵树的高度
int TreeHeight(bitree T) {
    if( T == NULL )  //空树，返回0 
        return 0;
    if( T->left == NULL && T->right == NULL ) //树根返回1 
        return 1;
    return max(TreeHeight(T->left), TreeHeight(T->right)) + 1; //树的高度 = MAX(左子树的高度，右子树的高度) + 1;
} 

int main() {
    bitree root;
    int height = 0;
    
    root = CreateTree();
    
    height = TreeHeight(root);
    cout << "树的高度为:" << height << endl;
    
    root = FreeTree(root);
    if(root == NULL)
        cout << "释放成功" << endl;
        
    return 0;
}

    相关文章

      网友评论

          本文标题：二叉树（C实现）

          本文链接：https://www.haomeiwen.com/subject/lxyhrltx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|二叉树（C实现）|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！