首页 > 其他分享 >12、二叉树

12、二叉树

时间：2024-09-29 08:51:58浏览次数：1  
标签：node rightChild 12 st leftChild 二叉树 BinTreeNode NULL

1、二叉树的定义和初始化

//二叉树节点定义 
typedef struct BinTreeNode{
    ElemType data;
    struct BinTreeNode* leftChild;
    struct BinTreeNode* rightChild;
}BinTreeNode;

//二叉树定义 
typedef struct BinTree{
    BinTreeNode* root;
    ElemType refvalue; //结束标记 
}BinTree;

//初始化二叉树,并规定结束标记为 #
void initBinTree(BinTree* tree,ElemType ref){
    tree->root = NULL;
    tree->refvalue = ref; 
}

2、二叉树的创建方式

// 创建二叉树方式1 [node 是二级指针 C++可以通过BinTreeNode*& node引用的简便写法]
void createBinTree_1(BinTree* bt,BinTreeNode** node){
    ElemType item;
    scanf("%c",&item);
    if(item == bt->refvalue)
        *node = NULL;
    else{
        (*node) = (BinTreeNode*) malloc(sizeof(BinTreeNode));
        assert(*node != NULL);
        //创建根
        (*node)->data = item; 
        //递归创建
        createBinTree_1(bt,&(*node)->leftChild);
        createBinTree_1(bt,&(*node)->rightChild);
    }
}

//创建二叉树方式2 通过返回根节点创建二叉树
BinTreeNode* createBinTree_2(BinTree* bt){
    ElemType item;
    scanf("%c",&item);
    if(item == bt->refvalue)
        return NULL;
    else{
        BinTreeNode* node = (BinTreeNode*) malloc(sizeof(BinTreeNode));
        assert(node != NULL);
        node->data = item;
        node->leftChild = createBinTree_2(bt);
        node->rightChild = createBinTree_2(bt);
        return node;
    }
} 
//创建二叉树方式3 根据字符串str创建二叉树
//此处是错误代码,原因:char* str  
//        1.createBinTree_3(bt,&(*node)->leftChild,++str);
//        2.createBinTree_3(bt,&(*node)->rightChild,++str);
//      在运行这两行代码时，如果 在运行1时又递归调用了 1 ,
//        str不会进行改变,也就说不会"+2",在回来运行2时还是+1的状态
//      所以此处不应该char* 想要改变一级指针的值就需要二级指针 
//void createBinTree_3(BinTree* bt,BinTreeNode** node,char* str){
//    if(*str == bt->refvalue){
//        *node = NULL;
//      ++str;
//    } else {
//        *node = (BinTreeNode*) malloc(sizeof(BinTreeNode));
//        assert(node != NULL);
//        (*node)->data = *str;
//        //递归创建
//      str++
//        createBinTree_3(bt,&(*node)->leftChild,str);
//        createBinTree_3(bt,&(*node)->rightChild,str);
//    }
//}
//改进 ABC##DE##F##G#H##
void createBinTree_3(BinTree* bt,BinTreeNode** node,char** str){
    if(**str == bt->refvalue){
        ++(*str);
        *node = NULL;
    } else {
        *node = (BinTreeNode*) malloc(sizeof(BinTreeNode));
        assert(node != NULL);
        (*node)->data = **str;
        //递归创建
        ++(*str);
        createBinTree_3(bt,&(*node)->leftChild,str);

        createBinTree_3(bt,&(*node)->rightChild,str);
    }
}

3、二叉树遍历

3.1、递归方式

//先序遍历
void preOrder(BinTreeNode* node){
    if(node != NULL){
        printf("%c ",node->data);
        preOrder(node->leftChild);
        preOrder(node->rightChild);
    }
}

//中序遍历
void inOrder(BinTreeNode* node){
    if(node != NULL){
        inOrder(node->leftChild);
        printf("%c ",node->data);
        inOrder(node->rightChild);
    }
} 

//后序遍历
void postOrder(BinTreeNode* node){
    if(node != NULL){
        postOrder(node->leftChild);
        postOrder(node->rightChild);
        printf("%c ",node->data);
    }
}

3.2、非递归方式

