二叉树的链式存储

实现二叉树的基本操作:建立、遍历、计算深度、结点数、叶子数等。

输入C,先序创建二叉树,#表示空节点;

输入H:计算二叉树的高度;

输入L:计算二叉树的叶子个数;

输入N:计算二叉树节点总个数;

输入1:先序遍历二叉树;

输入2:中序遍历二叉树;

输入3:后续遍历二叉树;

输入F:查找值=x的节点的个数;

输入P:以缩格文本形式输出所有节点。

代码如下:

#include <iostream>
#include <stack>
#include <iomanip>
using namespace std;
class BinaryTree;
class BinTreeNode{//结点类定义
    friend class BinaryTree;
private:
    BinTreeNode *leftChild,*rightChild;//左右子女链域
    char data;//数据域
public:
    BinTreeNode(){leftChild=NULL;rightChild=NULL;}
    BinTreeNode(char x,BinTreeNode *left=NULL,BinTreeNode *right=NULL)
    {//构造函数
        data=x;
        leftChild=left;
        rightChild=right;
    }
    ~BinTreeNode(){}//析构函数
};
class BinaryTree{//二叉树的定义
private:
    BinTreeNode *root;//二叉树的根指针
    char RefValue;//数据输入停止标志
    void CreateBinTree(BinTreeNode *&subTree);
    int Height(BinTreeNode *subTree);
    int Size(BinTreeNode *subTree);
    int Leaf(BinTreeNode *subTree);
    int Node(BinTreeNode *subTree,char x);
    void preOrder(BinTreeNode *subTree);//前序遍历
    void inOrder(BinTreeNode *subTree);//中序遍历
    void postOrder(BinTreeNode *subTree);//后序遍历
public:
    BinaryTree():root(NULL),RefValue('#'){}
    BinaryTree(char value){RefValue=value;root=NULL;}
    void CreateBinTree(){
        CreateBinTree(root);
    }
    BinTreeNode *LeftChild(BinTreeNode *current)
    {
        return(current!=NULL)?current->leftChild:NULL;
    }
    BinTreeNode *rightChild(BinTreeNode *current)
    {
        return(current!=NULL)?current->rightChild:NULL;
    }
    int Height(){return Height(root);}//二叉树高度
    int Size(){return Size(root);}//二叉树结点总个数
    int Leaf(){return Leaf(root);}//叶子个数
    int Node(char x){return Node(root,x);}//查找值=x的节点的个数
    void preOrder(){preOrder(root);}//前序遍历
    void inOrder(){inOrder(root);}//中序遍历
    void postOrder(){postOrder(root);}//后序遍历
    void output();
};
void BinaryTree::CreateBinTree(BinTreeNode *&subTree)//二叉树的建立
{
    char item;
    cin>>item;
    if(item!=RefValue)
    {
        subTree=new BinTreeNode(item);
        CreateBinTree(subTree->leftChild);
        CreateBinTree(subTree->rightChild);
    }
    else subTree=NULL;
}
int Max(int left,int right)
{
    return(left<right)?right:left;
}
int BinaryTree::Height(BinTreeNode *subTree)//计算二叉树的高度
{
    if(subTree==NULL)return 0;
    else return 1+Max(Height(subTree->leftChild),Height(subTree->rightChild));
}
int BinaryTree::Leaf(BinTreeNode *subTree)//计算二叉树叶子节点数
{
    if(subTree==NULL)return 0;
    else{
        if(subTree->leftChild==NULL&&subTree->rightChild==NULL)
        {
            return 1;
        }
        else
            return(Leaf(subTree->leftChild)+Leaf(subTree->rightChild));
    }
}
int BinaryTree::Size(BinTreeNode *subTree)//计算结点总个数
{
    if(subTree==NULL)return 0;
    else
        return 1+Size(subTree->leftChild)+Size(subTree->rightChild);
}
void BinaryTree::preOrder(BinTreeNode *subTree)//前序遍历
{
    if(subTree!=NULL)
    {
        cout<<subTree->data<<" ";
        preOrder(subTree->leftChild);
        preOrder(subTree->rightChild);
    }
}
void BinaryTree::inOrder(BinTreeNode *subTree)//中序遍历
{
    if(subTree!=NULL)
    {
        inOrder(subTree->leftChild);
        cout<<subTree->data<<" ";
        inOrder(subTree->rightChild);
    }
}
void BinaryTree::postOrder(BinTreeNode *subTree)//后序遍历
{
    if(subTree!=NULL)
    {
        postOrder(subTree->leftChild);
        postOrder(subTree->rightChild);
        cout<<subTree->data<<" ";
    }
}
int BinaryTree::Node(BinTreeNode *subTree,char x)//查找值=x的节点的个数
{
    if(subTree==NULL)
        return 0;
    else if(subTree->data==x)
        return 1;
    else
        return Node(subTree->leftChild,x)+Node(subTree->rightChild,x);
}
void BinaryTree::output(){
    stack<BinTreeNode*> S;
    BinTreeNode *p=root;
    int counter=1;
    int label=0;
    cout<<"The tree is:"<<endl;
    while(p!=NULL){
    cout<<setw(counter)<<setfill(' ');
    if(label==1){
    cout<<setw(counter+2)<<setfill(' ');
    label=0;
    }
    cout<<p->data<<endl;
    if(p->leftChild==NULL && p->rightChild==NULL && S.empty()) return;
    if(p->rightChild!=NULL)  S.push(p->rightChild);
    if(p->leftChild!=NULL){
    p=p->leftChild;
    counter+=2;
 }
 else{
 p=S.top();
 S.pop();
 if(!S.empty()) label=1;
 }
 }
 }
int main()
{
    char oper;
    int count=0;
    BinaryTree A;
    while(1)
    {
        cin>>oper;
        char x;
        switch(oper)
        {
            case 'C':A.CreateBinTree();cout<<"Created success!"<<endl;break;
            case 'H':cout<<"Height="<<A.Height()<<"."<<endl;break;
            case 'L':cout<<"Leaf="<<A.Leaf()<<"."<<endl;break;
            case 'N':cout<<"Nodes="<<A.Size()<<"."<<endl;break;
            case '1':cout<<"Preorder is:";A.preOrder();cout<<"."<<endl;break;
            case '2':cout<<"Inorder is:";A.inOrder();cout<<"."<<endl;break;
            case '3':cout<<"Postorder is:";A.postOrder();cout<<"."<<endl;break;
            case 'F':cin>>x;
                cout<<"The count of "<<x<<" is "<<A.Node(x)<<"."<<endl;break;
            case 'P':A.output();count=1;break;
        }
        if(count==1)
        {
            break;
        }
    }
    return 0;
}


You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注