那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)

费了两天时间写的,包括前中后序遍历的递归和非递归算法,还有层序遍历总共2*3 + 1 = 7中遍历二叉树的算法,感觉其中后序遍历的非递归算法比较困难,想了很久最后的实现还是不够优雅,请大家指正~~

总共三个文件,一个头文件,一个对应的cpp文件,还有一个用于测试的文件.

头文件:
/********************************************************************
    created:    2006/07/04
    filename:     BinaryTree.h
    author:        李创
                
http://www.cppblog.com/converse/

    purpose:    演示二叉树的算法
********************************************************************
*/


#ifndef BinaryTree_H
#define BinaryTree_H

#include 
<stdlib.h>
#include 
<stack>

class BinaryTree
{
private:
    typedef 
int Item;
    typedef 
struct TreeNode
    
{
        Item        Node;
        TreeNode
*   pRight;
        TreeNode
*   pLeft;

        TreeNode(Item node 
= 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
            : Node(node)
            , pRight(pright)
            , pLeft(pleft)
        
{
        }


    }
TreeNode, *PTreeNode;

public:
    
enum TraverseType
    
{
        PREORDER    
= 0,        // 前序
        INORDER        = 1,        // 中序
        POSTORDER    = 2,        // 后序
        LEVELORDER    = 3            // 层序
    }
;

    BinaryTree(Item Array[], 
int nLength);
    
~BinaryTree();

    PTreeNode GetRoot()
    
{
        
return m_pRoot;
    }


    
// 遍历树的对外接口
    
// 指定遍历类型和是否是非递归遍历,默认是递归遍历
    void Traverse(TraverseType traversetype, bool bRec = true);

private:
    PTreeNode   CreateTreeImpl(Item Array[], 
int nLength);
    
void        DetroyTreeImpl(PTreeNode pTreenode);

    
void        PreTraverseImpl(PTreeNode pTreenode);        // 递归前序遍历树
    void        InTraverseImpl(PTreeNode pTreenode);        // 递归中序遍历树
    void        PostTraverseImpl(PTreeNode pTreenode);        // 递归后序遍历树

    
void        NoRecPreTraverseImpl(PTreeNode pTreenode);    // 非递归前序遍历树
    void        NoRecInTraverseImpl(PTreeNode pTreenode);    // 非递归中序遍历树
    void        NoRecPostTraverseImpl(PTreeNode pTreenode);    // 非递归后序遍历树

    
void        LevelTraverseImpl(PTreeNode pTreenode);

