链式存储二叉树
《数据结构C++语言描述》 清华大学出版社， 任燕编著小弟去除了书中一些没有必要的方法，同时还自己写了一个用链式存储自递归方式创建二叉树的方法
嵌入在默认构造函数里，小弟也是很恼火为什么书上这个喜欢顺序存储的二叉树，什么都要从那个二叉树里转化过来，，，，
/*
*二叉树遍历是非常重要的操作，
*二叉树的三种常见的前序，中序，后序递归遍历真的很有意思
*二叉树的操作你会发现离不开递归，递归再解决二叉树链式存储方面真的好用
*遇到不会的问题就要在纸上画一画，会遇到很多常规操作，要牢记
*一些类模板的用法平时要进行知识点的累计和记忆，这种语法问题在C++中非常重要
*have fun
*/
#include <iostream>
#include <cstdlib>
#include <cstdbool>
#include <assert.h>
using namespace std;
//嵌入头文件
#ifndef MYSEQTREE_H
#define MYSEQTREE_H
#include "C://Users//pc//Desktop//BinaryTree//ConsoleApplication1//MySeqTree.cpp"
#endif
#define LH 1 //左高
#define EH 0 //等高
#define RH -1 //右高
template <typename elemtype>
class BiTree{
public:
//二叉树，链表存储结点的数据结构
class Node{
public:
Node() :lchild(NULL), rchild(NULL){}; //初始化构造函数
elemtype data; //结点的数据域
class Node* lchild, *rchild; //左右孩子指针
};
typedef Node* NodePointer; //指向结点的指针类型声明
public:
//链式存储构造二叉树
void createBiTree(NodePointer &p); //这里要取引用
//二叉树置空
void clear();
//求二叉树的叶子数
int countLeaf();
//求二叉树的节点数
int countNode();
//递归求二叉树的深度
int depth();
//显示二叉树的顺序存储
void displaySeqTree();
//交换二叉树中所有结点的左右子树
void exchangeLRchild();
//取根指针
NodePointer getRoot();
//中序递归遍历二叉树
void inOrderTraverse();
//判断是否为空的二叉树
bool isEmpty();
//按层次顺序遍历二叉树
void layOrderTraverse();
//二叉树的二叉链表存储转化位顺序存储结构
void linkToSequential();
//非递归中序遍历二叉树
void noRecursionInOrderTraverse();
//后续递归遍历二叉树
void postOrderTraverse();
//前序递归遍历二叉树
void preOrderTraverse();
//随机生成一棵二叉树
void randomCreate();
//二叉树的顺序存储转化为二叉链表存储的数据结构
//void sequentialToLink(MySeqTree<elemtype> T);
private:
//拷贝初始化构造函数的辅助函数
void BiTree_aux(NodePointer &p, NodePointer otherP);
//求二叉树叶子数的辅助函数
int countLeaf_aux(NodePointer p);
//求二叉树结点数的辅助函数
int countNode_aux(NodePointer p);
//回收二叉树结点存储空间的辅助函数
void deleteNode_aux(NodePointer p);
//递归求二叉树深度的辅助函数
int depth_aux(NodePointer p);
//交换二叉树中所有的结点的左右子树的辅助函数
void exchangeLRchild_aux(NodePointer p);
//中序递归遍历二叉树的辅助函数
void inOrderTraverse_aux(NodePointer p);
//二叉树的二叉链表转化为顺序存储结构的辅助函数
void linkToSequential_aux(MySeqTree<elemtype> &tempT, NodePointer p, int i);
//后序递归遍历二叉树的辅助函数
void postOrderTraverse_aux(NodePointer p);
//前序递归遍历二叉树的辅助函数
void preOrderTraverse_aux(NodePointer p);
//二叉树的顺序存储转化为二叉链表存储结构的辅助函数
void sequentialToLink_aux(int i, NodePointer& subroot);
public:
//构造函数
BiTree();
//二叉树析构函数
virtual ~BiTree();
//拷贝初始化构造函数
BiTree(const BiTree<elemtype> &otherT);
//输入二叉树，采用二叉链表存储
void read(istream& in);
//输出二叉树，采用二叉链表存储
void display(ostream& out);
protected:
NodePointer root; //二叉树的根指针
MySeqTree<elemtype> seqT;//二叉树对应的顺序存储树
};
//把二叉树置空,通过指针递归实现，借助deleteNode_aux，从根指针root开始递归
template <typename elemtype>
void BiTree<elemtype>::clear(){
seqT.clear(); //回收二叉树对应顺序存储的空间
deleteNode_aux(root); //逐一回收二叉树的每一个结点的存储结点
root = NULL; //二叉树根指针置空
}
//回收二叉树结点存储空间的辅助函数
//输入：函数的值参指针p指向待回收的结点
//后序遍历
template <typename elemtype>
void BiTree<elemtype>::deleteNode_aux(NodePointer p){
//按照后序遍历方式逐一回收每一个结点
if (p){
deleteNode_aux(p->lchild); //自递归回收左子树结点
deleteNode_aux(p->rchild); //自递归回收右子树结点
delete p; //回收指针p所指的存储空间
}
}
//求二叉树的也指数
//输出：二叉树的叶子数
//借助coutLeaf_aux从根指针root进行递归
template <typename elemtype>
int BiTree<elemtype>::countLeaf(){
return countLeaf_aux(root);
}
//求二叉树叶子数的辅助函数
//输入：函数的值参指针p指向带判断是否为叶子的结点
//输出：如果指针p指向根节点，函数的返回值返回最终的叶子结点数
template <typename elemtype>
int BiTree<elemtype>::countLeaf_aux(NodePointer p){
int num = 0; //预存放最终的叶子节点数
static int i = 0; //存放叶子结点的累计数，初始化为0
if (p){
if (!p->lchild && !p->rchild){ //找到了叶子
i++;
}
countLeaf_aux(p->lchild); //自递归求左子树的叶子结点数
countLeaf_aux(p->rchild); //自递归求右子树的叶子结点数
}
if (p == root){
num = i;
i = 0; //static 最后要清零，你懂的
}
return num;
}
//求二叉树的结点数
template <typename elemtype>
int BiTree<elemtype>::countNode(){
return countNode_aux(root);
}
//求二叉树结点数的辅助函数
template <typename elemtype>
int BiTree<elemtype>::countNode_aux(NodePointer p){
int num = 0; //预存放最终的节点数
static int i = 0; //类似前面计算叶子数的，你懂的
if (p){
i++; //结点数加一
countNode_aux(p->lchild); //自递归遍历左子树
countNode_aux(p->rchild); //自递归遍历右子树
}
if (p == root){
num = i;
i = 0;
}
return num;
}
//递归求二叉树深度
template <typename elemtype>
int BiTree<elemtype>::depth(){
return depth_aux(root);
}
//递归求二叉树深度辅助函数
template <typename elemtype>
int BiTree<elemtype>::depth_aux(NodePointer p){
int lDep; //预存放左子树的深度
int rDep; //预存放右子树的深度
if (!p){
return 0; //空树返回零
}
else{
lDep = depth_aux(p->lchild);
rDep = depth_aux(p->rchild);
return (lDep > rDep ? lDep : rDep) + 1; //这个递归不同于之前的递归，有意思
}
}
//取根指针
//输出：根指针
template <typename elemtype>
typename BiTree<elemtype>::NodePointer BiTree<elemtype>::getRoot(){ //注意这里的写法
return root;
}
//中序递归遍历二叉树
//从根指针root进行递归
template <typename elemtype>
void BiTree<elemtype>::inOrderTraverse(){
inOrderTraverse_aux(root);
}
//中序递归遍历二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::inOrderTraverse_aux(NodePointer p){
if (p){
cout << "hahhahahhahah" << endl;
inOrderTraverse_aux(p->lchild); //用指针p->lchild自递归遍历左子树的结点
cout << p->data << "\t"; //遍历p所指向的结点
inOrderTraverse_aux(p->rchild); //用指针p->rchild自递归遍历右子树的结点
}
}
//判断是否为空的二叉树
template <typename elemtype>
bool BiTree<elemtype>::isEmpty(){
return root ? false : true;
}
//后序递归遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::postOrderTraverse(){
postOrderTraverse_aux(root);
}
//后序递归遍历二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::postOrderTraverse_aux(NodePointer p){
if (p){
postOrderTraverse_aux(p->lchild);
postOrderTraverse_aux(p->rchild);
cout << p->data << "\t";
}
}
//前序递归遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::preOrderTraverse(){
preOrderTraverse_aux(root);
}
//前序递归遍历二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::preOrderTraverse_aux(NodePointer p){
if (p){
cout << p->data << "\t";
preOrderTraverse_aux(p->lchild);
preOrderTraverse_aux(p->rchild);
}
}
//二叉树的构造函数
template <typename elemtype>
BiTree<elemtype>::BiTree(){
root = NULL;
createBiTree(root);
}
//链式存储创建二叉树
template <typename elemtype>
void BiTree<elemtype>::createBiTree(NodePointer &p){
cout << "请输入数字，要想停止左或右创建要输入多次零:";
elemtype value;
cin >> value;
if (value == 0){
p = NULL;
}
else{
p = new Node;
assert(p != 0);
p->data = value;
createBiTree(p->lchild); //自递归创建左子树
createBiTree(p->rchild); //自递归创建右子树
}
}
//析构函数
template <typename elemtype>
BiTree<elemtype>::~BiTree(){
clear();
}
int main(int argc, char *argv[]){
BiTree<int> bt1;
cout << "结点数:";
cout << bt1.countNode() << endl;
cout << "叶子数:";
cout << bt1.countLeaf() << endl;
cout << "中序遍历:" << endl;
bt1.inOrderTraverse();
return 0;
}
页:
[1]