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

本文主要是介绍二叉树简单实现（创建、遍历、叶子数等），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

这篇关于二叉树简单实现（创建、遍历、叶子数等）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---