二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树。以下是对链式存储结构的二叉树的创建与先序、中序、后序遍历操作:
定义二叉树节点
每个节点由三个部分组成:
数据部分
左孩子节点
右孩子节点
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
主函数
声明初始节点时,是BiTree bt,此时bt是节点指针,如果写的是BiTNode bt,则为节点元素。为了传地址操作方便,我们使用声明节点地址的形式。
int main(){
BiTree bt;//指针
initial(&bt);
cout<<"先序创建树(输入#停止生成节点):\n";
createTree(&bt);
cout<<"先序遍历:\n";
preOrder(bt);
cout<<"\n中序遍历:\n";
inOrder(bt);
cout<<"\n后序遍历:\n";
postOrder(bt);
return 0;
}
初始化
我们在主函数里以initial(&bt)的形式调用bt指针,即将指针地址传入初始化函数里。参数里写的是(BiTree bt)表示bt是指向根节点这个节点指针的指针。
此时bt指的是根节点指针,(BiTree)malloc(sizeof(BiTNode))为该节点分配空间。
初始时均无左右孩子,所以设为NULL。
Status initial(BiTree *bt){//指针的指针
*bt = (BiTree)malloc(sizeof(BiTNode));
(*bt)->lchild = NULL;
(*bt)->rchild = NULL;
}
创建二叉树
依然是以指针的指针的形式将节点指针传入函数里
我们设置输入“#”为输入结束。
当输入的元素不是“#”时,为节点指针开辟空间后,将元素赋给该节点的data。
然后递推式创建左右孩子。
Status createTree(BiTree *bt){
ElemType c;
c = getchar();
if(c=='#'){
*bt = NULL;
}else{
*bt = (BiTree)malloc(sizeof(BiTNode));
(*bt)->data = c;
createTree(&(*bt)->lchild);
createTree(&(*bt)->rchild);
}
}
值得注意的是:因为我们使用的是“指针的指针”,所以递推式将创建其左右孩子时,记得是将其左右孩子的地址传入createTree函数里
(即:&(*bt)->child的形式)
关于先序、中序和后序遍历
先序遍历最容易理解:从根节点开始输出,一直向左遍历输出,到尽头后再找到该节点兄弟右节点输出,然后再去到父亲节点的兄弟右节点输出……以此类推。
中序遍历:从左子树的最左边最底层的左孩子节点开始输出,然后输出其父亲节点,再输出其兄弟右节点,然后输出其父亲节点的父亲节点……以此类推。
后序遍历:从左子树的最左边最底层的左孩子节点开始输出,然后输出其兄弟右节点,然后输出其父亲节点,然后输出其父亲节点的熊迪右节点……以此类推。
示例1
我们来创建一个如下图的树:
示例2
示例3
简单粗暴地画法就是遵守这个规律:
文章来源:https://www.toymoban.com/news/detail-753254.html
先序、中序、后序遍历代码实现:
void preOrder(BiTree bt){//指针形参
if(bt!=NULL){
cout<<bt->data<<" ";
preOrder(bt->lchild);
preOrder(bt->rchild);
}
}
void inOrder(BiTree bt){//指针形参
if(bt!=NULL){
inOrder(bt->lchild);
cout<<bt->data<<" ";
inOrder(bt->rchild);
}
}
void postOrder(BiTree bt){//指针形参
if(bt!=NULL){
postOrder(bt->lchild);
postOrder(bt->rchild);
cout<<bt->data<<" ";
}
}
源代码(编程风格参考严蔚敏版《数据结构》)
#include<iostream>
#include<stdio.h>
#include<malloc.h>
using namespace std;
#define MAXSIZE 5
#define ElemType char
#define Status int//表示状态
#define OK 1
#define ERROR 0
#define STOP 0
#define OVERFLOW 0
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status initial(BiTree *bt){//指针的指针
*bt = (BiTree)malloc(sizeof(BiTNode));
(*bt)->lchild = NULL;
(*bt)->rchild = NULL;
}
Status createTree(BiTree *bt){
ElemType c;
c = getchar();
if(c=='#'){
*bt = NULL;
}else{
*bt = (BiTree)malloc(sizeof(BiTNode));
(*bt)->data = c;
createTree(&(*bt)->lchild);
createTree(&(*bt)->rchild);
}
}
void preOrder(BiTree bt){//指针形参
if(bt!=NULL){
cout<<bt->data<<" ";
preOrder(bt->lchild);
preOrder(bt->rchild);
}
}
void inOrder(BiTree bt){//指针形参
if(bt!=NULL){
inOrder(bt->lchild);
cout<<bt->data<<" ";
inOrder(bt->rchild);
}
}
void postOrder(BiTree bt){//指针形参
if(bt!=NULL){
postOrder(bt->lchild);
postOrder(bt->rchild);
cout<<bt->data<<" ";
}
}
int main(){
BiTree bt;//指针
initial(&bt);
cout<<"先序创建树(输入#停止生成节点):\n";
createTree(&bt);
cout<<"先序遍历:\n";
preOrder(bt);
cout<<"\n中序遍历:\n";
inOrder(bt);
cout<<"\n后序遍历:\n";
postOrder(bt);
return 0;
}
敬请批评指正!文章来源地址https://www.toymoban.com/news/detail-753254.html
到了这里,关于数据结构——二叉树的创建与遍历(链式存储结构)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!