二叉樹的建立和遍歷

題目描述

已知一個按先序序列輸入的字符序列，如abc,,de,g,,f,,,(其中逗號表示空節點)。請建立二叉樹並按中序和後序方式遍歷二叉樹，最後求出葉子節點個數和二叉樹深度。

輸入

輸入一個長度小於50個字符的字符串。

輸出

輸出共有4行：

第1行輸出中序遍歷序列；

第2行輸出後序遍歷序列；

第3行輸出葉子節點個數；

第4行輸出二叉樹深度。

示例輸入

abc,,de,g,,f,,,

示例輸出

cbegdfa

cgefdba

3

5

#include <iostream>
using namespace std;
typedef char Elem_Type;
typedef struct BiTNode
{
Elem_Type data;
BiTNode *lchild;
BiTNode *rchild;
}BiTNode;
void CreateBiTree(BiTNode **root)
{
Elem_Type temp;
cin>>temp;
if(temp == ',')
*root = NULL;
else
{
*root = new BiTNode;
(*root)->data = temp;
CreateBiTree( &(*root)->lchild );
CreateBiTree( &(*root)->rchild );
}
}
void InOrderTraverse(BiTNode *root)//中
{
if( root )
{
InOrderTraverse( root->lchild);
cout<<root->data;
InOrderTraverse( root->rchild);
}
}
void PostOrderTraverse(BiTNode *root)
{
if( root )
{
PostOrderTraverse( root->lchild);
PostOrderTraverse( root->rchild);
cout<<root->data;
}
}
int LeafNodes( BiTNode *root)
{
static int count =0;
if( !root )
return 0;
if( !root->lchild && !root->rchild)
count++;
LeafNodes(root->lchild);
LeafNodes(root->rchild);
return count;
}
int BiTreeDepth(BiTNode *root)
{
if( !root )
return 0;
return (BiTreeDepth(root->lchild) > BiTreeDepth(root->rchild)?
BiTreeDepth(root->lchild) : BiTreeDepth(root->rchild)) + 1;
}
int main(void)
{
BiTNode *root = NULL;
CreateBiTree(&root);
InOrderTraverse(root);
cout<<endl;
PostOrderTraverse(root);
cout<<endl;
cout<<LeafNodes( root)<<endl;
cout<<BiTreeDepth(root)<<endl;
return 0;
}
/**************************************
Problem id : SDUT OJ 2136
User name : 李俊
Result : Accepted
Take Memory : 456K
Take Time : 10MS
Submit Time : 2014-05-05 23:13:18
**************************************/

二叉樹的常見問題及其解決程序 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