qq_51347217
2021-06-15 09:53
采纳率: 100%
浏览 23

用C语言实现 无任何限制

假设二叉树采用链式存储方式,root为其根节点,p指向二叉树中的任意一个节点,编写一个求从根节点到p所指节点之间路径长度的函数   

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • CSDN专家-Fay 2021-06-15 09:55
    已采纳

    C语言链表二叉树:

    如有帮助还望在我的回答上点个【采纳】,后期有问题可以私信交流!

    //    二叉树的实现(C语言)
    //    链表,递归实现
    //    编译环境:visual studio 2017
    //    操作系统:win8.1
    
    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    
    typedef char Elementtype;    //    定义数据类型,可根据需要自行定制
    typedef struct TreeNode * Node;    //    Node相当于struct treeNode *
    //    定义数节点结构
    typedef struct TreeNode {
        Elementtype Element;
        Node left;    //    树节点的左子节点
        Node right;    //    树节点的右子节点
    }TREE,*PTREE;
    
    //    函数声明
    void CreatTree(PTREE *);    //    树的先序创建函数
    void PreOrderTree(PTREE );    //    树的前序遍历函数
    void InOrderTree(PTREE );    //    树的中序遍历
    void PostOrderTree(PTREE );    //    树的后序遍历
    void LeafOfTree(PTREE );    //    打印树的叶子节点函数
    int  Get_Leaf_Num(PTREE );    //    获取树叶子节点个数
    int Get_Height(PTREE );    //    获取树的高度
    
    
    //    主函数
    int main() {
        
        PTREE Root;    
        printf("请先序输入二叉树的节点数据: ");
        CreatTree(&Root);    
        printf("\n前序遍历结果为:");
        PreOrderTree(Root);    
        printf("\n中序遍历结果为:");
        InOrderTree(Root);
        printf("\n后序遍历结果为:");
        PostOrderTree(Root);
        printf("\n打印叶子节点为:");
        LeafOfTree(Root);
        printf("\n叶子节点个数为:%d", Get_Leaf_Num(Root));
        printf("\n二叉树的高度为:%d", Get_Height(Root));
        printf("\n");
    
        return 0;
    }
    
    //    定义树先序创建函数
    void CreatTree(PTREE *Root) {
        char val=0;    //    用于下面存放数据
        val=getchar();    //    输入数据值
        //    如果输入'*',则指向为空
        if (val == '*')
            (*Root) = NULL;
        //    如果输入非'*',则给数据域赋值
        else {
            (*Root) = (PTREE)malloc(sizeof(TREE));    //    申请内存空间
            if ((*Root) == NULL) {
                printf("创建节点失败,无法分配可用内存...");
                exit(-1);
            }
            else {
                (*Root)->Element = val;    //    给节点数据域赋值
                CreatTree(&(*Root)->left);
                CreatTree(&(*Root)->right);
            }
        }
        
    }
    //    树的前序遍历函数定义
    void PreOrderTree(PTREE Root) {
    
        if (Root == NULL)
            return;
        else {
            putchar(Root->Element);
            PreOrderTree(Root->left);
            PreOrderTree(Root->right);
    
        }
    }
    //    树的中序遍历函数定义
    void InOrderTree(PTREE Root) {
    
        if (Root == NULL)
            return;
        else {
            InOrderTree(Root->left);
            putchar(Root->Element);
            InOrderTree(Root->right);
    
        }
    }
    
    //    树的后序遍历函数定义
    void PostOrderTree(PTREE Root) {
    
        if (Root==NULL) 
            return ;
        else{
            PostOrderTree(Root->left);
            PostOrderTree(Root->right);
            putchar( Root->Element);
        }
    }
    
    
    
    //    打印树的叶子节点函数定义
    void LeafOfTree(PTREE Tree) {
        if (Tree == NULL)    
            return ;
    
        else {
            if (Tree->left == NULL&&Tree->right == NULL)
                putchar(Tree->Element);
            else {
                LeafOfTree(Tree->left);
                LeafOfTree(Tree->right);
            }
        }
            
    }
    
    //    获取树的叶子节点个数函数定义
    int Get_Leaf_Num(PTREE Tree) {
        if (Tree == NULL)
            return 0;
        if (Tree->left == NULL&&Tree->right == NULL)
            return 1;
        //递归整个树的叶子节点个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数
        return Get_Leaf_Num(Tree->left) + Get_Leaf_Num(Tree->right);
    }
    //    获取树高的函数定义
    int Get_Height(PTREE Tree) {
        int Height = 0;
        if (Tree == NULL)
            return 0;
        
        //树的高度 = max(左子树的高度,右子树的高度) + 1
        else
        {
            int L_Height = Get_Height(Tree->left);
            int R_Height = Get_Height(Tree->right);
            Height = L_Height >= R_Height ? L_Height + 1 : R_Height + 1;
        }
        return Height;
    }
    1 打赏 评论
  • #include "bitree.h" //请不要删除,否则检查不通过
    #include <stdio.h>
    #include <stdlib.h>
     
    bool path(BiTNode* root, BiTNode* node, Stack* s)
    {
        BiTNode *p, *q; // ElemType p;
        int i = 0;
     
        p = root;
        q = NULL;
        init_stack(s);
     
        if (p == NULL || node == NULL)
            return false;
        if (p == node) {
            push(s, p);
            return true;
        }
     
        while (p != NULL || !is_empty(s)) {
            while (p) {
                push(s, p);//非空就先压进去 
                if (p == node)//node已经压进去了 
                    return true;
                p = p->left;//先根遍历 
            }
            top(s, &p); //回到分支的根
            if (p->right == q || p->right == NULL) {
                q = p;//第一个判断条件很关键, 判是否已经遍历过 
                pop(s, &p);//左子树前面的while遍历了, 该结点的右子树遍历了或者为空就不要这个节点了 
                p = NULL; //置空就不会被再次压入 ,过前面的while循环,  等待下一次top赋值, 层次-1//这里指针断了 
                //需要注意的是p虽然指向该节点但是置空, 该结点任然存在, 并且q结点指向避免再次访问 
            } else {
                p = p->right;
            }
        }
     
        return false;
    }

    参考(2条消息) 数据结构--二叉树--路径 假设二叉树采用二叉链表方式存储, root指向根结点,node 指向二叉树中的一个结点, 编写函数 path,计算root到 node 之间的路径,(该路径包括root结_风起-CSDN博客_假设二叉树采用二叉链表存储结构

    2 打赏 评论
  • 有问必答小助手 2021-06-17 18:35

    您好,我是有问必答小助手,您的问题已经有小伙伴解答了,您看下是否解决,可以追评进行沟通哦~

    如果有您比较满意的答案 / 帮您提供解决思路的答案,可以点击【采纳】按钮,给回答的小伙伴一些鼓励哦~~

    ps: 问答会员年卡【8折】购 ,限时加赠IT实体书,即可 享受50次 有问必答服务,了解详情>>>https://t.csdnimg.cn/RW5m

    打赏 评论

相关推荐 更多相似问题