二叉树的遍历前序中序后序分别实现递归和非递归遍历方式

水深无声 2022-05-14 04:48 181阅读 0赞

开始复习下数据结构，学习二叉树将二叉树的遍历方式实现了一遍，非递归相对有点难度，通过收集资料最终完成了二叉树的所有遍历方式，做个记录以备后用。废话不说了，贴代码！

1. BinaryTree.h

#ifndef _BINARY_TREE_H_
    #define _BINARY_TREE_H_
    #include <string>
    
    typedef int POS;
    typedef int METHOD;
    typedef std::string String;
    
    enum { LeftChild, RightChild };
    enum { Preorder, Inorder, Postorder };
    
    struct Node
    {
    	String elem;
    	Node* left;
    	Node* right;
    
    	Node() { elem = ""; left = right = NULL; }
    	Node(const String& str) { elem = str; left = right = NULL; }
    };
    
    class BinaryTree
    {
    public:
    	BinaryTree(void);
    	~BinaryTree(void);
    
    public:
    	//@ DESC：输出树
    	//\params: 
    	// method, 为 中序后序前序三种遍历方式，
    	// recursive, 为是否使用递归的方式
    	void     DumpTree( METHOD method, bool recursive = false );
    	//@ DESC：创建一棵树，其实就是初始化了根节点
    	//\params:  
    	// rootContent, 参见Node的定义，其中elem的类型为std::string, 其实就是为了传入根节点的内容
    	void     CreateTree( const String& rootContent );
    	//@ DESC：插入一个节点
    	//\params:
    	// root, 参数node的父节点
    	// node, 要插入的节点
    	// pos, 是左子树还是右子树
    	//@RTRN:返回当前插入的节点，其实就是node
    	Node*    InsertNode( Node* root, Node* node, POS pos );
    	void     Destroy();
    	Node*    Root();
    
    private:
    	void     PreorderDump();
    	void     InorderDump();
    	void     PostOrderDump();
    
    	void     Dump( METHOD method, String info );
    	void     Output( String info );
    
    	void     PreorderR( Node* node );
    	void     InorderR( Node* node );
    	void     PostorderR( Node* node );
    
    private:
    	Node*    m_pRoot;
    };
    
    #endif

2. BianryTreeImp.cpp 二叉树类的实现

