c++二叉树的各种操作

头文件

 

#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<