    PTreeNode   m_pRoot;        
// 根结点

    
// 采用STL里面的stack作为模拟保存链表结点的stack容器
    typedef std::stack<BinaryTree::PTreeNode> TreeNodeStack;
}
;

#endif


实现文件:
/********************************************************************
    created:    2006/07/04
    filename:     BinaryTree.cpp
    author:        李创
                
http://www.cppblog.com/converse/

    purpose:    演示二叉树的算法
********************************************************************
*/


#include 
<iostream>
#include 
<assert.h>
#include 
<queue>
#include 
"BinaryTree.h"

BinaryTree::BinaryTree(Item Array[], 
int nLength)
    : m_pRoot(NULL)
{
    assert(NULL 
!= Array);
    assert(nLength 
> 0);

    m_pRoot 
= CreateTreeImpl(Array, nLength);
}


BinaryTree::
~BinaryTree()
{
    DetroyTreeImpl(m_pRoot);
}


// 按照中序递归创建树
BinaryTree::PTreeNode BinaryTree::CreateTreeImpl(Item Array[], int nLength)
{
    
int mid = nLength / 2;
    PTreeNode p 
= new TreeNode(Array[mid]);

    
if (nLength > 1)
    
{
        p
->pLeft    = CreateTreeImpl(Array, nLength / 2);
        p
->pRight   = CreateTreeImpl(Array + mid + 1, nLength / 2 - 1);
    }


    
return p;
}


void BinaryTree::DetroyTreeImpl(PTreeNode pTreenode)
{
    
if (NULL != pTreenode->pLeft)
    
{
        DetroyTreeImpl(pTreenode
->pLeft);
    }

    
if (NULL != pTreenode->pRight)
    
{
        DetroyTreeImpl(pTreenode
->pRight);
    }


    delete pTreenode;
    pTreenode 
= NULL;
}


// 遍历树的对外接口
// 指定遍历类型和是否是非递归遍历,默认是递归遍历
void BinaryTree::Traverse(TraverseType traversetype, bool bRec /*= true*/)
{
    
switch (traversetype)
    
{
    
case PREORDER:    // 前序
        {            
            
if (true == bRec)
            
{
                std::cout 
<< "递归前序遍历树\n";
                PreTraverseImpl(m_pRoot);
            }

            
else
            
{
                std::cout 
<< "非递归前序遍历树\n";
                NoRecPreTraverseImpl(m_pRoot);
            }

        }

        
break;

    
case INORDER:    // 中序
        {            
            
if (true == bRec)
            
{
                std::cout 
<< "递归中序遍历树\n";
                InTraverseImpl(m_pRoot);
            }

            
else
            
{
                std::cout 
<< "非递归中序遍历树\n";
                NoRecInTraverseImpl(m_pRoot);
            }

        }

        
break;

    
case POSTORDER:    // 后序
        {            
            
if (true == bRec)
            
{
                std::cout 
<< "递归后序遍历树\n";
                PostTraverseImpl(m_pRoot);
            }

            
else
            
{
                std::cout 
<< "非递归后序遍历树\n";
                NoRecPostTraverseImpl(m_pRoot);
            }

        }

        
break;

    
case LEVELORDER:    // 层序
        {
            std::cout 
<< "层序遍历树\n";
            LevelTraverseImpl(m_pRoot);
        }

    }


    std::cout 
<< std::endl;
}


// 递归前序遍历树
void BinaryTree::PreTraverseImpl(PTreeNode pTreenode)
{
    
if (NULL == pTreenode)
        
return;

    std::cout 
<< "Item = " << pTreenode->Node << std::endl;

    PreTraverseImpl(pTreenode
->pLeft);

    PreTraverseImpl(pTreenode
->pRight);
}


// 非递归前序遍历树
void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)
{
    
if (NULL == pTreenode)
        
return;

    TreeNodeStack NodeStack;
    PTreeNode pNode;
    NodeStack.push(pTreenode);

    
while (!NodeStack.empty())
    
{
        
while (NULL != (pNode = NodeStack.top()))    // 向左走到尽头
        {
            std::cout 
<< "Item = " << pNode->Node << std::endl;    // 访问当前结点
            NodeStack.push(pNode->pLeft);                    // 左子树根结点入栈
        }

        NodeStack.pop();                                    
// 左子树根结点退栈
        if (!NodeStack.empty())
        
{
            pNode 
= NodeStack.top();
            NodeStack.pop();                                
// 当前结点退栈
            NodeStack.push(pNode->pRight);                // 当前结点的右子树根结点入栈
        }

    }

}


// 中序遍历树
// 中序遍历输出的结果应该和用来初始化树的数组的排列顺序一致
void BinaryTree::InTraverseImpl(PTreeNode pTreenode)
{
    
if (NULL == pTreenode)
        
return;

    
if (NULL != pTreenode->pLeft)
    
{
        InTraverseImpl(pTreenode
->pLeft);
    }


    std::cout 
<< "Item = " << pTreenode->Node << std::endl;

    
if (NULL != pTreenode->pRight)
    
{
        InTraverseImpl(pTreenode
->pRight);
    }

}


// 非递归中序遍历树
void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)
{
    
if (NULL == pTreenode)
        
return;

    TreeNodeStack NodeStack;
    PTreeNode pNode;
    NodeStack.push(pTreenode);

    
while (!NodeStack.empty())
    
{
        
while (NULL != (pNode = NodeStack.top()))    // 向左走到尽头
        {
            NodeStack.push(pNode
->pLeft);
        }


        NodeStack.pop();

        
if (!NodeStack.empty() && NULL != (pNode = NodeStack.top()))
        
{
            std::cout 
<< "Item = " << pNode->Node << std::endl;
            NodeStack.pop();
            NodeStack.push(pNode
->pRight);
        }

    }

}


// 后序遍历树
void BinaryTree::PostTraverseImpl(PTreeNode pTreenode)
{
    
if (NULL == pTreenode)
        
return;

    
if (NULL != pTreenode->pLeft)
    
{
        PostTraverseImpl(pTreenode
->pLeft);
    }


    
if (NULL != pTreenode->pRight)
    
{
        PostTraverseImpl(pTreenode
->pRight);
    }


    std::cout 
<< "Item = " << pTreenode->Node << std::endl;
}