//先序遍历-不采用递归
void preOrder(BinTreeNode* node){
    if(node != NULL){
        SeqStack st;
        InitStack(&st);
        BinTreeNode* p;
        //根节点入栈 
        push(&st,node);
        while(!isEmpty(&st)){
            //当栈不为空
            //获取栈顶 元素 
            GetTop(&st,&p);
            //出栈
            Pop(&st);
            //访问元素 
            printf("%c ",p->data); 
            if(p->rightChild != NULL)
                //先将右节点入栈 
                push(&st,p->rightChild);
            if(p->leftChild != NULL)
                //在将左节点入栈 
                push(&st,p->leftChild);
        }
    }
} 

// 中序遍历
void inOrder(BinTreeNode* node){
    if(node != NULL){
        SeqStack st;
        InitStack(&st);
        BinTreeNode* p;
        //根节点入栈 
        push(&st,node);
        while(! isEmpty(&st)){
            //将当前节点的左子树入栈 
            while(node != NULL && node->leftChild != NULL){
                Push(&st,node->leftChild);
                node = node->leftChild;
            }
            //当访问该节点的所有左子树时 
            GetTop(&st,&p);
            Pop(&st);
            printf("%c ",p->data);
            //访问完该节点的所有左子树，将该节点的右子树入栈 
            if(p->rightChild != NULL){
                node = p->rightChild;
                if(node != NULL)
                    Push(&st,node);
            }
        }
    }
} 
//后序遍历-非递归 核心思想:将该节点的左右子树都遍历完才访问该元素
//修改结构，增加标记位来记录该节点从哪边返回 
typedef enum{L,R} Tag;
typedef struct StkNode{
    BinTreeNode* prt;
    Tag tag;
}StkNode;

void postOrder(BinTreeNode* t){
    if(t != NULL){
        SeqStack st;
        InitStack(&st);
        StkNode sn;
        BinTreeNode* p;
        do{
            while(t != NULL){
                sn.prt = t;
                sn.tag = L;
                Push(&st,sn);
                t = t->leftChild;
            }
            bool flag = true;//是否继续访问的标记
            while(flag && !isEmpty(&st)){
                GetTop(&st, &sn);
                Pop(&st);
                p = sn->prt;
                switch(sn.tag){
                    case L:
                        //说明还没访问该节点的右子树
                        sn->tag = R;
                        Push(&st,sn);
                        flag = false;//第一次右节点,先找该右节点的左子树
                        t = p->rightChild;
                        break;  
                    case R:
                        //说明访问过右子树
                        printf("%c",p->data);
                        break; 
                }
            } 
        }while(!isEmpty(&st));
    }
}

3.3、层次遍历

  
//层次遍历
void leverOrder(BinTreeNode* node){
    if(node == NULL)
        return; 
    BinTreeNode* v;
    LinkQueue queue;//声明队列
    initQueue(&queue);//初始化队列
    enQueue(&queue,node);//入队根节点
     
    while(!isEmpty(&queue)){
        //获取队头元素 
        GetHead(&queue,&v);
        //出队
        DeQueue(&queue);
        //访问数据 
        printf("%c",v->data);
        //左节点入队 
        if(v->leftChild != NULL)
            EnQueue(&queue,v->leftChild);
        //右节点入队 
        if(v->rightChild != NULL)
            EnQueue(&queue,v->rightChild);
    }
}

4、其他常用方法实现

//二叉树节点个数
int Size(BinTreeNode* node){
    if(node == NULL){
        return 0;
    }
    return Size(node->leftChild) + Size(node->rightChild) + 1;
}

//二叉树高度
int Height(BinTreeNode* node) {
    if(node == NULL)
        return 0;
    else {
        int left_height = Height(node->leftChild);
        int right_height = Height(node->rightChild);
        return (left_height > right_height ? left_height : right_height) + 1;
    }
}

//查找节点
BinTreeNode* Search(BinTreeNode* t,ElemType key) {
    if(t == NULL)
        return NULL;
    if(t->data == key)
        return t;
    BinTreeNode* p = Search(t->leftChild,key);
    if(p != NULL)
        return p;
    return Search(t->rightChild,key);
} 
//查找节点的父节点
BinTreeNode* Parent(BinTreeNode* t,BinTreeNode* p){
    if(t == NULL || p == NULL)
        return NULL;
    if(t->leftChild == p || t->rightChild == p)
        return t;
    BinTreeNode* q = Parent(t->leftChild,p);
    if(q != NULL)
        return q;
    return Parent(t->leftChild,p);
} 

