首页 > 其他分享 >【锐格】数据结构-实验-二叉树

【锐格】数据结构-实验-二叉树

时间：2023-06-07 14:07:25浏览次数：44  
标签：lchild ch return int NULL 锐格 二叉树 rchild 数据结构


7075

#include<iostream>
#include<cstdio>

using namespace std;

typedef struct TNode{
    char data;
    struct TNode *lchild, *rchild;
}BiNode, *BiTree;
BiTree T;

void createTree(BiTree &T)
{

    char ch;
    cin>>ch;
    if(ch=='@') T=NULL;
    else
    {
        T=new TNode;
        T->data=ch;
        createTree(T->lchild);
        createTree(T->rchild);
    }
}

void printTree_back(BiTree &T)
{
    if(T)
    {
        printTree_back(T->lchild);
        printTree_back(T->rchild);
        cout<<T->data;
    }
}

int main()
{
    createTree(T);
    printTree_back(T);
    return 0;
}

7078(线索二叉树，中序遍历)

#include <iostream>
#include<cstdio>

using namespace std;

typedef struct BThrNode{
    char data;
    struct BThrNode *lchild, *rchild;
    int ltag, rtag;
}BThrNode, *BThrTree;

BThrTree T,p;

void createBTree(BThrTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='@') T=NULL;
    else
    {
        T=new BThrNode;
        T->data=ch;
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}
BThrTree pre=NULL;

void InThread(BThrTree p)
{
    if(p!=NULL)
    {
        InThread(p->lchild);
        if(p->lchild==NULL){p->ltag=1; p->lchild=pre;}
        else p->ltag=0;
        if(p->rchild==NULL){p->rtag=1; pre->rchild=p;}
        else pre->rtag=0;
        pre=p;
        InThread(p->rchild);
    }
}

void TraveBTree(BThrTree &T)
{
    if(T)
    {
        TraveBTree(T->lchild);
        cout<<T->data;
        TraveBTree(T->rchild);
    }
}
int main()
{
    createBTree(T);
    InThread(p);
    TraveBTree(T);
    return 0;
}

7079（中序遍历）

#include <iostream>
#include<cstdio>

using namespace std;

typedef struct BTNode{
    char data;
    struct BTNode *lchild, *rchild;
    //int ltag, rtag;
}BTNode, *BTree;

BTree T;

void createBTree(BTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='@') T=NULL;
    else
    {
        T=new BTNode;
        T->data=ch;
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}

//void InThread(BThrTree p)
//{
//    if(p!=NULL)
//    {
//        InThread(p->lchild);
//        if(p->lchild==NULL){p->ltag=1; p->lchild=pre;}
//        else p->ltag=0;
//        if(p->rchild==NULL){p->rtag=1; pre->rchild=p;}
//        else pre->rtag=0;
//        pre=p;
//        InThread(p->rchild);
//    }
//}

void TraveBTree(BTree &T)
{
    if(T)
    {
        TraveBTree(T->lchild);
        cout<<T->data;
        TraveBTree(T->rchild);
    }
}
int main()
{
    createBTree(T);
    TraveBTree(T);
    return 0;
}

7077（层次遍历）

#include <iostream>
#include<cstdio>
#include <queue>

using namespace std;

const int MAX_SIZE=1010;

typedef struct BTNode{
    char data;
    struct BTNode *lchild, *rchild;
    //int ltag, rtag;
}BTNode, *BTree;

typedef struct {
    BTNode data[MAX_SIZE];
    int front,rear;
}SQ;
BTree T;

void createBTree(BTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='@') T=NULL;
    else
    {
        T=new BTNode;
        T->data=ch;
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}

//void InThread(BThrTree p)
//{
//    if(p!=NULL)
//    {
//        InThread(p->lchild);
//        if(p->lchild==NULL){p->ltag=1; p->lchild=pre;}
//        else p->ltag=0;
//        if(p->rchild==NULL){p->rtag=1; pre->rchild=p;}
//        else pre->rtag=0;
//        pre=p;
//        InThread(p->rchild);
//    }
//}

void TraveBTree(BTree &T)
{
    BTree p;
    queue<BTree> Q;
    if(T)
    {
        Q.push(T);
        while (!Q.empty())
        {
            p=Q.front();
            cout<<p->data;
            Q.pop();
            if(p->lchild)   Q.push(p->lchild);
            if(p->rchild)   Q.push(p->rchild);
        }
    }
}
int main()
{
    createBTree(T);
    TraveBTree(T);
    return 0;
}

7076

#include<iostream>
#include<cstdio>

using namespace std;

typedef struct BTNode{
    char data;
    struct BTNode *lchild, *rchild;
}BTNode, *BTree;
BTree T;

void createBTree(BTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='@') T=NULL;
    else
    {
        T=new BTNode;
        T->data=ch;
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}

int Trave(BTree T)
{
    //int num=0;
    if(!T)  return 0;
    else
    {
        if(T->lchild==NULL && T->rchild==NULL)  return 1;
        else return Trave(T->lchild)+ Trave(T->rchild);
    }
    return 0;
}

int main()
{
    createBTree(T);
    int ans= Trave(T);
    cout<<ans<<endl;
    return 0;
}

7074

#include<iostream>
#include<cstdio>

using namespace std;

typedef struct BTNode{
    char data;
    struct BTNode *lchild, *rchild;
}BTNode, *BTree;
BTree T;

void createBTree(BTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='@') T=NULL;
    else
    {
        T=new BTNode;
        T->data=ch;
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}

