首页 / 算法 / c++实验7 二叉树

c++实验7 二叉树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了c++实验7 二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6693字，纯文字阅读大概需要10分钟。

内容图文

二叉树数据结构表示及基本操作算法实现

1、所加载的库函数或常量定义及类的定义：

#include<stdlib.h>
#include<stdio.h>
#include"BiTreeNode.h"
#include<iostream>
usingnamespace std;
template <class T>
class BiTree
{
private:
    BiTreeNode<T> *root;            //根结点指针void Destroy(BiTreeNode<T>* &t);


    void InOrder(BiTreeNode<T> *&t, void (*Visit)(T item));
    void PostOrder(BiTreeNode<T>* &t, void (*Visit)(T item));
public:
    BiTree(void):root(NULL){};                 //构造函数
    ~BiTree(void){};                         //析构函数void PreOrder(BiTreeNode<T>* &t, void (*Visit)(T item));
    //构造二叉树void MakeTree(const T item, BiTree<T> &left, BiTree<T> &right);
    void Destroy(void);            //撤消二叉树
    BiTreeNode<T> *getroot()
    {
        return root;
    }
    void PreOrder(void (*Visit)(T item));        //前序遍历void InOrder(void (*Visit)(T item));        //中序遍历void PostOrder(void (*Visit)(T item));        //后序遍历
    BiTreeNode<T> *createbintree();             //前序遍历建立二叉树int numofnode(BiTreeNode<T> *t);            //二叉树结点个数void showmid(BiTreeNode<T> *t);             //按中序遍历所有子节点值
    BiTreeNode<T> *LeverCreateTree(BiTreeNode<T> *tr);//按层次遍历-非递归创建二叉树
    BiTreeNode<T> *GetTreeNode(const T item, BiTreeNode<T> *left=NULL, BiTreeNode<T> *right=NULL)
    {
        BiTreeNode<T> *p;
        p = new BiTreeNode<T> (item, left, right);
        return p;
    }
    int leafnode(BiTreeNode<T> *t);      //二叉树叶子节点个数
};

 

2、二叉树存储结构定义：链式存储

结点类：

template <class T>
class BiTreeNode
{
public:
    BiTreeNode<T> *leftChild;                        //左子树指针
    BiTreeNode<T> *rightChild;                        //右子树指针
    T data;                                            //数据域

    //构造函数和析构函数    BiTreeNode():leftChild(NULL), rightChild(NULL){}
    BiTreeNode(T item, BiTreeNode<T> *left = NULL, BiTreeNode<T> *right = NULL):
        data(item), leftChild(left), rightChild(right){}
    ~BiTreeNode(){}

    BiTreeNode<T>* &Left(void)    //注意返回值类型为指针的引用类型
        {return leftChild;}
    BiTreeNode<T>* &Right(void)    //注意返回值类型为指针的引用类型
        {return rightChild;}
    BiTreeNode<T>* setleft(){}

};

 3、二叉树递归遍历算法（3种）

注：已知树的根结点 和测试文件中增加visit函数 得到按三种树的序遍历（起到显示结点值作用-并不好用【第4题种自行定义了showmid函数按中序显示】）

1）     先序递归遍历

template <class T>
void BiTree<T>::PreOrder(BiTreeNode<T> *&t, void (*Visit)(T item))
//使用Visit(item)函数前序遍历二叉树t{
    if(t != NULL)
    {
        Visit(t->data);   //根
        PreOrder(t->Left(), Visit);  //左子树
        PreOrder(t->Right(), Visit); //右子树    }
}

2）     中序递归遍历

template <class T>
void BiTree<T>::InOrder(BiTreeNode<T> *&t, void (*Visit)(T item))
//使用Visit(item)函数中序遍历二叉树t{
    if(t != NULL)
    {
        InOrder(t->Left(), Visit); //左子树
        Visit(t->data); //根
        InOrder(t->Right(), Visit); //右子树    }
}

3）     后序递归遍历

template <class T>
void BiTree<T>::PostOrder(BiTreeNode<T> *&t, void (*Visit)(T item))
//使用Visit(item)函数后序遍历二叉树t{
    if(t != NULL)
    {
        PostOrder(t->Left(), Visit); //左子树
        PostOrder(t->Right(), Visit); //右子树
        Visit(t->data); //根    }
}

 

 测试数据：

#include <iostream>
#include<stdlib.h>
#include"BiTree.h"usingnamespace std;
template <class T>
void Visit(T item)
{
    cout << item << "";
}
int main()
{
    BiTree<char>a,b,c,d,e,f,g,null;
    g.MakeTree(‘G‘,null,null);
    d.MakeTree(‘D‘,null,g);
    b.MakeTree(‘B‘,d,null);
    e.MakeTree(‘E‘,null,null);
    f.MakeTree(‘F‘,null,null);
    c.MakeTree(‘C‘,e,f);
    a.MakeTree(‘A‘,b,c);
    cout<<"先序遍历:";
    a.PreOrder(Visit);
    cout<<"\n中序遍历:";
    a.InOrder(Visit);
    cout<<"\n后序遍历:";
    a.PostOrder(Visit);
    return0;
}

 结果：

技术分享图片

4、二叉树创建递归算法-选用（前序）遍历实现二叉树创建的递归算法

注：按先序遍历创建二叉树（#为空结点） 