//求左子树
BinTreeNode* leftChild(BinTreeNode* p){
    if(p != NULL)
        return p->leftChild;
    return NULL;
} 

//求右子树
BinTreeNode* rightChild(BinTreeNode* p){
    if(p != NULL)
        return p->rightChild;
    return NULL;
} 

//判空
int BinTreeEmpty(BinTree* bt){
    return bt->root == NULL;
} 

//拷贝
void copy(BinTreeNode** bt1,BinTreeNode* bt2){
    if (bt2 == NULL) {
        *bt1 = NULL; // 如果 bt2 为空，则设置 *bt1 为空
    } else {
        *bt1 = (BinTreeNode*)malloc(sizeof(BinTreeNode)); // 分配新节点
        assert(*bt1 != NULL); // 确保内存分配成功
        (*bt1)->data = bt2->data; // 复制数据
        copy(&(*bt1)->leftChild, bt2->leftChild); // 递归复制左子树
        copy(&(*bt1)->rightChild, bt2->rightChild); // 递归复制右子树
    }
} 
//清除树的所有节点
void BinTreeClear(BinTreeNode** t){
    if(*t != NULL){
        BinTreeClear(&(*t)->leftChild);
        BinTreeClear(&(*t)->rightChild);
        free(*t);
        *t = NULL;
    }
} 



int main(){
    //ABC##DE##F##G#H##
    BinTree myTree;
    initBinTree(&myTree,'#');
//    createBinTree_1(&myTree,&myTree.root);
//    myTree.root = createBinTree_2(&myTree);
    char* str = "ABC##DE##F##G#H##";
    createBinTree_3(&myTree,&myTree.root,&str);
    preOrder(myTree.root);
    printf("\n");
    inOrder(myTree.root);
    printf("\n");
    postOrder(myTree.root);
    printf("\n");
    printf("Size=%d\n",Size(myTree.root));
    printf("Height=%d\n",Height(myTree.root));
    
    BinTreeNode* p = Search(myTree.root,'B');
    BinTreeNode* q = Parent(myTree.root,p);
    printf("Parent=%c\n",q->data);
    
    return 0;
}

5、二叉树的恢复实现(VLR_LVR_LRV)

//根据先序序列和中序序列生成二叉树 
//root是一级指针 
void createBinTreeByVLRAndLVR(BinTreeNode** t,char* VLR,char* LVR,int n){
    if(n == 0)
        *t = NULL;
    else{
        int k = 0;
        //找到中序序列中的根节点位置 
        while(VLR[0] != LVR[k])
            k++;
        *t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
        (*t)->data = LVR[k];
        //左子树递归创建 
        createBinTreeByVLRAndLVR(&(*t)->leftChild,VLR+1,LVR,k);
        //右子树递归创建
        // 先序遍历中 VLR+k+1之前的都是左子树的节点 
        createBinTreeByVLRAndLVR(&(*t)->rightChild,VLR + k + 1,LVR + k + 1,n - k - 1); 
    }
}

//根据中序序列和后序序列生成二叉树 后序先访问完左树再右树 
void createBinTreeByLVRAndLRV(BinTreeNode** t,char* LVR,char* LRV,int n){
    if(n == 0)
        *t = NULL;
    else{
        int k = 0;
        while(LRV[n - 1] != LVR[k])
            k++;
        *t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
        (*t)->data = LVR[k];
        //右子树递归创建 
        //当找到中序遍历的根节点在k的位置时，说明k之前的节点都是左子树节点,
        // 因为是后序遍历，所以左子树一定先显示。故LRV+k 
        createBinTreeByLVRAndLRV(&(*t)->rightChild,LVR + k + 1,LRV + k,n - k - 1);
        //左子树递归创建 
        createBinTreeByLVRAndLRV(&(*t)->leftChild,LVR,LRV,k);
    }
}

