二叉树的中序遍历序列

女爷i 2023-05-28 15:51 13阅读 0赞

## 二叉树的中序遍历序列 ##

【问题描述】

设计算法求二叉树的中序遍历序列。

![在这里插入图片描述][20200316103133594.png]

【输入形式】一行字符串，该行是扩展二叉树的前序遍历序列，用于构造二叉树。

【输出形式】二叉树中的中序遍历序列。

【样例输入】AB\#D\#\#C\#\#

【样例输出】

BDAC

#include<iostream>
    using namespace std;
    template<typename DataType>
    
    struct BiNode
    {
        
    	DataType data;
    	BiNode<DataType> *lchild,*rchild;
    };
    
    template <typename DataType>
    class BiTree
    {
        
    	public:
    		BiTree()
    		{
        
    			root=Creat();
    		}
    		void InOrder()
    		{
        
    			InOrder(root);
        	}
    	private:
    		BiNode<DataType> *Creat();
    		void InOrder(BiNode<DataType> *bt);
    		BiNode<DataType> *root;
    };
    
    
    
    template<typename DataType>
    BiNode<DataType> *BiTree<DataType>::Creat()
    {
        
    	BiNode<DataType> *bt;
    	char ch;
    	cin>>ch;
    	if(ch=='#')  bt=NULL;
    	else
    	{
        
    		bt=new BiNode<DataType>;
    		bt->data=ch;
    		bt->lchild=Creat();
    		bt->rchild=Creat();
    	}
    	return bt;
    }
    
    template<typename DataType>
    void BiTree<DataType>::InOrder(BiNode<DataType> *bt)
    {
        
    	if(bt)
    	{
        
    		InOrder(bt->lchild);
    		cout<<bt->data;
    		InOrder(bt->rchild);
    	}
    }
    
    
    int main()
    {
        
    	BiTree<char>  t;
    	t.InOrder();
    }

[20200316103133594.png]: /images/20230528/6e12ebfd933749f89a7e8fb5d39fff24.png