【数据结构】二叉树(c++)
2024-09-01 13:34:10
头文件：
#include <iostream>
using namespace std; template<class Type>
class Bintree; //结点类
template<class Type>
class BintreeNode
{
friend class Bintree<Type>;
public:
BintreeNode() :data(Type()), leftchild(NULL), rightchild(NULL)
{}
BintreeNode(Type d, BintreeNode<Type> *l = NULL, BintreeNode<Type> *r = NULL) : data(d), leftchild(l), rightchild(r)
{}
private:
BintreeNode<Type> *leftchild;
BintreeNode<Type> *rightchild;
Type data;
}; //二叉树类
template<class Type>
class Bintree
{
public:
Bintree() :Ref(Type()), root(NULL)
{}
Bintree(Type re, BintreeNode<Type> *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<Type> *&t)
{
Type input;
cin >> input;
if (input == Ref)
{
t = NULL;
}
else
{
t = new BintreeNode<Type>(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<Type> *root;
Type Ref;
};
页面设计：
#include "Bintree.h" int main()
{
Bintree<char> 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="">
前序遍历：
退出系统：
求其右孩子：
求根：
查找：
求节点个数：
最新文章
- docker index服务概述
- CNAME
- c#中的类型转换
- Java Swing中Substance个人比较喜欢的两种组合
- (转)ReSharper 配置及用法
- scanf与gets函数混用 前后位置出错的问题解决
- npm note
- c语言： inline（gcc）
- qt button以及label实现不规则图形（五种方法：使用QSS，设置Mask图片，自己画）
- GreenOpenPaint的实现（一）基本框架
- 阻塞IO
- 柯塔娜（Cortana）：从科幻虚构到真实人生
- shell第四篇（上）
- PHP生成腾讯云COS请求签名
- day-02
- Session之Config配置
- Java 对象的序列化和反序列化
- NET Core 指令启动
- SharePoint 2013 安装.NET Framework 3.5 报错
- 微软BI 之SSRS 系列 - 使用 LookupSet 和 Adjacent Group 等高级技巧在报表中跨 Dataset 分组查询