二叉链表表示的二叉树和一些基本操作
二叉链表表示的二叉树和一些基本操作
设计不同的结点结构可构成不同形式的链式储存结构。由二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据域和左、右指针域
一下是二叉链表的定义和部分基本操作的函数原型说明：
#ifndef BINARY_LINKED_LIST_TREE_H
#define BINARY_LINKED_LIST_TREE_H
//---------二叉树的二叉链表储存表示-----------
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MYOVERFLOW -2
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
BiTNode *lchild, *rchild;
}*BiTree;
//------------基本操作的函数原型说明（部分）------------
Status CreateBiTree(BiTree &T);
//T表示这个树的根节点的指针
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示的二叉树T
Status VisitBiTree(BiTree);
//输出结点的数据域
Status PreOrderTraverse(BiTree T, Status(*Visit)(BiTree));
//T表示这个树的根节点的指针
//采用二叉链表储存结构，Visit是对结点操作的对应函数
//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit（）失败，则操作失败
Status InOrderTraverse(BiTree T, Status(*Visit)(BiTree));
//T表示这个树的根节点的指针
//采用二叉链表储存结构，Visit是对结点操作的对应函数
//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit（）失败，则操作失败
Status InOrderTraverse_2(BiTree T, Status(*Visit)(BiTree));
//采用二叉链表储存结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
Status InOrderTraverse_3(BiTree T, Status(*Visit)(BiTree));
//采用二叉链表储存结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
Status PostOrderTraverse(BiTree T, Status(*Visit)(BiTree));
//T表示这个树的根节点的指针
//采用二叉链表储存结构，Visit是对结点操作的对应函数
//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit（）失败，则操作失败
Status LevelOrderTraverse(BiTree T, Status(*Visit)(BiTree));
//T表示这个树的根节点的指针
//采用二叉链表储存结构，Visit是对结点操作的对应函数
//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit（）失败，则操作失败
Status Destroy(BiTree T);//摧毁T这个节点
Status DestroyBiTree(BiTree &T);
//摧毁二叉树T
#endif
在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就提出了一个遍历二叉树的问题，即如何按某条搜索路径寻访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。二叉树的遍历又有很多情况，其中先序、中序、后序、层序遍历是常见的情况
上述操作的实现：
#include"stdafx.h"
#include"ADT.h"
#include<deque>
#include<stack>
//------------基本操作的函数原型说明（部分）------------
Status CreateBiTree(BiTree &T)
//T表示这个树的根节点的指针
//按先序次序输入二叉树中结点的值（一个字符），字符为空表示空树，
//构造二叉链表表示的二叉树T
{
char ch;
ch = getchar();
if (ch == ' '){
T = NULL; return OK;
}
else
{
if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))exit(MYOVERFLOW);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
Status VisitBiTree(BiTree T)
//输出结点的数据域
{
cout << T->data << " ";
return OK;
}
Status Destroy(BiTree T){//摧毁T这个节点
if (T){
free(T);
}
return OK;
}
Status PreOrderTraverse(BiTree T, Status(*Visit)(BiTree))
//T表示这个树的根节点的指针
//采用二叉链表储存结构，Visit是对结点操作的对应函数
//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit（）失败，则操作失败
{
if (T){
BiTree lchild = T->lchild, rchild = T->rchild;
if(Visit(T))
if (PreOrderTraverse(lchild,Visit))
if (PreOrderTraverse(rchild, Visit))return OK;
return ERROR;
}
return OK;
}
Status InOrderTraverse(BiTree T, Status(*Visit)(BiTree))
//T表示这个树的根节点的指针
//采用二叉链表储存结构，Visit是对结点操作的对应函数
//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit（）失败，则操作失败
{
if (T){
BiTree lchild = T->lchild, rchild = T->rchild;
if (InOrderTraverse(lchild, Visit))
if (Visit(T))
if (InOrderTraverse(rchild, Visit))return OK;
return ERROR;
}
return OK;
}
Status InOrderTraverse_2(BiTree T, Status(*Visit)(BiTree))
//采用二叉链表储存结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
{
stack<BiTree> sta;
sta.push(T);
BiTree p;
while (!sta.empty()){
while (p = sta.top())sta.push(p->lchild);
sta.pop();
if (!sta.empty()){
p = sta.top();
sta.pop();
if (!Visit(p))return ERROR;
sta.push(p->rchild);
}
}
return OK;
}
Status InOrderTraverse_3(BiTree T, Status(*Visit)(BiTree))
//采用二叉链表储存结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
{
stack<BiTree> sta;
BiTree p = T;
while (p || !sta.empty()){
if (p){ sta.push(p); p = p->lchild; }
else{
p = sta.top();
sta.pop();
if (!Visit(p))return ERROR;
p = p->rchild;
}
}
return OK;
}
Status PostOrderTraverse(BiTree T, Status(*Visit)(BiTree))
//T表示这个树的根节点的指针
//采用二叉链表储存结构，Visit是对结点操作的对应函数
//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit（）失败，则操作失败
{
if (T){
BiTree lchild = T->lchild, rchild = T->rchild;
if (PostOrderTraverse(lchild, Visit))
if (PostOrderTraverse(rchild, Visit))
if (Visit(T))return OK;
return ERROR;
}
return OK;
}
Status LevelOrderTraverse(BiTree T, Status(*Visit)(BiTree))
//T表示这个树的根节点的指针
//采用二叉链表储存结构，Visit是对结点操作的对应函数
//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit（）失败，则操作失败
{
deque<BiTree> deq;
if (T){
deq.push_back(T);
while (!deq.empty()){
auto temp = deq.at(0);
Visit(temp);
if (temp->lchild)
deq.push_back(temp->lchild);
if (temp->rchild)
deq.push_back(temp->rchild);
deq.pop_front();
}
}
cout << endl;
return OK;
}
Status DestroyBiTree(BiTree &T)
//摧毁二叉树T
{
if (PreOrderTraverse(T, Destroy))return OK;
return FALSE;
}
主函数：
// 二叉链表.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
BiTree T;
cout << "中序输入二叉树，如果某个节点的左右子树为空，则输入两个空格：" << endl;
CreateBiTree(T);
cout << "先序遍历" << endl;
PreOrderTraverse(T, VisitBiTree);
cout << endl;
cout << "中序遍历"<<endl;
InOrderTraverse(T, VisitBiTree);
cout << endl;
InOrderTraverse_2(T, VisitBiTree);
cout << endl;
InOrderTraverse_3(T, VisitBiTree);
cout << endl;
cout << "后序遍历"<<endl;
PostOrderTraverse(T, VisitBiTree);
cout << endl;
cout << "层序遍历"<<endl;
LevelOrderTraverse(T, VisitBiTree);
DestroyBiTree(T);
return 0;
}
结果：（在vs2013中实现，注意要在stadfx.h中包含相应的头文件）
二叉树的常见问题及其解决程序
【递归】二叉树的先序建立及遍历
在JAVA中实现的二叉树结构
【非递归】二叉树的建立及遍历
二叉树递归实现与二重指针
二叉树先序中序非递归算法
轻松搞定面试中的二叉树题目
本文永久更新链接地址：
评论暂时关闭