统计二叉树各度数的结点的个数高度宽度结点最大元素的值交换结点的左孩子和右孩子删除所有叶子节点
/*设一棵二叉树以二叉链表表示，试编写有关二叉树的递归算法：
1、统计二叉树中度为1的结点
2、统计二叉树中度为2的结点
3、统计二叉树中度为0的结点
4、统计二叉树的高度
5、统计二叉树的宽度，即在二叉树各层上具有节点数最多的那一层上结点总数
6、计算二叉树中个结点最大元素的值
7、交换每个结点的左孩子结点和右孩子结点
8从二叉树中删除所有叶子节点*/
#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;
template <class T>
class btrnode
{
public:
T element; //结点的数据域
btrnode<T>* lchild; //结点的左孩子结点
btrnode<T>* rchild; //结点的右孩子节点
btrnode(){ lchild = NULL; rchild = NULL; } //默认构造函数
btrnode(T ele) //给定数值域的值得构造函数
{
element = ele;
lchild = NULL;
rchild = NULL;
}
};
//二叉树的抽象数据类型
template <class T>
class btr
{
private:
btrnode<T>* root;
int count;
public:
btr(){ count = 0; } //默认构造函数
btrnode<T>* pib(string preod, string inod); //前序中序构造二叉树的算法 int num0(btrnode<T>* root); //求度为0的结点的个数
int num1(btrnode<T>* root); //求度为1的结点的个数
int num2(btrnode<T>* root); //求度为2的结点的个数
int btrhigh(btrnode<T>* root); //求树的的高度
int btrwidth(btrnode<T>* root); //求树的宽度
btrnode<T>* max(btrnode<T>* root); //二叉树中个结点最大元素的值 void change(btrnode<T>* root); //交换每个结点的左右孩子
void del(btrnode<T>* &root); //删除所有叶子节点
void preorder(btrnode<T>* root);
void visit(btrnode<T>* cur);
};
//先序、中序构造二叉树递归算法
template <class T>
btrnode<T>* btr<T>::pib(string preod, string inod)// 是二 叉树结点个数 {
string p, q, m, n;
int i = 0;
btrnode<char>* tmp = new btrnode<char>; //？？？？？？？？为什么直接构造无法赋值成功？？？？？？？？？
tmp->element = preod[0];
for (; inod[i] != preod[0]; i++);
if (preod == "" || inod == "")
return NULL;
p = preod.substr(1, i);
q = inod.substr(0, i);
m = preod.substr(i + 1);
n = inod.substr(i + 1);
tmp->lchild = pib(p, q);
tmp->rchild = pib(m, n);
return tmp;
}
//求度为0的结点的个数
template <class T>
int btr<T>::num0(btrnode<T>* root)
{
int n ,m,sum=0 ;
btrnode<T>* pointer = root;
if (pointer)
{
if (pointer->lchild == NULL && pointer->rchild == NULL) sum++;
n = num0(pointer->lchild);
sum += n;
m = num0(pointer->rchild);
sum += m;
}
return sum;
}
//求度为1的结点的个数
template <class T>
int btr<T>::num1(btrnode<T>* root)
{
int n, m, sum = 0;
btrnode<T>* pointer = root;
if (pointer)
{
if ((pointer->lchild == NULL && pointer->rchild (pointer->rchild == NULL && pointer->lchild != NULL)) sum++;
n = num1(pointer->lchild);
sum += n;
m = num1(pointer->rchild);
sum += m;
}
return sum;
}
//求度为2的结点的个数
template <class T>
int btr<T>::num2(btrnode<T>* root)
{
int n, m, sum = 0;
btrnode<T>* pointer = root;
if (pointer) NULL) != ||
{
if (pointer->lchild != NULL && pointer->rchild != NULL) sum++;
n = num2(pointer->lchild);
sum += n;
m = num2(pointer->rchild);
sum += m;
}
return sum;
}
//求树的的高度
template <class T>
int btr<T>::btrhigh(btrnode<T>* root)
{
btrnode<T>* pointer = root;
int m, n, max;
if (pointer == NULL)
return 0;
m = btrhigh(pointer->lchild);
n = btrhigh(pointer->rchild);
max = 1 + (m > n ? m : n);
return max;
}
//求树的宽度
template <class T>
int btr<T>::btrwidth(btrnode<T>* root)
{
int cur, max = 0;
btrnode<T> *pointer = root;
queue<btrnode<T> *> nqueue1 , nqueue2;
if (pointer == NULL)
return 0;
nqueue1.push(pointer);
while (!nqueue1.empty())
{
cur = 0;
while (!nqueue1.empty())
{
cur++;
pointer = nqueue1.front();
nqueue1.pop();
if (pointer->lchild != NULL)
nqueue2.push(pointer->lchild);
if (pointer->rchild != NULL)
nqueue2.push(pointer->rchild);
}
max = (max > cur ? max : cur);
while (!nqueue2.empty())
{
nqueue1.push(nqueue2.front());
nqueue2.pop();
}
}
return max;
}
/*//求树的宽度
template <class T>
int btr<T>::btrwidth(btrnode<T>* root)
{
int n, m, sum = 0;
btrnode<T>* pointer = root;
if (pointer)
{
sum = 1;
n = btrwidth(pointer->lchild);
m = btrwidth(pointer->rchild);
}
return sum;
}*/
//二叉树中个结点最大元素的值
template <class T>
btrnode<T>* btr<T>::max(btrnode<T>* root)
{
btrnode<T>* pointer = root;
btrnode<T> *tmp, *tmpl, *tmpr;
if (pointer == NULL)
return NULL;
tmpl = max(pointer->lchild);
tmpr = max(pointer->rchild);
if (tmpl == NULL && tmpr == NULL)
tmp = pointer;
else
{
if (tmpl != NULL && tmpr == NULL)
tmp = tmpl;
else if (tmpl == NULL && tmpr != NULL)
tmp = tmpr;
else
tmp = (tmpl->element > tmpr->element ? tmpl : tmpr);
tmp = (tmp->element > pointer->element ? tmp : pointer);
}
return tmp;
}
//删除所有叶子节点
template <class T>
void btr<T>::del(btrnode<T>* &root)
{
if (root == NULL)
return ;
if (root->lchild == NULL && root->rchild == NULL){
delete root;
root = NULL;
return;
}
del(root->lchild);
del(root->rchild);
}
//交换每个结点的左右孩子
template <class T>
void btr<T>::change(btrnode<T>* root)
{
btrnode<T>* tmp;
btrnode<T>* pointer = root;
if (pointer)
{
tmp = pointer->lchild;
pointer->lchild = pointer->rchild;
pointer->rchild = tmp;
}
else
return;
change(pointer->l
child);
change(pointer->rchild);
}
//前序遍历
template <class T>
void btr<T>::preorder(btrnode<T>* root)
{
if (root != NULL)
{
visit(root); //处理根结点
preorder(root->lchild);
preorder(root->rchild);
}
}
template <class T>
void btr<T>::visit(btrnode<T>* cur)
{
cout << cur->element << " ";
}
int main()
{
string a, b;
btr<char> c;
btrnode<char>* root,*tmp;
int n;
cout << "分别输入先序序列、和中序序列：";
cin >> a;
cin >> b;
root = c.pib(a, b);
n = c.num0(root);
cout << "度为0的结点个数: " << n << endl; n = c.num1(root);
cout << "度为1的结点个数: " << n << endl; n = c.num2(root);
cout << "度为2的结点个数: " << n << endl; n = c.btrhigh(root);
cout << "树的高度为: " << n << endl;
n = c.btrwidth(root);
cout << "树的宽度为: " << n << endl;
tmp = c.max(root);
cout << "最大元素值为" << tmp->element << endl; c.change(root);
c.preorder(root);
cout << endl;
c.del(root);
c.preorder(root);
return 0;
}
统计二叉树各度数的结点的个数高度宽度结点最大元素的值交换结点的左孩子和右孩子删除所有叶子节点
/*设一棵二叉树以二叉链表表示，试编写有关二叉树的递归算法：
1、统计二叉树中度为1的结点
2、统计二叉树中度为2的结点
3、统计二叉树中度为0的结点
4、统计二叉树的高度
5、统计二叉树的宽度，即在二叉树各层上具有节点数最多的那一层上结点总数
6、计算二叉树中个结点最大元素的值
7、交换每个结点的左孩子结点和右孩子结点
8从二叉树中删除所有叶子节点*/
#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;
template <class T>
class btrnode
{
public:
T element; //结点的数据域
btrnode<T>* lchild; //结点的左孩子结点
btrnode<T>* rchild; //结点的右孩子节点
btrnode(){ lchild = NULL; rchild = NULL; } //默认构造函数
btrnode(T ele) //给定数值域的值得构造函数
{
element = ele;
lchild = NULL;
rchild = NULL;
}
};
//二叉树的抽象数据类型
template <class T>
class btr
{
private:
btrnode<T>* root;
int count;
public:
btr(){ count = 0; } //默认构造函数
btrnode<T>* pib(string preod, string inod); //前序中序构造二叉树的算法 int num0(btrnode<T>* root); //求度为0的结点的个数
int num1(btrnode<T>* root); //求度为1的结点的个数
int num2(btrnode<T>* root); //求度为2的结点的个数
int btrhigh(btrnode<T>* root); //求树的的高度
int btrwidth(btrnode<T>* root); //求树的宽度
btrnode<T>* max(btrnode<T>* root); //二叉树中个结点最大元素的值 void change(btrnode<T>* root); //交换每个结点的左右孩子
void del(btrnode<T>* &root); //删除所有叶子节点
void preorder(btrnode<T>* root);
void visit(btrnode<T>* cur);
};
//先序、中序构造二叉树递归算法
template <class T>
btrnode<T>* btr<T>::pib(string preod, string inod)// 是二 叉树结点个数 {
string p, q, m, n;
int i = 0;
btrnode<char>* tmp = new btrnode<char>; //？？？？？？？？为什么直接构造无法赋值成功？？？？？？？？？
tmp->element = preod[0];
for (; inod[i] != preod[0]; i++);
if (preod == "" || inod == "")
return NULL;
p = preod.substr(1, i);
q = inod.substr(0, i);
m = preod.substr(i + 1);
n = inod.substr(i + 1);
tmp->lchild = pib(p, q);
tmp->rchild = pib(m, n);
return tmp;
}
//求度为0的结点的个数
template <class T>
int btr<T>::num0(btrnode<T>* root)
{
int n ,m,sum=0 ;
btrnode<T>* pointer = root;
if (pointer)
{
if (pointer->lchild == NULL && pointer->rchild == NULL) sum++;
n = num0(pointer->lchild);
sum += n;
m = num0(pointer->rchild);
sum += m;
}
return sum;
}
//求度为1的结点的个数
template <class T>
int btr<T>::num1(btrnode<T>* root)
{
int n, m, sum = 0;
btrnode<T>* pointer = root;
if (pointer)
{
if ((pointer->lchild == NULL && pointer->rchild (pointer->rchild == NULL && pointer->lchild != NULL)) sum++;
n = num1(pointer->lchild);
sum += n;
m = num1(pointer->rchild);
sum += m;
}
return sum;
}
//求度为2的结点的个数
template <class T>
int btr<T>::num2(btrnode<T>* root)
{
int n, m, sum = 0;
btrnode<T>* pointer = root;
if (pointer) NULL) != ||
{
if (pointer->lchild != NULL && pointer->rchild != NULL) sum++;
n = num2(pointer->lchild);
sum += n;
m = num2(pointer->rchild);
sum += m;
}
return sum;
}
//求树的的高度
template <class T>
int btr<T>::btrhigh(btrnode<T>* root)
{
btrnode<T>* pointer = root;
int m, n, max;
if (pointer == NULL)
return 0;
m = btrhigh(pointer->lchild);
n = btrhigh(pointer->rchild);
max = 1 + (m > n ? m : n);
return max;
}
//求树的宽度
template <class T>
int btr<T>::btrwidth(btrnode<T>* root)
{
int cur, max = 0;
btrnode<T> *pointer = root;
queue<btrnode<T> *> nqueue1 , nqueue2;
if (pointer == NULL)
return 0;
nqueue1.push(pointer);
while (!nqueue1.empty())
{
cur = 0;
while (!nqueue1.empty())
{
cur++;
pointer = nqueue1.front();
nqueue1.pop();
if (pointer->lchild != NULL)
nqueue2.push(pointer->lchild);
if (pointer->rchild != NULL)
nqueue2.push(pointer->rchild);
}
max = (max > cur ? max : cur);
while (!nqueue2.empty())
{
nqueue1.push(nqueue2.front());
nqueue2.pop();
}
}
return max;
}
/*//求树的宽度
template <class T>
int btr<T>::btrwidth(btrnode<T>* root)
{
int n, m, sum = 0;
btrnode<T>* pointer = root;
if (pointer)
{
sum = 1;
n = btrwidth(pointer->lchild);
m = btrwidth(pointer->rchild);
}
return sum;
}*/
//二叉树中个结点最大元素的值
template <class T>
btrnode<T>* btr<T>::max(btrnode<T>* root)
{
btrnode<T>* pointer = root;
btrnode<T> *tmp, *tmpl, *tmpr;
if (pointer == NULL)
return NULL;
tmpl = max(pointer->lchild);
tmpr = max(pointer->rchild);
if (tmpl == NULL && tmpr == NULL)
tmp = pointer;
else
{
if (tmpl != NULL && tmpr == NULL)
tmp = tmpl;
else if (tmpl == NULL && tmpr != NULL)
tmp = tmpr;
else
tmp = (tmpl->element > tmpr->element ? tmpl : tmpr);
tmp = (tmp->element > pointer->element ? tmp : pointer);
}
return tmp;
}
//删除所有叶子节点
template <class T>
void btr<T>::del(btrnode<T>* &root)
{
if (root == NULL)
return ;
if (root->lchild == NULL && root->rchild == NULL){
delete root;
root = NULL;
return;
}
del(root->lchild);
del(root->rchild);
}
//交换每个结点的左右孩子
template <class T>
void btr<T>::change(btrnode<T>* root)
{
btrnode<T>* tmp;
btrnode<T>* pointer = root;
if (pointer)
{
tmp = pointer->lchild;
pointer->lchild = pointer->rchild;
pointer->rchild = tmp;
}
else
return;
change(pointer->l
child);
change(pointer->rchild);
}
//前序遍历
template <class T>
void btr<T>::preorder(btrnode<T>* root)
{
if (root != NULL)
{
visit(root); //处理根结点
preorder(root->lchild);
preorder(root->rchild);
}
}
template <class T>
void btr<T>::visit(btrnode<T>* cur)
{
cout << cur->element << " ";
}
int main()
{
string a, b;
btr<char> c;
btrnode<char>* root,*tmp;
int n;
cout << "分别输入先序序列、和中序序列：";
cin >> a;
cin >> b;
root = c.pib(a, b);
n = c.num0(root);
cout << "度为0的结点个数: " << n << endl; n = c.num1(root);
cout << "度为1的结点个数: " << n << endl; n = c.num2(root);
cout << "度为2的结点个数: " << n << endl; n = c.btrhigh(root);
cout << "树的高度为: " << n << endl;
n = c.btrwidth(root);
cout << "树的宽度为: " << n << endl;
tmp = c.max(root);
cout << "最大元素值为" << tmp->element << endl; c.change(root);
c.preorder(root);
cout << endl;
c.del(root);
c.preorder(root);
return 0;
}