链式存储二叉树

溯影

《数据结构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;
}