int Trave(BTree T)
{
    //int num=0;
    if(!T)  return 0;
    else
    {
        if(T->lchild==NULL && T->rchild==NULL)  return 1;
        else return Trave(T->lchild)+ Trave(T->rchild);
    }
    return 0;
}

int Depth(BTree &T)
{
    int m,n;
    if(T==NULL) return  0;
    else
    {
        m= Depth(T->lchild);
        n= Depth(T->rchild);
        if(m>n) return m+1;
        else    return n+1;
    }
}

int main()
{
    createBTree(T);
    int ans= Depth(T);
    cout<<ans<<endl;
    return 0;
}

7080（父亲孩子表示法）

#include<iostream>
#include<cstdio>

using namespace std;

typedef struct BTNode{
    char data;
    struct BTNode *lchild, *rchild;
}BTNode, *BTree;

BTree T;

void createBTree(BTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='@') T=NULL;
    else
    {
        T=new BTNode;
        T->data=ch;
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}

int Trave(BTree T)
{
    //int num=0;
    if(!T)  return 0;
    else
    {
        if(T->lchild==NULL && T->rchild==NULL)  return 1;
        else return Trave(T->lchild)+ Trave(T->rchild);
    }
    return 0;
}

int Depth(BTree &T)
{
    int m,n;
    if(T==NULL) return  0;
    else
    {
        m= Depth(T->lchild);
        n= Depth(T->rchild);
        if(m>n) return m+1;
        else    return n+1;
    }
}

int CountLeaf(BTree &T)
{
    int ans=0;
    if(T==NULL) return 0;
    if(T->lchild==NULL) return CountLeaf(T->rchild)+1;
    else
        return CountLeaf(T->lchild)+ CountLeaf(T->rchild);
}

int main()
{
    createBTree(T);
    //int ans= Depth(T);
    cout<<CountLeaf(T)<<endl;
    return 0;
}

未完待续


标签：lchild,ch,return,int,NULL,锐格,二叉树,rchild,数据结构
From： https://blog.51cto.com/u_15567308/6431253

相关文章

  • 【锐格】数据结构-实验-图
    7039#include<iostream>#include<cstdio>usingnamespacestd;constintMAX_NUM=100;intw;intmark[MAX_NUM];typedefintEdgeData;typedefstructNode{intdest;EdgeDataweight;//边权structNode*next;//nextroute}EdgeNode;......
  • 【NEFU】数据结构阶段二机试代码
    个人拙见，难免有不足之处，望大佬们斧正P1#defineMAXNODE64#include<stdio.h>#include<stdlib.h>typedefstructNode//边的信息{intadjvex;structNode*next;}ArcNode;typedefstructVNode//顶点的信息{intdata;ArcNode*firstarc;}Ve......
  • 【数据结构】图的基本操作
    #include<iostream>#include<cstdio>#include<stack>#include<queue>#include<cstring>constintMAX_SUM=110;usingnamespacestd;typedefstructArcNode{intadj;structArcNode*nextarc;}ArcNode;typedefstruct......
  • 30. 平衡二叉树
    一、什么是平衡二叉树  平衡二叉树（BalanceFactorTree，简称AVL树）是一个特殊的二叉树，它可以是空树。如果不为空，它任一节点左、右子树高度差的绝对值不超过1，即|BF(T)|≤1。其中，BF是指平衡因子（BalanceFactory）：\(BF(T)=h_{L}-h_{R}\)，其中\(h_{L}\)和\(h_{R}\)分别为......
  • 初级数据结构--栈在表达式求值的应用
    表达式一般有三部分组成：操作数、运算符、界限符我们常见的表达式一般都属于中缀表达式，比如：2*2/(1+1)-4/2+1后缀表达式中缀表达式便于人的理解，但不便于计算机的处理。于是便有了后缀表达式，也成逆波兰表达式。比如上面表达式手动转为后缀表达式为22*11+/42/-1+（提一下不常......
  • #yyds干货盘点# LeetCode程序员面试金典：二叉树的右视图
    1.简述：给定一个二叉树的根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 示例1:输入: [1,2,3,null,5,null,4]输出: [1,3,4]示例2:输入: [1,null,3]输出: [1,3]示例3:输入: []输出: []2.代码实现：classSolution{publicList<I......
  • 每日记录(数据结构 第 三 章 栈与队列 二 )
    队列队列是一种先进先出(FIFO)(FIFO)(FIFO)的线性表.在表一端插入,在另一端删除。0.队列的基本概念定义只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表逻辑结构与线性表相同，仍为一对一关系存储结构用顺序队列或链队存储均可运算规则先进先出（FIFO）实现方式......
  • 每日记录(数据结构 第 三 章 栈与队列 )
     一、栈栈（stack）(lastinfirstout)（stack）(last\infirst\out)（stack）(lastinfirstout)后进先出 栈的基本概念定义只能在表的一端（栈顶）进行插入和删除运算的线性表逻辑结构与线性表相同，仍为一对一关系存储结构用顺序栈或链栈存储均可，但以顺序栈更......
  • 数据结构与算法分析（Java语言描述）（14）—— 索引堆
    packagecom.dataStructure.heap;importjava.util.Arrays;publicclassIndexMaxHeap{//最大索引堆中的数据privateInteger[]data;//最大索引堆中的索引privateint[]indexes;privateintcount;privateintcapacity;//构造函数,......
  • 数据结构与算法分析（Java语言描述）（13）—— 原地堆排序
    packagecom.algorithm.sort;publicclassHeapSortInPlace{privateHeapSortInPlace(){}publicstaticvoidsort(Integer[]arr){intn=arr.length;//注意：我们堆的索引是从0开始的//从（最后一个元素的索引-1）/2开始......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99