二叉树初步理解
二叉树初步：
代码如下，注释很详细。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iomanip>
#include <ctype.h>
#include <ctime>
#include <stack>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;
//利用结构体去保存每一个节点的各个数据（节点数据、创建左右节点）
typedef struct treeNode//typedef重命名去简化每一次创建结构体时的操作
{
char data;//节点数据
struct treeNode* LChild;//创建左子树
struct treeNode* RChild;//创建右子树
}TREE,*LPTREE;//将创建结构体命名为TREE,创建结构体指针重命名为LPTREE
//创建新节点的函数。(输入新节点的数据)
LPTREE creatNode(char data)
{
//malloc()函数分配内存空间
//sizeof(LPTREE)大小为LPTREE的内存空间
//整个含义：
//分配一个LPTREE类型大小的数据空间给newNode
LPTREE newNode = (LPTREE)malloc(sizeof(TREE));
newNode->data = data;//将新节点的数据输入
newNode->LChild = NULL;//将左子树和右子树初始化为空
newNode->RChild = NULL;
return newNode;//返回数据
}
//插入数据的函数。(完善一个节点左右子树的信息)-做链接
void insertNode(LPTREE parentNode, LPTREE LChild, LPTREE RChild)
{
parentNode->LChild = LChild;//父节点的左边赋值左节点
parentNode->RChild = RChild;//父节点的右边赋值右节点
}
//创建一个打印函数
void printCurNodeData(LPTREE curData)
{
cout << curData->data << " ";
}
//递归法遍历
//先序
void preOrder(LPTREE root)//输入节点
{
if (root != NULL)
{
printCurNodeData(root);//打印根部
preOrder(root->LChild);//递归打印左子树
preOrder(root->RChild);//同上
}
}
//中序
void midOrder(LPTREE root)//输入节点
{
if (root != NULL)
{
preOrder(root->LChild);//递归打印左子树
printCurNodeData(root);//打印根部
preOrder(root->RChild);//同上
}
}
//后序
void lastOrder(LPTREE root)//输入节点
{
if (root != NULL)
{
preOrder(root->LChild);//递归打印左子树
preOrder(root->RChild);//同上
printCurNodeData(root);//打印根部
}
}
int main()
{
//创建A-G节点
LPTREE A = creatNode('A');
LPTREE B = creatNode('B');
LPTREE C = creatNode('C');
LPTREE D = creatNode('D');
LPTREE E = creatNode('E');
LPTREE F = creatNode('F');
LPTREE G = creatNode('G');
//建立连接
insertNode(A, B, C);
insertNode(B, D, NULL);
insertNode(D, NULL, G);
insertNode(C, E, F);
cout << "先序遍历" << endl;
preOrder(A);
cout << endl;
cout << "中序遍历" << endl;
midOrder(A);
cout << endl;
cout << "后序遍历" << endl;
lastOrder(A);
cout << endl;
return 0;
}