Jiang's C++ Space

创作,也是一种学习的过程。

   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

八、树(Tree)

树,顾名思义,长得像一棵树,不过通常我们画成一棵倒过来的树,根在上,叶在下。不说那么多了,图一看就懂:

当然了,引入了树之后,就不得不引入树的一些概念,这些概念我照样尽量用图,谁会记那么多文字?

树这种结构还可以表示成下面这种方式,可见树用来描述包含关系是很不错的,但这种包含关系不得出现交叉重叠区域,否则就不能用树描述了,看图:

面试的时候我们经常被考到的是一种叫“二叉树”的结构,二叉树当然也是树的一种了,它的特点是除了叶以外的节点都有两个子,图:

由此我们还可以推出“三叉树”:

当然还有“四叉树”,“五叉树”,“六叉树”……但太难画了,节点太多,略过。

九、树的遍历(Traversal)

值得再提一下的是二叉树,因为它确实比较特别,节点有两个子,这两个子是有左右之分的,颠倒一下左右,就是不一样的二叉树了,所以左右是不能随便颠倒的。


在第三篇讲到“队”的时候,提及到了广度优先遍历(Breadth-first traversal),除了广度优先遍历之外,还有深度优先遍历(Depth-first Traversal),深度优先遍历又可分为:前序遍历(Preorder Traversal),后序遍历(Postorder Traversal)和中序遍历(Inorder Traversal),其中中序遍历只有对二叉树才有意义,下图解释这几种遍历:

好了,又到代码阶段,写点代码。我看过许多数据结构的教材,二叉树遍历都是必不可少的内容,而且我知道的全部都是用递归实现的,现在,我要求你不用递归,实现对二叉树的中序遍历。怎么办?我给个提示:广度优先遍历时候我们用了队,中序遍历,我们使用*栈*。看看能不能写出来,我也来写:

#include <stdio.h>

// TreeNode
//////////////////////////////////////////////////////////////////////////
struct TreeNode
{
    
char m_cVal;
    TreeNode
* m_pLeft;
    TreeNode
* m_pRight;

    TreeNode(
char cVal);
    
~TreeNode();
};

TreeNode::TreeNode(
char cVal)
{
    m_cVal 
= cVal;
    m_pLeft 
= 0;
    m_pRight 
= 0;
}

TreeNode::
~TreeNode()
{
    
}

//Stack
//////////////////////////////////////////////////////////////////////////
class Stack
{
public:
    Stack(
int iAmount = 10);
    
~Stack();
    
    
//return 1 means succeeded, 0 means failed.
    int Pop(TreeNode* &pVal);
    
int Push(TreeNode* pVal);
    
int Top(TreeNode* &pVal);

    
//1 means not null, 0 means null.
    int NotNull();
private:
    TreeNode 
**m_ppData;
    
int m_iCount;
    
int m_iAmount;
};

Stack::Stack(
int iAmount)
{
    m_ppData 
= new TreeNode*[iAmount];
    m_iCount 
= 0;
    m_iAmount 
= iAmount;
}

Stack::
~Stack()
{
    delete m_ppData;
}

int Stack::Pop(TreeNode* &pVal)
{
    
if(m_iCount>0)
    {
        
--m_iCount;
        pVal 
= m_ppData[m_iCount];
        
return 1;
    }
    
return 0;
}

int Stack::Push(TreeNode* pVal)
{
    
if(m_iCount<m_iAmount)
    {
        m_ppData[m_iCount] 
= pVal;
        
++m_iCount;
        
return 1;
    }
    
return 0;
}

int Stack::Top(TreeNode* &pVal)
{
    
if(m_iCount>0 && m_iCount<=m_iAmount)
    {
        pVal 
= m_ppData[m_iCount-1];
        
return 1;
    }
    
return 0;
}

int Stack::NotNull()
{
    
if(m_iCount!=0)
        
return 1;
    
return 0;
}

int main(int argc, char* argv[])
{
    
//Construct the tree.
    
//      A
    
//    /   \
    
//   /     \
    
//  B       C
    
//   \     / \
    
//    D   E   F
    
//     \       \
    
//      G       H
    
//             / \
    
//            I   J
    
//           / \
    
//          K   L
    TreeNode nA('A');
    TreeNode nB(
'B');
    TreeNode nC(
'C');
    TreeNode nD(
'D');
    TreeNode nE(
'E');
    TreeNode nF(
'F');
    TreeNode nG(
'G');
    TreeNode nH(
'H');
    TreeNode nI(
'I');
    TreeNode nJ(
'J');
    TreeNode nK(
'K');
    TreeNode nL(
'L');

    nA.m_pLeft 
= &nB;
    nA.m_pRight 
= &nC;
    nB.m_pRight 
= &nD;
    nD.m_pRight 
= &nG;
    nC.m_pLeft 
= &nE;
    nC.m_pRight 
= &nF;
    nF.m_pRight 
= &nH;
    nH.m_pLeft 
= &nI;
    nH.m_pRight 
= &nJ;
    nI.m_pLeft 
= &nK;
    nI.m_pRight 
= &nL;

    Stack st;

    
//Inorder traversal
    TreeNode *pVal = &nA;
    
int iPopped = 0;
    
while(pVal!=0)
    {
        
if(pVal->m_pLeft!=0 && iPopped==0)
        {
            st.Push(pVal);
            pVal 
= pVal->m_pLeft;
            iPopped 
= 0;
        }
        
else if(pVal->m_pRight!=0)
        {
            printf(
"%c ", pVal->m_cVal);
            pVal 
= pVal->m_pRight;
            iPopped 
= 0;
        }
        
else
        {
            printf(
"%c ", pVal->m_cVal);
            
if(0==st.Pop(pVal))
                
break;
            iPopped 
= 1;
        }
    }

    
return 0;
}
代码就那么一点,可第一次写的时候我还真觉得颇费脑筋的。代码中有些注释显示不太正常,这是因为这个博客的的代码字体非等宽的缘故,拿到你的IDE下查看就正常了。
(未完待续……)
posted on 2009-10-16 16:24 Jiang Guogang 阅读(3103) 评论(3)  编辑 收藏 引用 所属分类: Knowledge

评论

# re: 图解数据结构(6)——树及树的遍历 2013-04-11 08:32 jiapei100
应该把打印结果给出来...  回复  更多评论
  

# re: 图解数据结构(6)——树及树的遍历 2013-04-11 08:34 jiapei100
哦,是二叉树中序遍历,那就不用给打印结果了... ^_^ Sorry@jiapei100
  回复  更多评论
  

# re: 图解数据结构(6)——树及树的遍历 2013-04-11 08:35 jiapei100
哦,是二叉树中序遍历,那就不用了。^_^  回复  更多评论
  


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