int main(){
    //先序序列 
    char* VLR = "ABCDEFGH";
    //中序序列
    char* LVR = "CBEDFAGH";
    //后序序列
    char* LRV = "CEFDBHGA";
    
    int n = strlen(VLR);
    BinTree myTree;
    initBinTree(&myTree,'#');
//    createBinTreeByVLRAndLVR(&myTree.root,VLR,LVR,n);

    createBinTreeByLVRAndLRV(&myTree.root,LVR,LRV,n);
    preOrder(myTree.root);
    printf("\n");
    inOrder(myTree.root);
    printf("\n");
    postOrder(myTree.root);
    printf("\n");
    return 0;
}

 

 

标签：node,rightChild,12,st,leftChild,二叉树,BinTreeNode,NULL
From： https://www.cnblogs.com/xpp3/p/18438800

相关文章

  • 13、线索二叉树
    1、线索化二叉树的定义和初始化#include<stdio.h>#include<malloc.h>#include<assert.h>#defineElemTypechartypedefstructBinTreeNode{ElemTypedata;structBinTreeNode*leftChild;structBinTreeNode*rightChild;intlTage;//左标记[0:......
  • 【CTF Web】BUUCTF SQLi-LABS Page-1(Basic Challenges) Less-12 Writeup（SQL注入+POST
    sqli-labs1点击启动靶机。SQLi-LABSPage-1(BasicChallenges)解法随便提交一些数据。审查元素。<formaction=""name="form1"method="post"> <divstyle="margin-top:15px;height:30px;">Username:&nbsp;&nbsp;&......
  • 08 常用：写入 读取文件格式为：alex|123
    练习1：请将user中的元素根据_链接，并写入'a1.txt'的文件"""user=['alex','eric']data="_".join(user)file_object=open('a1.txt',mode='w',encoding='utf-8')file_object.write(data)fil......
  • 2024-2025 20241312 《计算机基础与程序设计》第一周学习总结
    作业信息|这个作业属于哪个课程|2024-2025-1-计算机基础与程序设计）|||这个作业要求在哪里|2024-2025-1计算机基础与程序设计第一周作业)|----||这个作业的目标|快速浏览一遍教材计算机科学概论（第七版），课本每章提出至少一个自己不懂的或最想解......
  • 【前端】ES12：ES12新特性
    文章目录1逻辑赋值操作符2数字分隔符3replaceAll4Promise.any5WeakRef6FinalizationRegistry1逻辑赋值操作符逻辑赋值操作符??=、&&=、||=。leta=trueletb=false//a&&=b//falsea||=b;//trueconsole.log(a)letobj={name:"kerwin......
  • 【力扣 | SQL题 | 每日三题】力扣1068, 1204, 1193, 1084, 1141
    1.力扣1068：产品销售分析11.1题目：销售表 Sales：+-------------+-------+|ColumnName|Type|+-------------+-------+|sale_id|int||product_id|int||year|int||quantity|int||price|int|+-------------+-......
  • 12. 闭包
    一、闭包  在一个函数内部，我们可以在在定义一个函数，并且将内部的函数作为外部函数的返回值返回。这种高阶函数，我们也称为闭包。“闭”是指该函数是内嵌函数，“包”是指该函数包含外层函数作用域的引用（不是对全局作用域）。通过闭包，我们可以创建一些只有当前函数能访问的变量，我......
  • Leetcode 1235. 规划兼职工作
    1.题目基本信息1.1.题目描述你打算利用空闲时间来做兼职工作赚些零花钱。这里有n份兼职工作，每份工作预计从startTime[i]开始到endTime[i]结束，报酬为profit[i]。给你一份兼职工作表，包含开始时间startTime，结束时间endTime和预计报酬profit三个数组，请你计算并返回可......
  • 【算法】二叉树中的 DFS
     【ps】本篇有6 道 leetcode OJ。 目录一、算法简介二、相关例题1）计算布尔二叉树的值.1-题目解析.2-代码编写2）求根节点到叶节点数字之和.1-题目解析.2-代码编写3）二叉树剪枝.1-题目解析.2-代码编写4）验证二叉搜索树.1-题目解析.2-代码编写5）二叉......
  • 12 random案例 年会抽奖案例
    年会抽奖案例把向向过程编程函数实现时：可读性+重用性，print时，能不使用“”号时，尽量不使用-各部门统计员工的姓名=>部门名称.txt-读取用户信息-根据特定的奖项配置来进行抽奖data_list=[("三等奖"，5，"空气净化器"),("二等奖"，3，"ipad"), ("一等奖"，2，"iphone13"),......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99