|
|
///*
|
|
|
// * tree05.cpp
|
|
|
// *
|
|
|
// * Created on: Apr 13, 2024
|
|
|
// * Author: 28032
|
|
|
// */
|
|
|
//
|
|
|
//#include<iostream>
|
|
|
//#include"string"
|
|
|
//#include<queue>
|
|
|
//
|
|
|
//using namespace std;
|
|
|
//
|
|
|
//template<typename E>
|
|
|
//class BinNode//结点类
|
|
|
//{
|
|
|
//private:
|
|
|
// BinNode*lc;//左孩子
|
|
|
// BinNode*rc;//右孩子
|
|
|
// E elem;
|
|
|
//public:
|
|
|
// BinNode()//默认构造函数，设置左右孩子为空
|
|
|
// {
|
|
|
// lc = NULL;
|
|
|
// rc = NULL;
|
|
|
// }
|
|
|
// BinNode(E tmp, BinNode*l=NULL, BinNode*r=NULL)//带参构造函数
|
|
|
// {
|
|
|
// elem = tmp;
|
|
|
// lc = l;
|
|
|
// rc = r;
|
|
|
//
|
|
|
// }
|
|
|
// BinNode*left()//返回左孩子
|
|
|
// {
|
|
|
// return lc;
|
|
|
// }
|
|
|
// BinNode*right()//返回右孩子
|
|
|
// {
|
|
|
// return rc;
|
|
|
// }
|
|
|
// void setLeft(BinNode*l)//设置左孩子
|
|
|
// {
|
|
|
// lc = l;
|
|
|
// }
|
|
|
// void setRight(BinNode*r)//设置右孩子
|
|
|
// {
|
|
|
// rc = r;
|
|
|
// }
|
|
|
// void setValue(E tmp)//设置当前结点的值
|
|
|
// {
|
|
|
// elem = tmp;
|
|
|
// }
|
|
|
// E getValue()//获得当前结点的值
|
|
|
// {
|
|
|
// return elem;
|
|
|
// }
|
|
|
// bool isLeaf()//判断当前结点是否为叶子结点
|
|
|
// {
|
|
|
// return (lc == NULL)&&(rc == NULL);
|
|
|
// }
|
|
|
//};
|
|
|
//
|
|
|
//template<typename E>
|
|
|
//class BinTree//二叉树类
|
|
|
//{
|
|
|
//private:
|
|
|
// BinNode<E>*root;//根结点
|
|
|
// void clear(BinNode<E>*r)//清空二叉树
|
|
|
// {
|
|
|
// if(r == NULL) return ;
|
|
|
// clear(r->left());
|
|
|
// clear(r->right());
|
|
|
//
|
|
|
// delete r;
|
|
|
// }
|
|
|
// void preOrder(BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//先序遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
|
|
|
// {
|
|
|
// if(tmp == NULL) return ;
|
|
|
// visit(tmp);
|
|
|
// preOrder(tmp->left(),visit);
|
|
|
// preOrder(tmp->right(),visit);
|
|
|
// }
|
|
|
// void inOrder( BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//中序遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
|
|
|
// {
|
|
|
// if(tmp == NULL) return ;
|
|
|
// inOrder(tmp->left(),visit);
|
|
|
// visit(tmp);
|
|
|
// inOrder(tmp->right(),visit);
|
|
|
// }
|
|
|
// void postOrder(BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//后序遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
|
|
|
// {
|
|
|
// if(tmp == NULL) return ;
|
|
|
// postOrder(tmp->left(),visit);
|
|
|
// postOrder(tmp->right(),visit);
|
|
|
// visit(tmp);
|
|
|
// }
|
|
|
// void LevelOrderTranverse( BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//层次遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
|
|
|
// {
|
|
|
// if(tmp == NULL) return ;
|
|
|
//
|
|
|
// queue<BinNode<E>*> q;
|
|
|
//
|
|
|
// q.push(tmp);
|
|
|
//
|
|
|
// while(!q.empty())
|
|
|
// {
|
|
|
// BinNode<E>* t = q.front();
|
|
|
// q.pop();
|
|
|
// visit(t);
|
|
|
// if(t->left()) q.push(t->left());
|
|
|
// if(t->right()) q.push(t->right());
|
|
|
// }
|
|
|
//
|
|
|
// }
|
|
|
// int BinTreeDepth(BinNode<E>*tmp)//获得二叉树的深度
|
|
|
// {
|
|
|
// int height = BinTreeHeight(tmp);
|
|
|
//
|
|
|
// if(height) return height-1;
|
|
|
// else return 0;
|
|
|
//
|
|
|
// }
|
|
|
// int BinTreeNodes(BinNode<E>*tmp)//获得二叉树的结点数
|
|
|
// {
|
|
|
// if(tmp == NULL) return 0;
|
|
|
// int left_num = BinTreeNodes(tmp->left());
|
|
|
// int right_num = BinTreeNodes(tmp->right());
|
|
|
//
|
|
|
// return 1+left_num+right_num;
|
|
|
//
|
|
|
// }
|
|
|
// int BinTreeHeight(BinNode<E>*tmp)//获得二叉树的高度
|
|
|
// {
|
|
|
// if(tmp == NULL) return 0;
|
|
|
// int left_height = BinTreeHeight(tmp->left());
|
|
|
// int right_height = BinTreeHeight(tmp->right());
|
|
|
//
|
|
|
// return max(left_height,right_height)+1;
|
|
|
//
|
|
|
// }
|
|
|
// int BinTreeLeafs(BinNode<E>*tmp)//获得二叉树的叶子结点数
|
|
|
// {
|
|
|
// if(tmp == NULL) return 0;
|
|
|
// int left_leafnums = BinTreeLeafs(tmp->left());
|
|
|
// int right_leafnums = BinTreeLeafs(tmp->right());
|
|
|
//
|
|
|
// if(tmp->isLeaf())
|
|
|
// return 1+left_leafnums+right_leafnums;
|
|
|
// else
|
|
|
// return left_leafnums+right_leafnums;
|
|
|
//
|
|
|
// }
|
|
|
// bool find(BinNode<E>*tmp, E e)//查找二叉树中是否含有某个名为e的结点
|
|
|
// {
|
|
|
// if(tmp == NULL) return false;
|
|
|
//
|
|
|
// if(tmp->getValue() == e)
|
|
|
// return true;
|
|
|
//
|
|
|
// bool bl = find(tmp->left(),e);
|
|
|
// bool br = find(tmp->right(),e);
|
|
|
//
|
|
|
// return (bl||br);
|
|
|
//
|
|
|
// }
|
|
|
//public:
|
|
|
// BinTree()//默认构造函数
|
|
|
// {
|
|
|
// root=new BinNode<E>;
|
|
|
// }
|
|
|
// ~BinTree()//析构函数
|
|
|
// {
|
|
|
// clear(root);
|
|
|
// }
|
|
|
// bool BinTreeEmpty()//判断二叉树是否为空
|
|
|
// {
|
|
|
// if (root == NULL)
|
|
|
// return true;
|
|
|
// else
|
|
|
// return false;
|
|
|
// }
|
|
|
// BinNode<E>*getRoot()//获得根节点
|
|
|
// {
|
|
|
// return root;
|
|
|
// }
|
|
|
// void setRoot(BinNode<E>*r)//设置根节点
|
|
|
// {
|
|
|
// root = r;
|
|
|
// }
|
|
|
// //下面的函数是对外的函数，所以内部还会有一些同名的函数，但是参数列表不一样，实现数据的封装，外部的调用不会涉及到内部的数据对象
|
|
|
// void clear()//清空二叉树
|
|
|
// {
|
|
|
// clear(root);
|
|
|
// root = NULL;
|
|
|
// }
|
|
|
// void preOrder(void(*visit)(BinNode<E>*node))//先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
|
|
|
// {
|
|
|
// preOrder(root,visit);
|
|
|
// }
|
|
|
// void inOrder(void(*visit)(BinNode<E>*node)) //先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
|
|
|
// {
|
|
|
// inOrder(root,visit);
|
|
|
// }
|
|
|
// void postOrder(void(*visit)(BinNode<E>*node))//先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
|
|
|
// {
|
|
|
// postOrder(root,visit);
|
|
|
// }
|
|
|
// void LevelOrderTranverse(void(*visit)(BinNode<E>*node))//先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
|
|
|
// {
|
|
|
// LevelOrderTranverse(root,visit);
|
|
|
// }
|
|
|
// int BinTreeDepth()//获得二叉树深度
|
|
|
// {
|
|
|
// return BinTreeDepth(root);
|
|
|
// }
|
|
|
// int BinTreeNodes()//获得二叉树结点数
|
|
|
// {
|
|
|
// return BinTreeNodes(root);
|
|
|
// }
|
|
|
// int BinTreeHeight()//获得二叉树高度
|
|
|
// {
|
|
|
// return BinTreeHeight(root);
|
|
|
// }
|
|
|
// int BinTreeLeafs()//获得二叉树叶子结点数
|
|
|
// {
|
|
|
// return BinTreeLeafs(root);
|
|
|
// }
|
|
|
// bool find(E e)//查找二叉树中是否存在名为e的结点
|
|
|
// {
|
|
|
// return find(root, e);
|
|
|
// }
|
|
|
//};
|
|
|
//
|
|
|
//
|
|
|
//
|
|
|
//template<typename E>
|
|
|
//void printNode(BinNode<E>*tmp)//打印结点的值的函数
|
|
|
//{
|
|
|
// cout << tmp->getValue() << " ";
|
|
|
//}
|
|
|
//
|
|
|
//template<typename E>
|
|
|
//BinNode<E>* creatBinaryTree(string s[], int &x,int n)//构建二叉树的主函数，根据先序遍历，采用递归思想构建
|
|
|
//{
|
|
|
// if (s[x] =="/")
|
|
|
// return NULL;
|
|
|
// else
|
|
|
// {
|
|
|
// BinNode<E>*node = new BinNode<E>(s[x]);
|
|
|
// x = x + 1;
|
|
|
// if (x < n);
|
|
|
// node->setLeft(creatBinaryTree<E>(s, x,n));
|
|
|
// x = x + 1;
|
|
|
// if (x < n);
|
|
|
// node->setRight(creatBinaryTree<E>(s, x,n));
|
|
|
// return node;
|
|
|
// }
|
|
|
//}
|
|
|
//
|
|
|
//void creatBinaryTree(BinTree<string>*BT)//构建二叉树的函数，包含了上面的构建二叉树的主函数，仅仅起到了在主函数中简洁一些的作用
|
|
|
//{
|
|
|
// //cout << "现在进入构建二叉树程序......" << endl;
|
|
|
// //cout << "请输入二叉树有多少个结点(空结点也计算其中)" << endl;
|
|
|
// int n = 0;
|
|
|
// cin >> n;
|
|
|
// //cout << "请按preorder顺序输入，遇到NULL请输入'/',用空格隔开或者回车隔开均可以" << endl;
|
|
|
// string*s = new string[n];
|
|
|
// for (int i = 0; i < n; i++)
|
|
|
// {
|
|
|
// cin >> s[i];
|
|
|
// }
|
|
|
// int now = 0;
|
|
|
// BT->setRoot(creatBinaryTree<string>(s, now, n));
|
|
|
//}
|
|
|
//
|
|
|
//int main()
|
|
|
//{
|
|
|
// //本程序的二叉树是一个模板类，若想改变为别的类型，可以在相关的地方在“<>”中修改相关参数,本程序默认为最具有普遍性的string
|
|
|
// BinTree<string>*BT = new BinTree<string>;
|
|
|
// creatBinaryTree(BT);
|
|
|
// string strfind;
|
|
|
// cin>>strfind;
|
|
|
// //在这里，已经构建好了一棵二叉树
|
|
|
// //下面是二叉树的基本函数操作的展示
|
|
|
//
|
|
|
// cout << "0:判断是否为空树：";
|
|
|
// if (BT->BinTreeEmpty() == true)
|
|
|
// cout << "是" << endl;
|
|
|
// else
|
|
|
// cout << "否" << endl;
|
|
|
// cout << "1:前序遍历:";
|
|
|
// BT->preOrder(printNode);
|
|
|
// cout << endl;
|
|
|
// cout << "2:中序遍历:";
|
|
|
// BT->inOrder(printNode);
|
|
|
// cout << endl;
|
|
|
// cout << "3:后序遍历:";
|
|
|
// BT->postOrder(printNode);
|
|
|
// cout << endl;
|
|
|
// cout << "4:层次遍历:";
|
|
|
// BT->LevelOrderTranverse(printNode);
|
|
|
// cout << endl;
|
|
|
// cout << "5:记录树的深度:";
|
|
|
// cout << BT->BinTreeDepth() << endl;
|
|
|
// cout << "6:记录树的高度:";
|
|
|
// cout << BT->BinTreeHeight() << endl;
|
|
|
// cout << "7:统计结点:";
|
|
|
// cout << BT->BinTreeNodes() << endl;
|
|
|
// cout << "8:统计叶子结点:";
|
|
|
// cout << BT->BinTreeLeafs() << endl;
|
|
|
// cout << "9:查找"<<strfind<<":";
|
|
|
// if (BT->find(strfind) == true)
|
|
|
// cout << "存在" << endl;
|
|
|
// else
|
|
|
// cout << "不存在" << endl;
|
|
|
// cout << "10:是否清空:";
|
|
|
// BT->clear();
|
|
|
// cout << "已清空" << endl;
|
|
|
// cout << "5:记录树的深度:";
|
|
|
// cout << BT->BinTreeDepth() << endl;
|
|
|
// cout << "6:记录树的高度:";
|
|
|
// cout << BT->BinTreeHeight() << endl;
|
|
|
// cout << "7:统计结点:";
|
|
|
// cout << BT->BinTreeNodes() << endl;
|
|
|
// cout << "8:统计叶子结点:";
|
|
|
// cout << BT->BinTreeLeafs() << endl;
|
|
|
// return 0;
|
|
|
//}
|
|
|
//
|
|
|
//
|
|
|
//
|