template <class T>
BiTreeNode<T> * BiTree<T>:: createbintree()
{ /*按照前序遍历的顺序建立一棵给定的二叉树*/char ch;
    BiTreeNode<T> * t;
    if ((ch=getchar())==‘#‘)
        t=NULL;
    else
        {
            t = new BiTreeNode<T>;
            t->data=ch;
            t->leftChild=createbintree();
            t->rightChild=createbintree();
        }

    return t;
}
template <class T>
void BiTree<T>::showmid(BiTreeNode<T> *t)
{
    if(t!=NULL&&t->leftChild!=NULL)
        showmid(t->leftChild);
    cout<<t->data<<"";
    if(t!=NULL&&t->rightChild!=NULL)
        showmid(t->rightChild);
}

———— 其中增加showmid方法 显示给出结点下所有结点的值（按中序排列）

 

测试数据：

            int
             main()
{
      BiTree<char> a;
    cout<<"先序建立二叉树序列是（#为叶子节点）： ";
    BiTreeNode<char> * b= a.createbintree();
    cout<<"中序遍历:";
    a.showmid(b);
    return0;
}

 结果

技术分享图片

 

5、按层次遍历写出二叉树创建的非递归算法

注：已知树的根结点 按层输入二叉树（即按满树从上到下从左到右输入各结点值 #表示空结点 @为结束标志）
 

template<class T>
BiTreeNode<T> *BiTree<T>::LeverCreateTree(BiTreeNode<T> *tr)//按层次遍历-非递归创建二叉树
//输入序列：扩展结点度为2{
    BiTreeNode<T> *q[10],*p,*k;//q为队列，int f=0,w=0,n=0;//f表示队头，w表示队尾。n为计数器char ch;
    cin>>ch;
    if (ch==‘#‘||ch==‘@‘) tr=NULL;//空树时else{//1
            tr=new BiTreeNode<T>;//二叉树根结点的创建
            tr->data=ch;
            tr->leftChild=NULL;//99
            tr->rightChild=NULL;//99
            q[w++]=tr;
            cin>>ch;
            while(ch!=‘@‘)
            {
                n=n%2;
                if (ch!=‘#‘)
                {
                    p=new BiTreeNode<T>;
                    p->data=ch;
                    p->leftChild=NULL;
                    p->rightChild=NULL;
                    q[w++]=p;
                }
                else
                {p=NULL;}
                n++;
                if (n==1)
                    {k=q[f];k->leftChild=p;}
                elseif(n==2)
                    {k=q[f++];k->rightChild=p;}
                cin>>ch;
            }//while
        }//1return tr;
}//LeverCreateTree

 

 测试数据

            int
             main()
{
    BiTree<char> A;
    BiTreeNode<char>* b;
    cout<<"请按层次输入二叉树(@结尾)"<<endl;
    BiTreeNode<char>* c=A.LeverCreateTree(b);
    cout<<"按中序遍历输出：";
    A.showmid(c);
    return0;
}

 结果：

1）空树

 技术分享图片

2）仅有一个结点树

技术分享图片

3）一般的普通的二叉树

技术分享图片

4）给出数据输入的序列。

 技术分享图片

试分析，上列算法的基本算法思想，试问//99这句没有，数据的输入序列应如何？

去掉//99语句后：

　　理论上必须输入序列至少2层（1层即只有根结点）否则下方的左右子树不明确

　　但实际试验后没区别！！　　

若有个人思路见解望请留言指正

 

6、求二叉树的深度递归算法

注：已知树的根结点 得到二叉树深度 

template <class T> //二叉树的深度方法int PostTreeDepth(BiTreeNode<T> *t)
{
    int hl=0,hr=0;
    if (t==NULL)      return0;
    hl=PostTreeDepth(t->Left());
    hr=PostTreeDepth(t->Right());
   if (hl>hr)
       return (hl+1);
   elsereturn (hr+1);
}

 

7、求二叉树的结点数递归算法

注：已知树的根结点 得到二叉树结点个数 

template <class T>
int BiTree<T>::numofnode(BiTreeNode<T> *t)  //二叉树结点个数{
    if (t==NULL)
        return0;    //递归出口elsereturn( numofnode(t->leftChild)+numofnode(t->rightChild) + 1);
}

 

 

8、求二叉树的叶子数递归算法

注：已知树的根结点 得到二叉树叶子节点个数

template <class T>
int BiTree<T>::leafnode(BiTreeNode<T> *t)//二叉树叶子节点个数{
    if(t==NULL)
        return0;    //递归出口elseif (t->leftChild==NULL && t->rightChild==NULL)
        return1;    //递归出口elsereturn(leafnode(t->leftChild)+leafnode(t->rightChild));
}

 

 此处对上面3问进行测试

技术分享图片

9、求两颗二叉树的相似

递归算法提示：

1）若T1和T2均为空，则返回值为1；

2）若T1和T2的深度均为1（即只有一个结点），则返回为1；

3）若T1的左子树和T2的左子树相似，并且T1的右子树和T2的右子树相似，则返回为1;

4)其它为返回值为0；

注：已知2个根节点 得到是否两树相似 （该段不写于BiTree类中）

template <class T>
int islike(BiTreeNode<T> * t1,  BiTreeNode<T> * t2)
{
    int t=0;
    if(t1==NULL && t2==NULL)
        t=1;
    elseif(PostTreeDepth(t1)==PostTreeDepth(t2)&&PostTreeDepth(t1)==1)
        t=1;
    elseif((islike(t1->leftChild,t2->leftChild)==1)&&(islike(t1->rightChild,t2->rightChild)==1))
        t=1;
    else
        t=0;
    return t;
}

 

 测试结果：

技术分享图片

 

 

 

 

 

 

 

 

 

8

原文：https://www.cnblogs.com/cc123nice/p/10801717.html

内容总结

以上是互联网集市为您收集整理的c++实验7 二叉树全部内容，希望文章能够帮你解决c++实验7 二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1106877.html

来源：【匿名】