直接代码吧,有问题可以讨论,基本都是采用递归的方式求解,创建二叉树,这个例子对于root结点只有左孩子:
#include "stdafx.h" #include<stdlib.h> #include "math.h" #include <iostream> using namespace std; typedef struct BiTreeNode { char data; BiTreeNode *left; BiTreeNode *right; }BiTreeNode,*PBiTreeNode; static int iCnt = 0; void CreateBiTree(PBiTreeNode &Tree)//创建二叉树 { char s[]="ABC$$D$EF$$G$$$"; char ch = s[iCnt++]; if ( ch == ‘$‘ )//$代表不存在 Tree = NULL; else { Tree = (PBiTreeNode)malloc(sizeof(BiTreeNode)); if (!Tree) exit(OVERFLOW); Tree->data = ch; CreateBiTree(Tree->left); CreateBiTree(Tree->right); } } void PreOder(PBiTreeNode Tree)//先序遍历 { if ( !Tree ) return; cout << Tree->data << endl; if ( Tree->left ) PreOder( Tree->left ); if ( Tree->right ) PreOder( Tree->right); } void InOder(PBiTreeNode Tree)//中序遍历 { if ( !Tree ) return; if ( Tree->left ) InOder( Tree->left ); cout << Tree->data << endl; if ( Tree->right ) InOder( Tree->right ); } void PostOder(PBiTreeNode Tree)//后序遍历 { if ( !Tree ) return; if ( Tree->left ) InOder( Tree->left ); if ( Tree->right ) InOder( Tree->right ); cout << Tree->data << endl; } void PrintBiTree(PBiTreeNode Tree)//打印二叉树 { if ( !Tree ) return; cout << Tree->data << endl; if ( Tree->left || Tree->right ) { cout <<"("; PrintBiTree(Tree->left); if ( !Tree->right ) cout <<","; PrintBiTree(Tree->right); cout <<")"; } } int TreeDepth(PBiTreeNode Tree) //二叉树的深度 { int lDepth = 0, rDepth = 0; if ( !Tree ) return 0; lDepth = TreeDepth( Tree->left ); rDepth = TreeDepth( Tree->right ); return lDepth > rDepth ? (lDepth + 1) : (rDepth + 1); } int LeavesNum(PBiTreeNode Tree)//叶子数 { if ( !Tree ) return 0; else if ( !Tree->left && !Tree->right ) return 1; else return LeavesNum( Tree->left ) + LeavesNum( Tree->right ); } void DestroyBiTree(PBiTreeNode &Tree) { if ( !Tree) return; else { DestroyBiTree( Tree->left ); DestroyBiTree( Tree->right); free(Tree); Tree = NULL; } } int main() { PBiTreeNode Tree; CreateBiTree( Tree ); cout <<"输出二叉树:"<<endl; PrintBiTree( Tree ); cout << endl; cout <<"先序遍历结果:"<<endl; PreOder( Tree ); cout <<"中序遍历结果:"<<endl; InOder( Tree ); cout <<"后序遍历结果:"<<endl; PostOder( Tree ); cout <<"树的高度:"<<TreeDepth( Tree )<<endl; cout <<"叶子结点个数:"<< LeavesNum( Tree )<<endl; DestroyBiTree( Tree ); }