C++二叉树实现与遍历操作详解

//1．创建二叉树的链表存储结构；
//2．实现二叉链表的初始化算法、二叉树空的判断算法；
//3．实现二叉树的先序遍历算法、中序遍历算法和后序遍历算法；
//4．利用某遍历算法实现计算二叉树中叶子结点、度为2的结点和度为1的结点的个数。
//5．求二叉树中结点个数。
//6．求二叉树的深度。
//7．设计一个算法，求二叉树中指定结点x的层数。
//8．设计一算法，求先序遍历序列中第k个结点的左右孩子。
/*
9．求结点x的所有祖先。
实验后完成：
（1）输出所有叶子结点到根结点的路径。
#include<iostream>
#include<string>
using namespace std;
typedef int ElemType;
struct NodeType{
ElemType data;
NodeType *lch,*rch,*par;
};


class BiTree{
protected:
NodeType *root;
private:
void Preorder(NodeType *p);                  //先序遍历
void Inorder(NodeType *p);                   //中序遍历
void Postorder(NodeType *p);                 //后序遍历
void Destroy(NodeType *p);                   //删除所有节点

void AllNode(NodeType *p,int &m);            //统计节点总个数
void NodeDegree(NodeType *p,int &x,int &y,int &z);  //度数节点统计
int Predepth(NodeType *p);                   //二叉树的深度
int max(int x,int y);
void Floor(NodeType *p,ElemType x,int &i,int j);  //指定结点x的层数
void KNode(NodeType *p,int k,int i);         //先序遍历序列中第k个结点的左右孩子。
void FindPar(NodeType *p,ElemType x);        //结点x的所有祖先
void LeafPath(NodeType *p);                  //叶子结点到根结点的路径
public:
BiTree(){root=NULL;}
~BiTree(){Destroy(root);root=NULL;}
void Creat_Tree();                            //创建二叉树
bool IsEmpty();                               //判断二叉树是否为空
void Preorder(){Preorder(root);cout<<endl;}   //先序遍历调用
void Inorder(){Inorder(root);cout<<endl;}     //中序遍历调用
void Postorder(){Postorder(root);cout<<endl;} //后序遍历调用
void AllNode(){                               //统计节点总个数
int number=0;
AllNode(root,number);
cout<<"节点总数为："<<number<<endl;
}
void NodeDegree(){                            //度数节点统计
int x=0,y=0,z=0;
NodeDegree(root,x,y,z);
cout<<"叶子个数："<<x<<endl;
cout<<"度为1节点个数："<<y<<endl;
cout<<"度为2节点个数："<<z<<endl;
}
int Predepth(){return Predepth(root);}       //二叉树的深度
void KNode(int k){                           //先序遍历序列中第k个结点的左右孩子