V2AS问路
【数据结构】二叉树(c++)
阅读原文时间：2023年07月15日阅读：1

头文件：

#include
using namespace std;

template
class Bintree;

//结点类
template
class BintreeNode
{
friend class Bintree;
public:
BintreeNode() :data(Type()), leftchild(NULL), rightchild(NULL)
{}
BintreeNode(Type d, BintreeNode *l = NULL, BintreeNode *r = NULL) : data(d), leftchild(l), rightchild(r)
{}
private:
BintreeNode *leftchild;
BintreeNode *rightchild;
Type data;
};

//二叉树类
template
class Bintree
{
public:
Bintree() :Ref(Type()), root(NULL)
{}
Bintree(Type re, BintreeNode *r = NULL) : Ref(re), root(r)
{}
~Bintree()
{
Destory();
}
public:
//提供接口
void CreatBintree()
{
Creat(root);
}

void PreOrder()  
{  
    PreOrder(root);  
}

void InOrder()  
{  
    InOrder(root);  
}

void PostOrder()  
{  
    PostOrder(root);  
}

int Height()  
{  
    return Height(root);  
}

int Size()  
{  
    return Size(root);  
}

BintreeNode<Type> \*Search(Type key)  
{  
    return Search(root, key);  
}

BintreeNode<Type> \*PreOrder\_Find(Type key)  
{  
    return PreOrder\_Find(root, key);  
}

BintreeNode<Type> \*InOrder\_Find(Type key)  
{  
    return InOrder\_Find(root, key);  
}

BintreeNode<Type> \*PostOrder\_Find(Type key)  
{  
    return PostOrder\_Find(root, key);  
}

BintreeNode<Type> \*Parent(BintreeNode<Type> \*q)  
{  
    return Parent(root, q);  
}

BintreeNode<Type> \*Leftchild(Type key)  
{  
    return Leftchild(root, key);  
}

BintreeNode<Type> \*Rightchild(Type key)  
{  
    return Rightchild(root, key);  
}

Type Root()  
{  
    return Root(root);  
}

void Destory()  
{  
    return Destory(root);  
}

bool IsEmpty()  
{  
    return IsEmpty(root);  
}

void quit\_system(int &x)  
{  
    x = 0;  
}

protected:
//创建二叉树
void Creat(BintreeNode *&t)
{
Type input;
cin >> input;
if (input == Ref)
{
t = NULL;
}
else
{
t = new BintreeNode(input);
Creat(t->leftchild);
Creat(t->rightchild);
}
}

// 前序遍历  
void PreOrder(const BintreeNode<Type> \*t)  
{  
    if (t == NULL)  
    {  
        return;  
    }  
    else  
    {  
        cout << t->data << "  ";  
        PreOrder(t->leftchild);  
        PreOrder(t->rightchild);  
    }  
}

// 中序遍历  
void InOrder(const BintreeNode<Type> \*t)  
{  
    if (t == NULL)  
    {  
        return;  
    }  
    else  
    {  
        InOrder(t->leftchild);  
        cout << t->data << "  ";  
        InOrder(t->rightchild);  
    }  
}

// 后序遍历  
void PostOrder(const BintreeNode<Type> \*t)  
{  
    if (t == NULL)  
    {  
        return;  
    }  
    else  
    {  
        PostOrder(t->leftchild);  
        PostOrder(t->rightchild);  
        cout << t->data << "  ";  
    }  
}

// 求高度  
int Height(const BintreeNode<Type> \*t)  
{  
    if (t == NULL)  
        return 0;  
    return (Height(t->leftchild) > Height(t->rightchild)) ?

(Height(t->leftchild) + 1) : (Height(t->rightchild) + 1);
}

int Size(const BintreeNode<Type> \*t)  
{  
    if (t == NULL)  
        return 0;  
    return(Size(t->leftchild) + Size(t->rightchild) + 1);  
}

// 查找一个节点返回其地址  
BintreeNode<Type> \*Search( BintreeNode<Type> \*t,const Type key)  
{  
    if (t == NULL)  
    {  
        return NULL;  
    }  
    if (t->data == key)  
        return t;  
    BintreeNode<Type> \*p;  
    if ((p = Search(t->leftchild, key)) != NULL)  
        return p;  
    else  
        return Search(t->rightchild, key);  
}

// 前序查找  
BintreeNode<Type> \*PreOrder\_Find(BintreeNode<Type> \*t, const Type key)  
{  
    if (t == NULL)  
    {  
        return NULL;  
    }  
    if (t->data == key)  
        return t;  
    BintreeNode<Type> \*p;  
    if ((p = PreOrder\_Find(t->leftchild, key)) != NULL)  
         return p;  
    else  
        return PreOrder\_Find(t->rightchild, key);  
}

// 中序查找  
BintreeNode<Type> \*InOrder\_Find(BintreeNode<Type> \*t, const Type key)  
{  
    if (t == NULL)  
    {  
        return NULL;  
    }  
    BintreeNode<Type> \*p;  
    if ((p = InOrder\_Find(t->leftchild, key)) != NULL)  
        return p;  
    else if (t->data == key)  
        return t;  
    else  
        return InOrder\_Find(t->rightchild, key);  
}

// 后序查找  
BintreeNode<Type> \*PostOrder\_Find(BintreeNode<Type> \*t, const Type key)  
{  
    if (t == NULL)  
    {  
        return NULL;  
    }  
    BintreeNode<Type> \*p;  
    BintreeNode<Type> \*q;  
    if ((p = PostOrder\_Find(t->leftchild, key)) != NULL)  
        return p;  
    else if ((q = PostOrder\_Find(t->rightchild, key)) != NULL)  
        return q;  
    else if (t->data = key)  
        return t;  
}

// 求父节点并返回其父节点地址  
BintreeNode<Type> \*Parent(BintreeNode<Type> \*&t, BintreeNode<Type> \*q)  
{  
    if (t == NULL)  
    {  
        return t;  
    }  
    if (q == t->leftchild || q == t->rightchild || q == t)  
    {  
        return t;  
    }  
    BintreeNode<Type> \*p;  
    if ((p = Parent(t->leftchild, q)) != NULL)  
    {  
        return p;  
    }  
    else  
        return Parent(t->rightchild, q);  
}

// 求左孩子  
BintreeNode<Type> \*Leftchild(BintreeNode<Type> \*t, const Type key)  
{  
    BintreeNode<Type> \*p = Search(t, key);  
    if (p == NULL)  
    {  
        cout << "the node is not exist!" << endl;  
        return NULL;  
    }  
    if (p->leftchild == NULL)  
    {  
        cout << "this node not has leftchild" << endl;  
        return NULL;  
    }  
    else  
        return p->leftchild;  
}

// 求右孩子  
BintreeNode<Type> \*Rightchild(BintreeNode<Type> \*t, const Type key)  
{  
    BintreeNode<Type> \*p = Search(t, key);  
    if (p == NULL)  
    {  
        cout << "the node is not exist!" << endl;  
        return NULL;  
    }  
    if (p->rightchild == NULL)  
    {  
        cout << "this node not has rightchild" << endl;  
        return NULL;  
    }  
    else  
        return p->rightchild;  
}

// 求根  
Type Root(const BintreeNode<Type> \*t)  
{  
    return t->data;  
}

void Destory(const BintreeNode<Type> \*t)  
{  
    if (t != NULL)  
    {  
        Destory(t->leftchild);  
        Destory(t->rightchild);  
        delete t;  
    }  
}

// 看树是否为空  
bool IsEmpty(const BintreeNode<Type> \*t)  
{  
    return t == NULL;  
}

private:
BintreeNode *root;
Type Ref;
};

