二叉树的基本操作实现（建立、先序、中序、后序、层序）

2023-09-10 06:22| 来源: 网络整理| 查看: 265

[问题描述]

建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；

[基本要求]

从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），

[测试数据]

如输入：ABC##DE#G##F###（其中#表示空格字符）则输出结果为：

先序：ABCDEGF

中序：CBEGDFA

后序：CGEFDBA

层序：ABCDEFG

----------------------------------------------------------------我是分割线--------------------------------------------------------------------------------

【二叉树定义】

二叉树是n(n>=0)个结点所构成的集合，n=0时为空树，n>0为非空树。对于非空树T：

1.有且仅有一个称为根的结点；

2.除根节点外其余结点分为两个互不相交的子集T1，T2，分别称为T的左子树，右子树

二叉树与树一样具有递归性质，二叉树每个结点至多两颗子树，子树有左右之分，次序不可颠倒。

【存储结构】

1.顺序存储结构

#define MAXSIZE 100 typedef TElemType SqBiTree[MAXSIZE];//0号单元存储根节点，TElemType可换成自己需要的类型如char SqBiTree bt;

2.链式存储结构

typedef struct BiTNode { char data;//结点数据域 BiTNode *lchild, *rchild;//左右孩子指针 }BiTNode,*BiTree;

顺序存储结构只适用完全二叉树，一般采用链式。

【先序创建二叉链表】

void CreateBiTree(BiTree&T)//先序遍历的顺序建立二叉表 { char ch; cin >> ch;//输入的字符串会进入缓冲区， if (ch == '#')//ch为字符型，（ch=="#")错误 T = NULL;//递归结束，创建空树 else//递归创建二叉树 { T = new BiTNode;//生成根节点 T->data = ch;//将ch赋值给数据域 CreateBiTree(T->lchild);//递归创建左子树 CreateBiTree(T->rchild);//递归创建右子树 } }

【先序遍历】

void PreOrderTraverse(BiTree T)//先序遍历 { if (T)//若二叉树非空 { cout data;//访问根节点 PreOrderTraverse(T->lchild);//先序遍历左子树 PreOrderTraverse(T->rchild);//先序遍历右子树 } }

先中后序类似，先序是根左右，中序左根右，后序左右根，只要改变访问根节点顺序就行，具体代码在下面。

【层序遍历】

void SeqOrderTraverse(BiTree T)//层序遍历 { SqQueue q; InitQueue(q); EnQueue(q, T); while (q.rear!=q.front) { BiTree root = OutQueue(q); cout data lchild) EnQueue(q, root->lchild); if (root->rchild) EnQueue(q, root->rchild); } cout > ch;//输入的字符串会进入缓冲区， if (ch == '#')//ch为字符型，（ch=="#")错误 T = NULL;//递归结束，创建空树 else//递归创建二叉树 { T = new BiTNode;//生成根节点 T->data = ch;//将ch赋值给数据域 CreateBiTree(T->lchild);//递归创建左子树 CreateBiTree(T->rchild);//递归创建右子树 } } void PreOrderTraverse(BiTree T)//先序遍历 { if (T)//若二叉树非空 { cout data lchild);//先序遍历左子树 PreOrderTraverse(T->rchild);//先序遍历右子树 } } void InOrderTraverse(BiTree T)//中序遍历 { if (T) { InOrderTraverse(T->lchild); cout data rchild); } } void PostOrderTraverse(BiTree T)//后序遍历 { if (T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout data lchild); if (root->rchild) EnQueue(q, root->rchild); } cout

【本文地址】

公司简介

联系我们