叶⽼师版数据结构⼆叉树各种函数
//⼆叉树类
#include "BinaryNode.h" //⼆叉树的⼆叉链表结点类
#include "SeqStack.h" //顺序栈
#include "LinkedStack.h" //链式栈
实验室制取乙烯#include "SeqQueue.h" //顺序循环队列
//#include "LinkedQueue.h" //链式队列
template
class BinaryTree //⼆叉树类
{
public:
BinaryNode *root; //指向根结点
BinaryTree(); //构造空⼆叉树
BinaryTree(T prelist[], int n); //以标明空⼦树的先根序列构造⼀棵⼆叉树BinaryTree(T prelist[], T inlist[], int n); //以先根和中根序列构造⼆叉树
~BinaryTree(); //析构函数
bool isEmpty(); //判断是否空⼆叉树
void preOrder(); //先根次序遍历⼆叉树最热门的专业
void inOrder(); //中根次序遍历⼆叉树
void postOrder(); //后根次序遍历⼆叉树
int count(); //返回⼆叉树的结点个数
int height(); //返回⼆叉树的⾼度
BinaryNode* arch(T value); //查找⾸次出现的值为value的结点BinaryNode* getParent(BinaryNode *node); //返回node结点的⽗母结点
BinaryNode* inrt(BinaryNode *p, T value, bool leftChild=true); //插⼊value作为p结点的孩⼦
void remove(BinaryNode *p, bool leftChild=true); //删除p结点的左或右⼦树
void printGList(); //以⼴义表表⽰输出⼆叉树
void inOrderTraver(); //中根次序遍历⼆叉树的⾮递归算法void levelOrder(); //按层次遍历⼆叉树
private:
void preOrder(BinaryNode *p); //先根次序遍历以p结点为根的⼦树void inOrder(BinaryNode *p); //中根次序遍历以p结点为根的⼦树void postOrder(BinaryNode *p); //后根次序遍历以p结点为根的⼦树void destroy(BinaryNode *p); //撤销⼆叉树BinaryNode* create(T prelist[], int n, int &i); //以标明空⼦树的先根遍历序列创建⼦树
BinaryNode* create(T prelist[], T inlist[], int preStart, int inStart, int n); //以先根和中根序列创建⼀棵⼦树
鲁班
int count(BinaryNode *p); //返回以p结点为根的⼦树结点个数int height(BinaryNode *p); //返回以p结点为根的⼦树⾼度
void printGList(BinaryNode *p); //以⼴义表表⽰输出以p结点为根的⼦树
//第6章习题
public:
void leaf(); //遍历输出叶⼦结点
int countLeaf(); //返回⼆叉树的叶⼦结点数
bool replace(T old, T value); //将⾸次出现的值为old结点值替换为value
void replaceAll(T old, T value); //将值为old的结点全部替换为value
int operator==(BinaryTree &bitree); //⽐较两棵⼆叉树是否相等，重载运算符==
BinaryTree(BinaryTree &bitree); //由已知的bitree构造⼆叉树
void preOrderTraver(); //先根次序遍历⼆叉树的⾮递归算法bool isSorted(); //判断⼀棵⼆叉树是否为⼆叉排序树private:
void leaf(BinaryNode *p); //输出以p结点为根的⼦树的所有叶⼦结点
int countLeaf(BinaryNode *p); //返回以p结点为根的⼦树的叶⼦结点个数
void replaceAll(BinaryNode *p, T old, T value); //在以p为根的⼦树中实现全部替换
bool equals(BinaryNode *p, BinaryNode *q); //判断以p和q结点为根的两棵⼦树是否相等
BinaryNode* copy(BinaryNode *p); //复制以p根的⼦⼆叉树
//第8章习题
bool isSorted(BinaryNode* p);
};
template
BinaryTree::BinaryTree() //构造空⼆叉树
{
root = NULL;
}
template
bool BinaryTree::isEmpty() //判断是否空⼆叉树
{
return root==NULL;
}
//3. ⼆叉树的先根、中根和后根次序遍历算法
template
void BinaryTree::preOrder() //先根次序遍历⼆叉树
{
void BinaryTree::preOrder(BinaryNode *p) //先根次序遍历以p结点为根的⼦树，递归函数{
if (p!=NULL) //若⼆叉树不空
{
cout<data<<" "; //访问当前结点
preOrder(p->left); //按先根次序遍历当前结点的左⼦树，递归调⽤
preOrder(p->right); //按先根次序遍历当前结点的右⼦树，递归调⽤
铭记那份美好}
}
template
void BinaryTree::inOrder() //中根次序遍历⼆叉树
{
cout<<"中根次序遍历⼆叉树: ";
inOrder(root); //调⽤中根次序遍历⼆叉树的递归函数
cout<
}
template
void BinaryTree::inOrder(BinaryNode *p) //中根次序遍历以p结点为根的⼦树，递
归函数
{
if (p!=NULL)
{
inOrder(p->left);
cout<data<<" ";
inOrder(p->right);
}
}
鼻子痛template
void BinaryTree::postOrder() //后根次序遍历⼆叉树
{
void BinaryTree::postOrder(BinaryNode *p) //后根次序遍历以p结点为根的⼦树，递归函数{
if (p!=NULL)
{
postOrder(p->left);
postOrder(p->right);
cout<data<<" ";
}
}
//4. 基于遍历的操作
template
BinaryTree::~BinaryTree() //析构函数
{
cout<<"撤销⼆叉树: ";
destroy(root);
cout<
儿童中耳炎症状}
template
void BinaryTree::destroy(BinaryNode *p) //撤销以p结点为根的⼦树，后根次序遍历
if (p!=NULL)
{
destroy(p->left);
destroy(p->right);
cout<data<<" "; //显⽰撤销结点的次序
delete p;
}
}
舞台设计方案
//【例6.1】构造并遍历⼆叉树。
template
int BinaryTree::count() //返回⼆叉树的结点个数
}
template
int BinaryTree::count(BinaryNode *p) //返回以p结点为根的⼦树结点个数{
if (p==NULL)
return 0;
el
return 1+count(p->left)+count(p->right);
}
template
int BinaryTree::height() //返回⼆叉树的⾼度国土整治
{
return height(root);
}
template
int BinaryTree::height(BinaryNode *p) //返回以p结点为根的⼦树⾼度，后根次序遍历{
if (p!=NULL)
{
int lh = height(p->left); //求左⼦树的⾼度
int rh = height(p->right);
return (lh>=rh) ? lh+1 : rh+1;
}
return 0;
}
template
BinaryNode* BinaryTree::arch(T value) //查找⾸次出现的值为value结点
{
return arch(root, value);
}
template
BinaryNode* BinaryTree::arch(BinaryNode *p, T value) //在以p为根的⼦树中查找{ //先根次序遍历查找值为value的结点，返回⾸次出现结点指针，若未找到返回NULL BinaryNode *find=NULL; //记载找到结点
