二叉树简单实现(创建、遍历、叶子数等)

      直接代码吧,有问题可以讨论,基本都是采用递归的方式求解,创建二叉树,这个例子对于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 );
}


二叉树简单实现(创建、遍历、叶子数等)

上一篇:移动端调试


下一篇:MySql--基本查询语句