欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

c++二叉树的各种操作

程序员文章站 2022-06-24 20:40:44
头文件   #ifndef _binarytree_h_ #define _binarytree_h_ const int maxsize = 100; template...

头文件

 

#ifndef _binarytree_h_
#define _binarytree_h_

const int maxsize = 100;

template
struct btnode
{
    t data;
    btnode *lchild;
    btnode *rchild;
};

template
class binarytree
{
public:
    binarytree();                   //构造函数
    ~binarytree();                  //析构函数
    void preorder(){preorder(r);}   //递归前序遍历
    void inorder(){inorder(r);}     //递归中序遍历
    void postorder(){postorder1(r);} //递归后序遍历
    void preorder1(){preorder1(r);}   //非递归前序遍历
    void inorder1(){inorder1(r);}     //非递归中序遍历
    void postorder1(){postorder(r);} //非递归后序遍历
    void levelorder(){levelorder(r);}//层序遍历
    btnode* findnode(t x){findnode(r,x);}//查找结点
    int btnodeheigth(){btnodeheigth(r);}//树的高度
    int nodecount1(){nodecount1(r);}    //基于前序遍历求结点个数
    int nodecount2(){nodecount2(r);}    //基于中序遍历求结点个数
    int nodecount3(){nodecount3(r);}    //基于后序遍历求结点个数
    int nodecount4(){nodecount4(r);}    //递归求结点个数
    void displeaf(){displeaf(r);}       //输出树的叶子结点
    void printroutelength(){printleavesdepth(r, 0);}//输出树的叶子结点到根结点的路径长度
    bool printancestor(t x){printancestor(r,x);}    //输出值为x的结点的祖先结点
private:
    btnode *r;
    btnode* createtree(btnode *t);//构造函数调用
    void destroytree(btnode *t);     //析构函数调用
    void preorder(btnode *t);        //递归前序遍历调用
    void inorder(btnode *t);         //递归中序遍历调用
    void postorder(btnode *t);       //递归后序遍历调用
    void preorder1(btnode *t);        //非递归前序遍历调用
    void inorder1(btnode *t);         //非递归中序遍历调用
    void postorder1(btnode *t);       //非递归后序遍历调用
    void levelorder(btnode *t);       //层序遍历调用
    btnode* findnode(btnode *t, t x);
    int btnodeheigth(btnode *t);
    int nodecount1(btnode *t);       //前序遍历求结点个数调用
    int nodecount2(btnode *t);       //中序遍历求结点个数调用
    int nodecount3(btnode *t);       //后序遍历求结点个数调用
    int nodecount4(btnode *t);       //递归求结点个数调用
    void displeaf(btnode *t);
    void printleavesdepth(btnode *t,int depth);
    bool printancestor(btnode *t,t x);
};
//
template
binarytree::binarytree()
{
    r = createtree(r);
}
//
template
binarytree::~binarytree()
{
    destroytree(r);
}
//
template
void binarytree::destroytree(btnode *t)
{
    if(t != null)
    {
        destroytree(t->lchild);
        destroytree(t->rchild);
        delete t;
    }
}
//
template
btnode* binarytree::createtree(btnode *t)
{
    t ch;
    std::cin>>ch;
    if(ch == '#')
    {
        t = null;
    }
    else
    {
        t = new btnode;
        t->data = ch;
        t->lchild = createtree(t->lchild);
        t->rchild = createtree(t->rchild);
    }
    return t;
}
//
template
void binarytree::preorder(btnode *t)
{
    if(t != null)
    {
        std::cout<data<<"  ";
        preorder(t->lchild);
        preorder(t->rchild);
    }
}
//
template
void binarytree::inorder(btnode *t)
{
    if(t != null)
    {
        inorder(t->lchild);
        std::cout<data<<"  ";
        inorder(t->rchild);
    }
}
//
template
void binarytree::postorder(btnode *t)
{
    if(t != null)
    {
        postorder(t->lchild);
        postorder(t->rchild);
        std::cout<data<<"  ";
    }
}
//
template
btnode* binarytree::findnode(btnode *t,t x)
{
    btnode *p;
    if(t == null)
    {
        return null;
    }
    else if(t->data == x)
    {
        return t;
    }
    else
    {
        p = findnode(t->lchild,x);
        if(p != null)
        {
            return p;
        }
        return findnode(t->rchild,x);
    }
}
//
template
int binarytree::btnodeheigth(btnode *t)
{
    int lchildh,rchildh;
    if(t == null)
    {
        return 0;
    }
    else
    {
        lchildh = btnodeheigth(t->lchild);
        rchildh = btnodeheigth(t->rchild);
        return (lchildh > rchildh)?(lchildh + 1):(rchildh + 1);
    }
}
//
template
int binarytree::nodecount4(btnode *t)
{
    if(t == null)
    {
        return 0;
    }
    else
    {
        return (nodecount4(t->lchild) + nodecount4(t->rchild) + 1);
    }
}
//
template
int binarytree::nodecount1(btnode *t)
{
    int m,n,k;
    if(t != null)
    {
        m = nodecount1(t->lchild);
        k = 1;
        n = nodecount1(t->rchild);
        return m + n + k;
    }
    return 0;
}
//
template
int binarytree::nodecount2(btnode *t)
{
    int m,n,k;
    if(t != null)
    {
        m = nodecount2(t->lchild);
        n = nodecount2(t->rchild);
        k = 1;
        return m + n + k;
    }
    return 0;
}
//
template
int binarytree::nodecount3(btnode *t)
{
    int m,n,k;
    if(t != null)
    {
        k = 1;
        m = nodecount3(t->lchild);
        n = nodecount3(t->rchild);
        return m + n + k;
    }
    return 0;
}
//
template
void binarytree::displeaf(btnode *t)
{
    if(t != null)
    {
        if((t->lchild == null)&&(t->rchild == null))
        {
            std::cout<data<<"  ";
        }
        displeaf(t->lchild);
        displeaf(t->rchild);
    }
}
//
template
//输出路径长度
void binarytree::printleavesdepth(btnode *t, int depth)
{
  if (t == null) return;
  if (t->lchild == null && t->rchild == null)
  {
    std::cout<data<<": "<lchild, depth+1);
    printleavesdepth(t->rchild, depth+1);
  }
}
//
template
bool binarytree::printancestor(btnode *t, t x)
{
    if(t == null)
    {
        return false;
    }
    if((t->lchild != null)&&(t->lchild->data == x))
    {
        std::cout<data<<"  ";
        return true;
    }
    if((t->rchild != null)&&(t->rchild->data == x))
    {
        std::cout<data<<"  ";
        return true;
    }
    if((printancestor(t->lchild,x))||(printancestor(t->rchild,x)))
    {
        std::cout<data<<"  ";
        return true;
    }
    return false;
}
//
template
void binarytree::preorder1(btnode *t)
{
    btnode *st[maxsize];
    int top = -1;
    btnode *p;
    top++;
    st[top] = t;                //将根结点入栈
    while(top != -1)            //栈非空
    {
        p = st[top];
        top--;
        std::cout<data<<"  ";
        if(p->rchild != null)   //右孩子先进栈
        {
            top++;
            st[top] = p->rchild;
        }
        if(p->lchild != null)   //左孩子再进栈
        {
            top++;
            st[top] = p->lchild;
        }
    }
}
//中序遍历非递归算法
template
void binarytree::inorder1(btnode *t)
{
    btnode *st[maxsize];
    btnode *p;
    int top = -1;
    p = t;
    while((top != -1)||(p!=null))   //栈不空或p不为空时
    {
        while(p != null)            //扫描所有左结点并进栈
        {
            top++;
            st[top] = p;
            p = p->lchild;
        }
        if(top > -1)                //若栈不为空
        {
            p = st[top];
            top--;
            std::cout<data<<"  ";
            p = p->rchild;          //转向处理右子树
        }
    }
}
//
template
void binarytree::postorder1(btnode *t)
{
    btnode *st[maxsize],*p,*q;
    p = t;
    int top = -1;
    bool flag;
    do
    {
        while(p != null)        //将p结点及所有的左下结点进栈
        {
            top++;
            st[top] = p;
            p = p->lchild;
        }
        q = null;              //q指向栈顶结点的前一个已经访问的结点
        flag =true;              //表示p结点的左子树已经遍历完
        while((top != -1)&&(flag == true))//若p结点及其右子树已访问或为空
        {
            p = st[top];
            if(p->rchild == q)
            {
                std::cout<data<<"  ";
                top--;
                q = p;
            }
            else
            {
                p = p->rchild;
                flag = false;
            }
        }
    }
    while(top != -1);
}
//
template
void binarytree::levelorder(btnode *t)
{
    btnode *qu[maxsize],*p;
    int front = 0, rear = 0;
    rear++;
    qu[rear] = t;
    while(front != rear)    //队列不为空
    {
        front = (front + 1) % maxsize;
        p = qu[front];
        std::cout<data<<"  ";
        if(p->lchild != null)
        {
            rear = (rear + 1) % maxsize;
            qu[rear] = p->lchild;
        }
        if(p->rchild != null)
        {
            rear = (rear + 1) % maxsize;
            qu[rear] = p->rchild;
        }
    }
}
#endif // _binaryree_h_

源文件

 

 

#include 
#include "binarytree.h"

using namespace std;

int main()
{
    binarytree a;

    cout<<"前序遍历:  ";
    a.preorder();
    cout<