二叉树遍历c++实现

- 日理万妓 2022-07-15 01:50 201阅读 0赞

//自己还真是个菜鸡，大一学了一年c++，现在还在基础的语法上转圈，还没有意识到c++真正的
    //的强大之处在于它的多变，封装，等算法告一段落了在考虑是往Java上走还是深造c++
    #include <iostream>
    #include <stack>
    #include <string>
    using namespace std;
    struct binode
    {
    	char date;
    	binode *lchild,*rchild;
    	bool isfirst;//非递归后续遍历要用到
    };
    class bitree
    {
    private:
    	binode *root;
    public:
    	bitree()
    	{
    		create(root);
    	};
        ~bitree();
    	binode *getroot()
    	{
    		return root;
    	}
    	void create(binode *jj)//建立二叉树
    	{
    		char aa;
    		cin>>aa;
    		if(aa==' ') jj=NULL;
    		else
    		{
    			jj=new binode;
    			jj->date=aa;
    			create(jj->lchild);
    			create(jj->rchild);
    			jj->isfirst=true;
    		}
    	}
    	void preordert(binode *a)//遍历二叉树--先序遍历递归算法
    	{
    		cout<<a->date;
    		preordert(a->lchild);
    		preordert(a->rchild);
    	}
    	void preordernonrec(binode *aa)//非递归先序遍历
    	{
    		stack<binode *> s;
    		s.push(aa);cout<<aa->date;
    		while(!s.empty())
    		{
    			while(aa->lchild) {aa=aa->lchild;s.push(aa);cout<<aa->date;}//到叶子节点
    	        s.pop();//之后走该节点的第三步--判断该节点的右子树，出栈后aa仍有该节点地址
    			if(!aa->rchild)
    			{
    				aa=s.top()->rchild;//之前已经走过s.top节点的左子树
    			    s.pop();//这里也要让叶子节点的父母节点出栈
    			}
    			else {aa=aa->rchild;s.push(aa);cout<<aa->date;}
    		}
    	}
    	void ineordernonrec(binode *aa)//非递归中序遍历
    	{
    		stack<binode *> s;
    		s.push(aa);
    		while(!s.empty())
    		{
    			while(aa->lchild) {aa=aa->lchild;s.push(aa);}
    			cout<<aa->date;s.pop();
    			if(!aa->rchild)
    			{
    				cout<<s.top()->date;
    				aa=s.top()->rchild;
    				s.pop();
    			}
    			else {aa=aa->rchild;s.push(aa);}
    		}
    	}
    	/*从根节点开始遍历左子树到叶子节点，之后要遍历节点的右子树，
    	遍历右子树分为两种情况，第一种右子树为空，可以直接输出，使
    	该节点出栈；第二种情况右子树不空，（之前放入栈中的该节点已
    	经出栈）这时要把该节点第二次放入栈中，这里就需要isfirst来标
    	记，之后按栈中顺序输出。*/
    	void posordernonrec(binode *aa)//非递后先序遍历
    	{
    		stack<binode *> s;
    		s.push(aa);
    		while(!s.empty())
    		{
    			while(!s.top()->isfirst)
    			{
    				cout<<s.top()->date;
    				s.pop();
    			}
    			while(aa->lchild) {aa=aa->lchild;s.push(aa);}//到叶子节点
    			s.pop();
    			if(!aa->rchild)
    			{
    				cout<<aa->date;
    				s.pop();
    			}
    			else 
    			{
    				s.push(aa);
    				aa->isfirst=false;
    				aa=aa->rchild;
    				s.push(aa);
    			}
    		}
    	}
    }
    int main()
    {
    	bitree bb;
    	bb.preordert(bb.getroot());
    	return 0;
    }