用c++实现二叉树及堆的数据结构

时间：2021-11-06 10:34:17

数据结构第二个实验要求能成功演示二叉树的有关运算，运算完毕后能成功释放二叉树所有结点占用的系统内存。其中构造二叉树修改二叉树，构造指定顺序的二叉树是本实验的重点与难点。

BTNode.h

#include<iostream>
using namespace std;

template <class T>
struct BTNode
{
T element;
    BTNode<T> *lchild;
    BTNode<T> *rchild;

    BTNode(const T &x)
    {
        element=x;
        lchild=rchild=NULL;
    }
    BTNode(const T &x,BTNode<T> *L,BTNode<T> *r)
    {
        element=x;
        lchild=L;
        rchild=r;
    }
};

BinaryTree.h

#include "BTNode.h"



template <class T>
class BinaryTree
{
 private:
 void PreOrder(void (*Visit)(T &x),BTNode<T>* t);
 void InOrder(void (*Visit)(T &x),BTNode<T>* t);
 void PostOrder(void (*Visit)(T &x),BTNode<T>* t);
 protected:
BTNode<T> *root;
 public:
 int count;
BinaryTree(){root=NULL; count=0;}
 ~BinaryTree(){}
 bool Root(T &x);
 void MakeTree(const T &x,BinaryTree<T> &left,BinaryTree<T> &right);
 void BreakTree(T &x,BinaryTree<T> &left,BinaryTree<T> &right);
 void PreOrder(void (*Visit)(T &x));
 void InOrder(void (*Visit)(T &x));
 void PostOrder(void (*Visit)(T &x));
};

template <class T>
void Visit(T &x)
{
 cout<<x<<" ";
}


template <class T>
bool BinaryTree<T>::Root(T &x)
{
 if(root)
 {
 x=root->element;
 return true;
 }
 else
 {
 return false;
 }
}


template <class T>
void BinaryTree<T>::MakeTree(const T &x,BinaryTree<T> &left,BinaryTree<T> &right)
{
 if(root||&left==&right) return;
 root=new BTNode<T>(x,left.root,right.root);
 left.root=right.root=NULL;
}

template <class T>
void BinaryTree<T>::BreakTree(T &x,BinaryTree<T> &left,BinaryTree<T> &right)
{
 if(!root||&left==&right||left.root||right.root) return;
 x=root->element;
 left.root=root->lchild;
 right.root=root->rchild;
 delete root;
 root=NULL;
}


template <class T>
void BinaryTree<T>::PreOrder(void (*Visit)(T &x))
{
PreOrder(Visit,root);
}

template <class T>
void BinaryTree<T>::InOrder(void (*Visit)(T &x))
{
InOrder(Visit,root);
}

template <class T>
void BinaryTree<T>::PostOrder(void (*Visit)(T &x))
{
PostOrder(Visit,root);
}

template <class T>
void BinaryTree<T>::PreOrder(void (*Visit)(T &x),BTNode<T>* t)
{
 if(t)
 {
Visit(t->element);
PreOrder(Visit,t->lchild);
PreOrder(Visit,t->rchild);
 count++;
 }
}

template <class T>
void BinaryTree<T>::InOrder(void (*Visit)(T &x),BTNode<T>* t)
{
 if(t)
 {
InOrder(Visit,t->lchild);
Visit(t->element);
InOrder(Visit,t->rchild);
 count++;
 }
}

template <class T>
void BinaryTree<T>::PostOrder(void (*Visit)(T &x),BTNode<T>* t)
{
 if(t)
 {
PostOrder(Visit,t->lchild);
PostOrder(Visit,t->rchild);
Visit(t->element);
 count++;
 }
}

main.cpp

#include "BinaryTree.h"


void main(void)
{
    BinaryTree<char> a,b,x,y,z;
//  char e;
y.MakeTree('E',a,b);
z.MakeTree('F',a,b);
x.MakeTree('C',y,z);
y.MakeTree('D',a,b);
z.MakeTree('B',y,x);
//  z.BreakTree(e,y,x);
z.PreOrder(Visit);
    cout<<' '<<z.count;
    cout<<endl;
z.count=0;
z.InOrder(Visit);
    cout<<endl;
z.count=0;
z.PostOrder(Visit);
    cout<<endl;
z.count=0;
}

以上实现了基本的树的构造，观察代码调试运行可以较深入的理解二叉树的构造原理

下面是特殊的树结构，这类树结构会为后面构造哈夫曼树打下基础

1.构造优先权队列样例源码

#include <iostream>
using namespace std;

template <class T>
class PrioQueue
{
    public:
        PrioQueue(int mSize=20);
        ~PrioQueue(){delete []q;};
        bool IsEmpty()const{return n==0;}
        bool IsFull()const{return n==maxSize;}
        void Append(T &x);
        void show();
    private:
        void AdjustUp(int j);
        T *q;
int n,maxSize;
};

template <class T>
PrioQueue<T>::PrioQueue(int mSize)
{
    maxSize=mSize;
    n=0;
q=new T[maxSize];
}

template <class T>
void PrioQueue<T>::AdjustUp(int j)
{
int i=j;
    T temp=q[i];
while(i>0 && temp<q[(i-1)/2])
    {
q[i]=q[(i-1)/2];
        i=(i-1)/2;
    }
q[i]=temp;
}

template <class T>
void PrioQueue<T>::Append(T &x)
{
q[n++]=x;
    AdjustUp(n-1);
}

template <class T>
void PrioQueue<T>::show()
{
for(int i=0;i<8;i++)
    {
        cout<<q[i]<<' ';
    }
    cout<<endl;
}

优先权队列测试main源码

#include "PrioQueue.h"
enum ResultCode{Overflow};

void main()
{
    PrioQueue<int> q1(8);
while(q1.IsFull()==0)
    {
int x;
cout<<"plz input an element"<<endl;
cin>>x;
    q1.Append(x);
    }
    q1.show();
}

2.堆的构造样例源码

#include <iostream>
using namespace std;

template <class T>
void adjustdown(T heap[],int r,int j)
{
int child=2*r+1;
    T temp=heap[r];
while(child<=j)
    {
if( (child<j) && (heap[child]>heap[child+1]))
        {
            child++;
        }
if(temp<=heap[child])
        {
break;
        }
        heap[(child-1)/2]=heap[child];
        child=child*2+1;
    }
    heap[(child-1)/2]=temp;
}

template <class T>
void createheap(T heap[],int n)
{
for(int i=(n-2)/2;i>-1;i--)
    {
        adjustdown(heap,i,n-1);
    }
}

void main()
{
int heap[8]={61,28,81,43,36,47,83,5};
    createheap(heap,8);
for(int i=0;i<8;i++)
    {
cout<<heap[i]<<' ';
    }
cout<<endl;
}
标签：

相关文章