#include "BinaryTree.h"
    #include <vector>
    
    // 使用vector实现了一个简单的堆栈，这里偷懒了，
    // 使用链表会更快 
    template <class T>
    class Stack
    {
    public:
    	void Push( const T& t ) { elements.insert( elements.begin(), t ); }
    	T Pop() { T tmp = *(elements.begin());
    			elements.erase( elements.begin() ); return tmp;  }
    	bool IsEmpty() { return elements.empty(); }
    	T Top() { return *(elements.begin()); }
    
    private:
    	std::vector<T> elements;
    };
    
    BinaryTree::BinaryTree(void)
    {
    	m_pRoot = NULL;
    }
    
    
    BinaryTree::~BinaryTree(void)
    {
    	Destroy();
    }
    
    void BinaryTree::CreateTree( const String& rootContent )
    {
    	if ( m_pRoot )
    		Destroy();
    
    	m_pRoot = new Node;
    	m_pRoot->elem = rootContent;
    }
    
    // DESC: 这个函数是不完整的，缺少了对树的所有子节点的内存释放，
    // 这里没写 
    void BinaryTree::Destroy()
    {
    	if ( m_pRoot )
    	{
    		delete m_pRoot;
    		m_pRoot = NULL;
    	}
    }
    
    void BinaryTree::DumpTree( METHOD method, bool recursive )
    {
    	switch( method )
    	{
    	case Preorder:
    		{
    			if ( recursive )
    			{
    				PreorderR( m_pRoot );
    				Output( "\n" );
    			}
    			else
    			{
    				PreorderDump();
    			}
    			break;
    		}
    	case Inorder:
    		{
    			if ( recursive )
    			{
    				InorderR( m_pRoot );
    				Output( "\n" );
    			}
    			else
    			{
    				InorderDump();
    			}
    			break;
    		}
    	case Postorder:
    		{
    			if ( recursive )
    			{
    				PostorderR( m_pRoot );
    				Output( "\n" );
    			}
    			else
    			{
    				PostOrderDump();
    			}
    			break;
    		}
    	}
    }
    
    void BinaryTree::PreorderDump()
    {
    	Node* p = m_pRoot;
    	Stack<Node*> stack;
    	while( p != NULL || !stack.IsEmpty() )
    	{
    		while ( p != NULL )
    		{
    			Output( p->elem );
    			stack.Push( p );
    			p = p->left;
    		}
    
    		if ( !stack.IsEmpty() )
    		{
    			p = stack.Pop();
    			p = p->right;
    		}
    	}
    
    	Output( "\n" );
    }
    
    void BinaryTree::InorderDump()
    {
    	Node* p = m_pRoot;
    	Stack<Node*> stack;
    	while( p != NULL || !stack.IsEmpty() )
    	{
    		if ( p != NULL )
    		{
    			stack.Push( p ); // if has left tree
    			p = p->left;
    		}
    		else // left tree traversed
    		{
    			p = stack.Pop();
    			Output( p->elem );
    			p = p->right;
    		}
    	}
    
    	Output( "\n" );
    }
    
    void BinaryTree::PostOrderDump()
    {
    	Node* p = m_pRoot;
    	Stack<Node*> stack;
    	Node* pPre = NULL;
    	while( p != NULL || !stack.IsEmpty() )
    	{
    		if ( p != NULL )
    		{
    			stack.Push( p ); // if has left tree
    			p = p->left;
    		}
    		else 
    		{
    			p = stack.Top();
    			if ( p->right != NULL && pPre != p->right ) 
    			{
    				p = p->right;
    			}
    			else
    			{
    				p = pPre = stack.Top();
    				Output( p->elem );
    				stack.Pop();
    				p = NULL;
    			}
    		}
    	}
    
    	Output( "\n" );
    }
    
    Node* BinaryTree::InsertNode( Node* root, Node* node, POS pos )
    {
    	switch ( pos )
    	{
    	case LeftChild:
    		{
    			root->left = node;
    			break;
    		}
    	case RightChild:
    		{
    			root->right = node;
    			break;
    		}
    	}
    
    	return node;
    }
    
    Node* BinaryTree::Root()
    {
    	return m_pRoot;
    }
    
    void BinaryTree::Dump( METHOD method, String info )
    {
    	switch( method )
    	{
    	case Preorder:
    		{
    			printf( "Preorder: %s", info.data() );
    			break;
    		}
    	case Inorder:
    		{
    			printf( "Inorder: %s", info.data() );
    			break;
    		}
    	case Postorder:
    		{
    			printf( "Postorder: %s", info.data() );
    			break;
    		}
    	}
    }
    
    void BinaryTree::Output( String info )
    {
    	printf( "%s", info.data() );
    }
    
    void BinaryTree::PreorderR( Node* node )
    {
    	if ( node )
    	{
    		// Visit
    		Output( node->elem );
    
    		PreorderR( node->left );
    		PreorderR( node->right );
    	}
    }
    
    void BinaryTree::InorderR( Node* node )
    {
    	if ( node )
    	{
    		InorderR( node->left );
    
    		// Visit
    		Output( node->elem );
    
    		InorderR( node->right );
    	}
    }
    
    void BinaryTree::PostorderR( Node* node )
    {
    	if ( node )
    	{
    		PostorderR( node->left );
    		PostorderR( node->right );
    
    		// Visit
    		Output( node->elem );
    	}
    }

3. 测试代码

树结构如下图

![1354073055_4991.jpg][]

int _tmain(int argc, _TCHAR* argv[])
    {
    	BinaryTree* pTree = new BinaryTree;
    	pTree->CreateTree( "+" );
    
    	// Construct left child tree
    	Node* pNow = pTree->InsertNode( pTree->Root(), new Node("+"), LeftChild );
    	pTree->InsertNode( pNow, new Node("a"), LeftChild );
    	pNow = pTree->InsertNode( pNow, new Node("*"), RightChild );
    	pTree->InsertNode( pNow, new Node("b"), LeftChild );
    	pTree->InsertNode( pNow, new Node("c"), RightChild );
    
    	// Construct right child tree
    	pNow = pTree->InsertNode( pTree->Root(), new Node("*"), RightChild );
    	pTree->InsertNode( pNow, new Node("g"), RightChild );
    	pNow = pTree->InsertNode( pNow, new Node("+"), LeftChild );
    	pTree->InsertNode( pNow, new Node("f"), RightChild );
    	pNow = pTree->InsertNode( pNow, new Node("*"), LeftChild );
    	pTree->InsertNode( pNow, new Node("d"), LeftChild );
    	pTree->InsertNode( pNow, new Node("e"), RightChild );
    
    	printf( _T("前序:\n") );
    	pTree->DumpTree( Preorder );
    	printf( _T("中序:\n") );
    	pTree->DumpTree( Inorder );
    	printf( _T("后序:\n") );
    	pTree->DumpTree( Postorder );
    
    	delete pTree;
    	pTree = NULL;
    	return 0;
    }

输出

![1354072134_3019.jpg][]

[1354073055_4991.jpg]: https://img-my.csdn.net/uploads/201211/28/1354073055_4991.jpg
[1354072134_3019.jpg]: https://img-my.csdn.net/uploads/201211/28/1354072134_3019.jpg