// 非递归后序遍历树
void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)
{
    
if (NULL == pTreenode)
        
return;

    TreeNodeStack NodeStack;
    PTreeNode pNode1, pNode2;
    NodeStack.push(pTreenode);
    pNode1 
= pTreenode->pLeft;
    
    
bool bVisitRoot = false;            // 标志位,是否访问过根结点
    while (!NodeStack.empty())
    
{
        
while (NULL != pNode1)            // 向左走到尽头
        {
            NodeStack.push(pNode1);
            pNode1 
= pNode1->pLeft;
        }


        pNode1 
= NodeStack.top();
        NodeStack.pop();

        
if (NULL == pNode1->pRight)            // 如果没有右子树就是叶子结点
        {
            std::cout 
<< "Item = " << pNode1->Node << std::endl;
            pNode2 
= pNode1;
            pNode1 
= NodeStack.top();

            
if (pNode2 == pNode1->pRight)    // 如果这个叶子结点是右子树
            {
                std::cout 
<< "Item = " << pNode1->Node << std::endl;
                NodeStack.pop();
                pNode1 
= NULL;
            }

            
else                            // 否则访问右子树
            {
                pNode1 
= pNode1->pRight;
            }

        }

        
else                                // 访问右子树
        {
            
if (pNode1 == pTreenode && true == bVisitRoot)    // 如果已经访问过右子树那么就退出
            {
                std::cout 
<< "Item = " << pNode1->Node << std::endl;
                
return;
            }

            
else
            
{
                
if (pNode1 == pTreenode)
                
{
                    bVisitRoot 
= true;
                }


                NodeStack.push(pNode1);
                pNode1 
= pNode1->pRight;
            }

        }

    }

}


// 按照树的层次从左到右访问树的结点
void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode)
{
    
if (NULL == pTreenode)
        
return;

    
// 层序遍历用于保存结点的容器是队列
    std::queue<PTreeNode> NodeQueue;
    PTreeNode pNode;
    NodeQueue.push(pTreenode);

    
while (!NodeQueue.empty())
    
{
        pNode 
= NodeQueue.front();
        NodeQueue.pop();
        std::cout 
<< "Item = " << pNode->Node << std::endl;

        
if (NULL != pNode->pLeft)
        
{
            NodeQueue.push(pNode
->pLeft);    
        }

        
if (NULL != pNode->pRight)
        
{
            NodeQueue.push(pNode
->pRight);
        }
    
    }

}

测试文件:
/********************************************************************
    created:    2006/07/04
    filename:     main.cpp
    author:        李创
                
http://www.cppblog.com/converse/

    purpose:    测试二叉树的算法
********************************************************************
*/


#include 
"BinaryTree.h"

#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<time.h>
#include 
<iostream>

void DisplayArray(int array[], int length)
{
    
int i;

    
for (i = 0; i < length; i++)
    
{
        printf(
"array[%d] = %d\n", i, array[i]);
    }

}


void CreateNewArray(int array[], int length)
{
    
for (int i = 0; i < length; i++)
    
{
        array[i] 
= rand() % 256 + i;
    }

}


int main()
{
    
int array[10];
    srand(time(NULL));

    
// 创建数组
    CreateNewArray(array, 10);
    DisplayArray(array, 
10);

    BinaryTree 
*pTree = new BinaryTree(array, 10);

    
// 测试前序遍历
    pTree->Traverse(BinaryTree::PREORDER);
    std::cout 
<< "root = " << pTree->GetRoot()->Node << std::endl;
    std::cout 
<< "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
    std::cout 
<< "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
    pTree
->Traverse(BinaryTree::PREORDER, false);
    
    
// 测试中序遍历
    pTree->Traverse(BinaryTree::INORDER);
    std::cout 
<< "root = " << pTree->GetRoot()->Node << std::endl;
    std::cout 
<< "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
    std::cout 
<< "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
    pTree
->Traverse(BinaryTree::INORDER, false);
    
// 测试后序遍历
    pTree->Traverse(BinaryTree::POSTORDER);
    std::cout 
<< "root = " << pTree->GetRoot()->Node << std::endl;
    std::cout 
<< "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
    std::cout 
<< "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
    pTree
->Traverse(BinaryTree::POSTORDER, false);
    
// 测试层序遍历
    pTree->Traverse(BinaryTree::LEVELORDER);

    system(
"pause");
    
    delete pTree;

    
return 0;
}

posted on 2006-07-08 15:21 那谁 阅读(20185) 评论(9)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)  回复  更多评论   

good
2007-06-16 18:04 | superdaxia

# re: 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)  回复  更多评论   

你好,我是新手,在用VC调试时发现错误
f:\hwh\二叉树\binarytree.h(64) : error C2027: use of undefined type 'BinaryTree'
f:\hwh\二叉树\binarytree.h(8) : see declaration of 'BinaryTree'
main.cpp
f:\hwh\二叉树\binarytree.h(64) : error C2027: use of undefined type 'BinaryTree'
f:\hwh\二叉树\binarytree.h(8) : see declaration of 'BinaryTree'
执行 cl.exe 时出错.

二叉树.exe - 1 error(s), 0 warning(s)
为什么呢?
2007-12-25 11:37 | tomy

