理解二叉树的链式结构的存储
实现二叉树的基本函数
理解二叉树的遍历过程
能够针对递归结构的二叉树进行查询、修改、删除等操作
一、 设计要求：
设计一棵二叉树，要求不少于4层，10个结点。并用Word绘出设计的二叉树。
编程实现按照凹入法打印该树。
编程打印该树的先序，中序，后序遍历序列。
编程打印该树的层次遍历序列。
交换该树的左右子树。
输入待删除的节点内容，要求删除该节点子树，并打印删除后的二叉树。
按照凹入表示法打印交换左右子树后的树。
二、 算法描述：
算法1：二叉树的遍历算法均为递归算法，以先序遍历为例。
Void preOrderTraverse()
{
先序遍历根结点；
先序遍历左子树；
先序遍历右子树；
}
算法2：二叉树的构造算法。
Void creatBiTree()
{
输入一个字符//代表树的结点的内容
如果字符为'*',则该节点表示空树，且为其双亲的左空孩子,
如果是'#',则该节点也表示空树，是为其双亲的右空孩子。
若是空孩子则当前指针的双亲的相应孩子置空。
否则，申请一个二叉树的结点，并把该字符赋给树的结点。
为左子树申请空间，创建左子树。
为右子树申请空间，创建右子树。
}
算法3：层次遍历算法。
Void leveOrderTraverse()
{
申请一个队列。
只要当前指针非空执行下列操作：
当前指针入队；
只要对不空执行下列操作：
出队，输出出队的结点数据；
如果出队的结点左孩子非空，左孩子入队；右孩子同样操作。
}
算法4:删除二叉树结点的算法。
Void destroyBiTree(TElemType e，孩子类型)
{//采用先序遍历搜索，找到关键字后相应指针置空
//孩子类型用于判断待删除结点是左孩子还是右孩子
当前指针非空；
如果是左孩子，并且关键字查找正确，则当前指针双亲的左孩子置空。
如果是右孩子，并且关键字查找正确，则当前指针双亲的右孩子置空。
如果是根结点，并且关键字查找正确，则当前指针双亲的左右孩子均置空。
}
三、 类/变量说明：
二叉树类：
class BiTree{
public:
BiTree()//构造函数，构造一棵空的二叉树
void creatBiTree();// 构造链式的二叉树 T
void preOrderTraverse(int);
// 先序遍历输出二叉树T.凹入法打印
void inOrderTraverse();
// 中序遍历输出二叉树T.
void postOrderTraverse();
// 后序遍历输出二叉树T.
void leveOrderTraverse();
// 层次遍历二叉树T.
void swapChild();
// 交换左右孩子
void destroyBiTree(TElemType,CHILD);
// 销毁一棵树
private:
TElemType data; // 结点（字符型）
BiTree *parent, *lchild, *rchild; // 双亲，左孩子和又孩子
};
队列类：（队列指针类的友元）
class QueueNode
{//队列结点
private:
friend class LinkQueue;
QElemType data;
QueueNode *next;
public:
QueueNode(QElemType e)//构造结点为e的队列
QueueNode()//构造空队列
};
队列指针类：
class LinkQueue
{// 对列指针
public:
LinkQueue();//初始化队列
void enQueue(QElemType);//入队
void deQueue(QElemType &);//出队
bool emputyQueue();//判断队是否空,队空TURE,非空FALSE
private:
QueueNode *front; // 队头指针
QueueNode *rear; // 队尾指针
};
四、 执行结果：
以下为我设计的二叉树：
![]()
![]()
执行结果：
Input：ABDH*#I*#E*#CF*J*#G*#
先序遍历的输出各结点，以回车结束没个结点的输入
先序遍历（凹入法表示）
A
B
D
H
I
E
C
F
J
G
中序遍历：
HDIBEAFJCG
后序遍历：
HIDEBJFGCA
层次遍历：
ABCDEFGHIJ
交换其左右子树后:
先序遍历（凹入法表示）
A
C
G
F
J
B
E
D
I
H
中序遍历：
GCJFAEBIDH
后序遍历：
GJFCEIHDBA
层次遍历：
ACBGFEDJIH
请输入需要删除的子树的根节点，以及结点类型
结点：C
结点类型1：左孩子，0：右孩子，-1：根结点:1
删除C后的子树为：
A
B
E
D
I
H
五、 附录：
//--- 二叉树的链式存储结构----
/* 实现二叉树的先序,中序和后序遍历，
并按凹入法打印。打印层次遍历序列。
交换树的左右子树*/
#include <iostream>
#include <stdio.h>
using namespace std;
typedef char TElemType;// 树的元素类型
typedef int CHILD; // 孩子类型1为左孩子，0为右孩子，-1为根结点
class BiTree{
public:
BiTree()
{
data = '/0';
parent = NULL;
lchild = NULL;
rchild = NULL;
}
void creatBiTree();// 构造链式的二叉树 T
void preOrderTraverse(int);
// 先序遍历输出二叉树T.凹入法打印
void inOrderTraverse();
// 中序遍历输出二叉树T.
void postOrderTraverse();
// 后序遍历输出二叉树T.
void leveOrderTraverse();
// 层次遍历二叉树T.
void swapChild();
// 交换左右孩子
void destroyBiTree(TElemType,CHILD);
// 销毁一棵树
private:
TElemType data; // 结点（字符串型）
BiTree *parent, *lchild, *rchild; // 双亲，左孩子和又孩子
};
typedef BiTree * QElemType;// 队列的元素类型
class QueueNode
{//队列结点
private:
friend class LinkQueue;
QElemType data;
QueueNode *next;
public:
QueueNode(QElemType e)
{
data = e;
next = NULL;
}
QueueNode()
{
data = NULL;
next = NULL;
}
};
class LinkQueue
{// 对列指针
public:
LinkQueue();//初始化队列
void enQueue(QElemType);//入队
void deQueue(QElemType &);//出队
bool emputyQueue();//判断队是否空,队空TURE,非空FALSE
private:
QueueNode *front; // 队头指针
QueueNode *rear; // 队尾指针
};
void BiTree:: creatBiTree()
{
char str[5];
scanf("%s",str);
BiTree *currentT = this;
if (str[0] == '*')// 左孩子为空
{
currentT->parent->lchild = NULL;
delete currentT;
}
else if(str[0] == '#')// 右孩子为空
{
currentT->parent->rchild = NULL;
delete currentT;
}
else
{
currentT->data = str[0]; // 构造根节点
currentT->lchild = new BiTree();
currentT->lchild->parent = currentT;
currentT->lchild->creatBiTree(); // 构造左子树
currentT->rchild = new BiTree();
currentT->rchild->parent = currentT;
currentT->rchild->creatBiTree(); // 够造右子树
}
}
void BiTree:: preOrderTraverse(int i)
{ // 凹入法打印
if (this)
{
int j;
for(j = i; j > 0; j--)
cout << " ";
cout << data << endl; // 遍历根节点
lchild->preOrderTraverse(i+1); //先序遍历左子树
rchild->preOrderTraverse(i+1); //先序遍历右子树
}
}
void BiTree:: inOrderTraverse()
{
if (this)
{
lchild->inOrderTraverse(); //先序遍历左子树
cout << data; // 遍历根节点
rchild->inOrderTraverse(); //先序遍历右子树
}
}
void BiTree:: postOrderTraverse()
{
if (this)
{
lchild->postOrderTraverse(); //先序遍历左子树
rchild->postOrderTraverse(); //先序遍历右子树
cout << data; // 遍历根节点
}
}
void BiTree:: leveOrderTraverse()
{
LinkQueue *p = new LinkQueue();
QElemType a = new BiTree();
if (this)
{
p->enQueue(this);
while(!p->emputyQueue())
{
p->deQueue(a);
cout << a->data;
if(a->lchild!=NULL)
p->enQueue(a->lchild);
if(a->rchild!=NULL)
p->enQueue(a->rchild);
}
cout << "/n";
}
}
void BiTree:: swapChild()
{ // 交换左右孩子，先序遍历
BiTree *temT;
if(this)
{
temT = lchild;
lchild = rchild;
rchild = temT;
lchild->swapChild();
rchild->swapChild();
}
}
void BiTree:: destroyBiTree(TElemType _Te, CHILD c)
{ // 删除数据位_Te的结点
if(this)
{
switch(c)
{
case 1: if(_Te == data) this->parent->lchild = NULL;break;
case 0: if(_Te == data) this->parent->rchild = NULL;break;
case-1:if(_Te==data) this->parent->lchild
=this->parent->rchild = NULL;break;
default: cout << "/n你的输入有误请按要求输入。/n";
}
lchild->destroyBiTree(_Te, c);
rchild->destroyBiTree(_Te, c);
}
}
LinkQueue:: LinkQueue()
{
QueueNode *p = new QueueNode();//创建一个内容为空的结点
front = rear = p; //空队列
}
void LinkQueue:: enQueue(QElemType e)
{
QueueNode *p = new QueueNode(e); //申请结点
rear->next = p; //加入新结点
rear = p; //队尾指针指向最后结点
}
void LinkQueue:: deQueue(QElemType &e)
{
QueueNode *p = new QueueNode();
if(!this->emputyQueue())//队非空才允许出队
p = front->next;
e = p->data;
front->next = p->next;
if(rear == p)rear = front;
delete p;
}
bool LinkQueue:: emputyQueue()
{
if(rear == front)//队空
return true;
else return false;
}
void main()
{
BiTree T = BiTree();
TElemType Te;
CHILD C;
cout << "先序遍历的输出各结点，以回车结束没个结点的输入/n";
T.creatBiTree();
cout << "先序遍历（凹入法表示）/n";
T.preOrderTraverse(0);
cout << "/n中序遍历：/n";
T.inOrderTraverse();
cout << "/n后序遍历：/n";
T.postOrderTraverse();
cout << "/n层次遍历：/n";
T.leveOrderTraverse();
T.swapChild();
cout << "/n交换其左右子树后:/n";
cout << "先序遍历（凹入法表示）/n";
T.preOrderTraverse(0);
cout << "/n中序遍历：/n";
T.inOrderTraverse();
cout << "/n后序遍历：/n";
T.postOrderTraverse();
cout << "/n层次遍历：/n";
T.leveOrderTraverse();
cout << "/n请输入需要删除的子树的根节点，以及结点类型/n ";
cout << "结点：";
cin >> Te;
cout << "结点类型1：左孩子，0：右孩子，-1：根结点:";
cin >> C;
T.destroyBiTree(Te, C);
cout << "/n删除" << Te << "后的子树为：/n";
T.preOrderTraverse(0);
}
转播
