数据结构二叉树的应用

骑猪看日落 2022-08-21 08:46 127阅读 0赞

1、二叉树相似性判断。

试设计算法，判断两棵二叉树是否相似。所谓二叉树t1与t2相似，指的是t1和t2都是空的二叉树；或者t1的左子树与t2的左子树相似，同时t1的右子树与t2的右子树相似。

2、求从二叉树根节点到r节点之间的路径。

假设二叉树采用二叉链表方式存储，root指向根节点，r所指节点为任一给定的节点。编写算法，求出从根节点到节点r之间的路径。

3、设二叉树按二叉链表存储，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指在二叉树中不存在子树个数为1的节点。

4、试编写计算二叉树最大宽度的算法。二叉树的最大宽度是指，二叉树所有层中节点个数的最大值。

5、试编写算法交换二叉树的左右子树。设二叉树用二叉链表存储。

代码实现及解释：

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #define Maxsize 100
    #define OK 1
    #define OVERFLOW -2
    #define Size 100
    
    using namespace std;
    
    typedef char CElemType;
    
    typedef struct BiNode
    {
        CElemType data;
        struct BiNode*lchild,*rchild;
    } BiNode,*BiTree;
    
    void CreateBiTree2(BiTree &t)  ///引用实现创建一棵二叉树
    {
        char ch;
        scanf("%c",&ch);
        if(ch==' ')
            t=NULL;
        else
        {
            t=(BiTree)malloc(sizeof(BiNode));
            t->data=ch;
            CreateBiTree2(t->lchild);
            CreateBiTree2(t->rchild);
        }
    }
    
    void PreOrder(BiTree t) ///递归先序遍历一棵二叉树
    {
        if(t!=NULL)
        {
            printf("%c ",t->data);
            PreOrder(t->lchild);
            PreOrder(t->rchild);
        }
    }
    
    int like(BiTree t1,BiTree t2) ///二叉树的相似性判断
    {
        int like1,like2;
        if(t1==NULL && t2==NULL)
        {
            return 1;
        }
        else if(t1==NULL || t2==NULL)
        {
            return 0;
        }
        else
        {
            like1=like(t1->lchild, t2->lchild);
            like2=like(t1->rchild, t2->rchild);
            return (like1&&like2);
        }
    }
    
    int IsNormalTree(BiTree bt) ///判断是否为正则树，待完善算法？？？
    {
        int flag1,flag2;
        if(bt)
        {
            if(bt->lchild && bt->rchild && bt->lchild->data!=' ' && bt->rchild->data!=' ')
            {
                IsNormalTree(bt->lchild);
                IsNormalTree(bt->rchild);
                return 1;
            }
            else if(!bt->lchild&&!bt->rchild)
            {
                return 1;
            }
            else return 0;
        }
    }
    
    
    typedef BiTree ElemType;
    
    typedef struct
    {
        ElemType *base;
        int front;
        int rear;
    } SeqQueue;
    
    int InitQueue(SeqQueue &Q)
    {
        Q.base=(ElemType *)malloc(Maxsize*sizeof(ElemType));
        if(!Q.base)
            exit(OVERFLOW);
        Q.front = Q.rear =0;
        return OK;
    }
    
    int EnQueue(SeqQueue &Q,ElemType e)
    {
        if((Q.rear+1)%Maxsize==Q.front)
        {
            cout<<"Queue Full"<<endl;
            return 0;
        }
        Q.rear = (Q.rear+1)%Maxsize;
        Q.base[Q.rear]=e;
        return 1;
    }
    
    int DeleQueue(SeqQueue &Q,ElemType &e)
    {
        if(Q.front==Q.rear)
        {
            //cout<<"Queue Empty"<<endl;
            return 0;
        }
        Q.front=(Q.front+1)%Maxsize;
        e=Q.base[Q.front];
        return 1;
    }
    
    int Empty(SeqQueue Q)
    {
        if(Q.rear==Q.front)
            return 1;
        else return 0;
    }
    
    int MaxWidth(BiTree tt) ///计算二叉树的最大宽度
    {
        SeqQueue Q;
        BiTree t=tt;
        int maxW=0,num;
        InitQueue(Q);
        if(t==NULL)
            maxW=0;
        else
        {
            EnQueue(Q,t);
            num=1;
            maxW=1;
            while(!Empty(Q))
            {
                for(int i=0; i<=num; i++)
                {
                    DeleQueue(Q,t);
                    if(t->lchild)
                    {
                        EnQueue(Q,t->lchild);
                    }
                    if(t->rchild)
                    {
                        EnQueue(Q,t->rchild);
                    }
                }
                num=(Q.rear-Q.front+Maxsize)%Maxsize;
                if(num>maxW) maxW=num;
            }
        }
        return maxW;
    }
    
    void Exchange(BiTree bt) ///交换二叉树的左右子树
    {
        BiTree p;
        if(bt)
        {
            p=bt->lchild;
            bt->lchild=bt->rchild;
            bt->rchild=p;
            Exchange(bt->lchild);
            Exchange(bt->rchild);
        }
    }
    
    void PasOrderzx(BiTree t,CElemType ch) ///借助于非递归后序遍历算法求任意一节点的所有祖先节点
    {
        int flag=0;
        struct
        {
            BiTree pp;
            int tag;
        }SS[Size];
        int top;
        BiTree p;
        top=0;
        p=t;
        while(p || top>0)
        {
            while(p)
            {
                top++;
                SS[top].tag=0;
                SS[top].pp=p;
                p=p->lchild;
            }
            if(top>0)
            {
                if(SS[top].tag==0)
                {
                    SS[top].tag=1;
                    p=SS[top].pp;
                    p=p->rchild;
                }
                else
                {
                    p=SS[top].pp;
                    if(p->data==ch)
                    {
                        int topp=top;
                        while(topp>0)
                        {
                            cout<<SS[topp].pp->data<<" ";
                            topp--;
                        }
                        flag=1;
                        break;
                    }
                    top--;
                    p=NULL;
                }
                if(flag==1)
                    break;
            }
            if(flag==1)
                break;
        }
    }
    
    int main()
    {
        BiTree t1,t2;
        cout<<"Please Input The First BiTree :"<<endl;
        CreateBiTree2(t1);
        getchar();
        cout<<"Please Input The Second BiTree :"<<endl;
        CreateBiTree2(t2);
        int l=like(t1,t2);
        if(l)
            cout<<"LIKE!"<<endl;
        else cout<<"DISLIKE!"<<endl;
    
    ///    int z=IsNormalTree(t1);
    ///   if(z)
    ///        cout<<"Zhengze Tree!"<<endl;
    ///    else
    ///        cout<<"Not Zhengze Tree!"<<endl;
    
        int w=MaxWidth(t1);
        cout<<"The greatest BiTree's Width Is: "<<w<<"  "<<endl;
        Exchange(t1);
        cout<<"After Exchange: "<<endl;
        PreOrder(t1);
        cout<<endl;
        cout<<"Please Input a Word:"<<endl;
        char Ch;
        scanf(" %c",&Ch);
        cout<<"The Zuxian of 'Ch':"<<endl;
        PasOrderzx(t1,Ch);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，127人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构-树、二叉树

一、概念 1、树的概念 ![a2c54e1c3956460cb4b78e8a78646577.png][] 树是一种非线性的数据结构，它是由n(n>=0)个有限结

快来打我*/ 2023年10月13日 10:04/ 0 赞/ 38 阅读

相关数据结构实验+二叉树的应用

二叉树的应用 include<stdio.h> //5-1二叉链表的存储结构定义 typedef struct BiTNode

╰半橙微兮°/ 2022年11月05日 14:52/ 0 赞/ 99 阅读

相关数据结构二叉树的应用

1、二叉树相似性判断。试设计算法，判断两棵二叉树是否相似。所谓二叉树t1与t2相似，指的是t1和t2都是空的二叉树；或者t1的左子树与t2的左子树相似，同时t1的右子树与t

骑猪看日落/ 2022年08月21日 08:46/ 0 赞/ 128 阅读

相关 Java数据结构-树的应用-二叉查找树

二叉查找树也叫二叉排序树。对于树中的每个节点X，它的所有左子树中项的值小于X节点中的项，所有右子树中的项的值大于X的项。需要实现的基本操作有： 1.包含：

痛定思痛。/ 2022年08月03日 00:52/ 0 赞/ 152 阅读

相关二叉树的应用详解 - 数据结构

概述： -------------------- 1、排序树——特点：所有结点“左小右大 2、平衡树——特点：所有结点左右子树深度差≤1 3、红黑树——特

亦凉/ 2022年06月10日 02:12/ 0 赞/ 216 阅读

相关二叉树应用_树的子结构

题目：输入两棵二叉树A和B，判断B是不是A的子结构（空树不是任一树的子结构）。分析：要想查找树A中是否存在和树B一样的结构，我们可以分成两步： 1、在树A中找到和树B

心已赠人/ 2022年05月22日 02:40/ 0 赞/ 125 阅读

相关数据结构--二叉树

数据结构--二叉树 [文章转自：https://blog.csdn.net/zxm317122667/article/details/85017317][https_bl

一时失言乱红尘/ 2022年04月10日 10:50/ 0 赞/ 337 阅读

相关数据结构 | 二叉树

树和二叉树：这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用（

蔚落/ 2021年11月29日 07:06/ 0 赞/ 408 阅读

相关数据结构——二叉树

文章目录前言参考博客前言树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。本篇博客将介绍一般二叉树、完全二叉树、满二叉树、线索二叉树、霍

àì夳堔傛蜴生んèń/ 2021年11月05日 07:02/ 0 赞/ 338 阅读

相关数据结构:二叉树

一.简介 struct TreeNode{ int val; TreeNode left; TreeN

短命女/ 2021年10月23日 07:19/ 0 赞/ 319 阅读