# re: 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)  回复  更多评论   

@tomy
你用的什么编译器?我用的VS2003,其次,你的工程里面有几个文件?这里一共有三个文件:binarytree.h,binarytree.cpp,main.cpp
2007-12-26 11:18 | 创系

# re: 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)[未登录]  回复  更多评论   

我用DEV C++编译后报以下信息,请指教:

C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp/cceIaaaa.o(.text+0x52d):main.cpp: undefined reference to `BinaryTree::Traverse(BinaryTree::TraverseType, bool)'
C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp/cceIaaaa.o(.text+0x62f):main.cpp: more undefined references to `BinaryTree::Traverse(BinaryTree::TraverseType, bool)' follow
C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp/cceIaaaa.o(.text+0x676):main.cpp: undefined reference to `BinaryTree::~BinaryTree()'
collect2: ld returned 1 exit status
2008-01-06 01:10 | ben

# re: 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)  回复  更多评论   

楼上的错误是DEV C++的工程文件/配置文件的问题吧?

# re: 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)[未登录]  回复  更多评论   

已经解决了,谢谢指点!
2008-01-06 15:19 | ben

# re: 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)  回复  更多评论   

请问,为什么我的窗口上什么都米有?只有一个“请按任意键继续”,用的是VC++ 2008
2008-07-09 07:03 | liuyu

# re: 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)  回复  更多评论   

其实如果不用 Stack 而改用 List 的话,三种非递归遍历将变得更加简单一致,一个 While 就够了

typedef std::list<BinaryTree::PTreeNode> TreeNodeList;

typedef struct TreeNode
{
Item Node;
TreeNode* pRight;
TreeNode* pLeft;
bool bVisited; // 关键

TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
: Node(node)
, pRight(pright)
, pLeft(pleft)
, bVisited(false)
{
}

}TreeNode, *PTreeNode;




// 非递归前序遍历树
void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeList NodeList;
PTreeNode pNode;
NodeList.push_front(pTreenode);

while (!NodeList.empty())
{
pNode = NodeList.front();
NodeList.pop_front();

std::cout << "Item = " << pNode->Node << std::endl;

if(pNode->pRight != NULL) NodeList.push_front(pNode->pRight);
if(pNode->pLeft != NULL) NodeList.push_front(pNode->pLeft);
}
}


// 非递归中序遍历树
void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeList NodeList;
PTreeNode pNode;
NodeList.push_front(pTreenode);

while (!NodeList.empty())
{
pNode = NodeList.front();

if(pNode->bVisited)
{
NodeList.pop_front();
pNode->bVisited = false; // 为下一次遍历做准备

std::cout << "Item = " << pNode->Node << std::endl;

if(pNode->pRight != NULL) NodeList.push_front(pNode->pRight);
}
else
{
if(pNode->pLeft != NULL) NodeList.push_front(pNode->pLeft);
pNode->bVisited = true;
}

}
}

// 非递归后序遍历树
void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeList NodeList;
PTreeNode pNode;
NodeList.push_front(pTreenode);

while (!NodeList.empty())
{
pNode = NodeList.front();

if(pNode->bVisited)
{
NodeList.pop_front();
pNode->bVisited = false; // 为下一次遍历做准备

std::cout << "Item = " << pNode->Node << std::endl;
}
else
{
if(pNode->pRight != NULL) NodeList.push_front(pNode->pRight);
if(pNode->pLeft != NULL) NodeList.push_front(pNode->pLeft);
pNode->bVisited = true;
}

}
}


2008-09-08 22:58 | Godspeed

# re: 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)[未登录]  回复  更多评论   

非递归后续遍历修改为:
public static void iterativePostorder(BinaryTree boot) {
Stack<BinaryTree> stack = new Stack<BinaryTree>();
BinaryTree current, pointer=boot;
boolean bVisitRoot = false;//标志是否访问过根节点
if (boot == null) {
return;
}
stack.push(boot);
current = boot.leftpoiter;
while (!stack.empty()) {
while (current != null) {//向左走到尽头
stack.push(current);
current = current.leftpoiter;
}
current = stack.peek();
stack.pop();
if ((current.rightpoiter == null)||(pointer == current.rightpoiter)) {
visit(current);
pointer = current;
current = stack.peek();
if (pointer == current.rightpoiter) {
visit(current);
stack.pop();
pointer=current;
current = null;
} else {
current = current.rightpoiter;
}
} else {
if (current == boot && (bVisitRoot == true)) {
visit(current);
return;
} else {
if (current == boot) {
bVisitRoot = true;
}
stack.push(current);
current = current.rightpoiter;
}
}

}

}
2011-07-07 11:12 | hepeng

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理