页面设计：

#include "Bintree.h"

int main()
{
Bintree bt('#');
int select = 1;
char c;
while (select)
{
cout << "******************************************************************" << endl; cout << "* [1] creat [2] PreOrder [3] InOrder *" << endl; cout << "* [4] PostOrder [5] Height [6] Size *" << endl; cout << "* [7] search [8] PreOrder_Find [9] InOrder_Find *" << endl; cout << "* [10] PostOrder_Find [11] parent [12] leftchild *" << endl; cout << "* [13] rightchild [14] root [15] destory *" << endl; cout << "* [16] Isempty [17] quit_system *" << endl; cout << "******************************************************************" << endl; cout << "pleae choose:"; cin >> select;
switch (select)
{
case 1:
cout << "please enter:"; bt.CreatBintree(); break; case 2: bt.PreOrder(); cout << endl; break; case 3: bt.InOrder(); cout << endl; break; case 4: bt.PostOrder(); cout << endl; break; case 5: cout << bt.Height() << endl; break; case 6: cout << bt.Size() << endl; break; case 7: cout << "please enter what u want to search:"; cin >> c;
cout << bt.Search(c) << endl; break; case 8: cout << "please enter what u want to search:"; cin >> c;
cout << bt.PreOrder_Find(c) << endl; break; case 9: cout << "please enter what u want to search:"; cin >> c;
cout << bt.InOrder_Find(c) << endl; break; case 10: cout << "please enter what u want to search:"; cin >> c;
cout << bt.PostOrder_Find(c) << endl; break; case 11: cout << "whose parent u wanna find:"; cin >> c;
cout << bt.Parent(bt.Search(c)) << endl; break; case 12: cout << "whose leftchild u wanna find:"; cin >> c;
cout << bt.Leftchild(c) << endl; break; case 13: cout << "whose rightchild u wanna find:"; cin >> c;
cout << bt.Rightchild(c) << endl;
break;
case 14:
cout << bt.Root() << endl;
break;
case 15:
bt.Destory();
break;
case 16:
if (bt.IsEmpty())
{
cout << "it is an empty bintree" << endl;
}
else
{
cout << "it is not an empty bintree" << endl;
}
break;
case 17:
bt.quit_system(select);
break;
default:
break;

    }  
}  
return 0;

}

求高度：

中序遍历：

中序遍历查找：

推断是否为空树：

求其父节点：

后序遍历：

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvemhhb3lhcWlhbjU1Mg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">

前序遍历：

退出系统：

求其右孩子：

求根：

查找：

求节点个数：

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章