歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

層次遍歷二叉樹

按先序序列輸入字符序列(其中逗號表示空節點),輸出該二叉樹的層次遍歷序列。

#include <iostream>
#define END ','//表示空節點
using namespace std;
typedef char Elem_Type;
typedef struct BiTree
{
    Elem_Type data;
    struct BiTree *Lchild;
    struct BiTree *Rchild;
}BiTree;
BiTree *CreateBiTree(void)
{
    Elem_Type value;cin>>value;
    if(value == END)
      return NULL;
    BiTree *root = new BiTree;
    root->data = value;
    root->Lchild = CreateBiTree();
    root->Rchild = CreateBiTree();
    return root;
}
int BiTreeDepth(BiTree *root)
{
    if( !root )
      return 0;
    return max( BiTreeDepth(root->Lchild),BiTreeDepth(root->Rchild) ) + 1;
}
void PrintBiTree(BiTree *root,int level)
{
    if( !root )//不寫這個會有段錯誤發生
      return;
    if(level == 1 )
      cout<<root->data;
    else
    {
        PrintBiTree(root->Lchild,level - 1);
        PrintBiTree(root->Rchild,level - 1);
    }
}
void LeveOrderTraverse(BiTree *root)
{
    int depth = BiTreeDepth(root);
    for(int i=1; i <= depth; i++)
    {
        PrintBiTree(root,i);
        cout<<endl;
    }
}
int main(void)
{
    BiTree *root = CreateBiTree();
    LeveOrderTraverse(root);
    return 0;
}

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

Copyright © Linux教程網 All Rights Reserved