大热天敲代码与看书更配哦  


伪代码。

二叉树的链式存储结构

1
2
3
4
typedef struct BiTNode{
ElemType data;//数据域
struct BiTNode *lchild, *rchild;//左、右孩子指针
}BiTNode, *BiTree;

二叉树的遍历

例:1
2 3
4 5
6

先序遍历(PreOrder)

根->左->右

1
2
3
4
5
6
7
void PreOrder(BiTree T){
if (T != NULL){
visit(T);//访问根节点
PreOrder(T->lchild);//递归遍历左子树
PreOrder(T->rchild);//递归遍历右子树
}
}

124635

中序遍历(InOrder)

左->根->右

1
2
3
4
5
6
7
void InOrder(BiTree T){
if (T != NULL){
InOrder(T->lchild);//递归遍历左子树
visit(T);//访问根节点
InOrder(T->rchild);//递归遍历右子树
}
}

264135

后序遍历(PostOrder)

左->右->根

1
2
3
4
5
6
7
8
void PostOrder(BiTree T){
if (T != NULL)
{
PostOrder(T->lchild);//递归遍历左子树
PostOrder(T->rchild);//递归遍历右子树
visit(T);//访问根节点
}
}

642531

时间复杂度都是O(n),空间复杂度为O(n)。

中序遍历的非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InOrder2(BiTree T){
//二叉树中序遍历的非递归算法,算法需要借助一个栈
InitStack(S);
BiTree p = T; //初始化栈;p是遍历指针
while (p || !IsEmpty(S)){ //栈不空或p不空时循环
if (p){ //根指针进展,遍历左子树
Push(S, p); //每遇到非空二叉树先向左走
p = p->lchild;
}
else{ //根指针退栈,访问根节点,遍历右子树
Pop(S, p); visit(p); //退栈,访问根节点
p = p->rchild; //再向右子树走
}
}
}

二叉树的层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void LevelOrder(BiTree T){
InitQueue(Q);//初始化辅助队列
BiTree p;
EnQueue(Q, T);//将根结点入队
while (!IsEmpty(Q)){//队列不空循环
DeQueue(Q, p);//队头元素出队
visit(p);//访问当前p所指向结点
if (p->lchild != NULL)
{
EnQueue(Q, p->lchild);//左子树不空,则左子树入队列
}
if (p->rchild != NULL)
{
EnQueue(Q, p->rchild);//右子树不空,则右子树入队列
}
}
}

树的存储结构

双亲表示法

1
2
3
4
5
6
7
8
9
#define MAX_TREE_SIZE 100	//树中最多结点数
typedef struct{ //树的结点定义
ElemType data; //数据元素
int parent; //双亲位置域
}PTNode;
typedef struct{ //树的类型定义
PTNode nodes[MAX_TREE_SIZE]; //双亲表示
int n; //结点数
}PTree;

求结点的孩子时需遍历整个结构。

孩子表示法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

typedef struct CTNode //孩子结点
{
int child;
struct CTNode *next;
}*ChildPtr;
typedef struct
{
TElemType data;
ChildPtr firstchild;//孩子链表头指针
}CTBox;
typedef struct
{
CTBox nodes[MAX_TREE_SIZE];
int n, r; //结点数和根的位置
}CTree;

求结点的双亲时需遍历N个结点中孩子链表指针域所指向的N个孩子链表。

孩子兄弟表示法(二叉树表示法)

1
2
3
4
5
typedef struct CSNode
{
ElemType data; //数据域
struct CSNode *firstchild, *nextsibling; //第一个孩子和右兄弟指针
}CSNode, *CSTree;

易查找结点的孩子,若为每个结点增设一个parent域指向其父节点,则查找结点的父结点也很方便。

树转换为二叉树的规则:每个结点左指针指向它的第一个孩子结点,右指针指向它在树中的相邻兄弟结点,可表示为“左孩子右兄弟”。由于根节点没有兄弟,所以由树转换而得的二叉树没有右子树。

例:
一颗具体的树
转换后

C++实现

由于博主不允许转载,因此详见参考。
为防止程序一闪而过,在main程序末尾添加system(“pause”);使画面停留。

参考

数据结构教材
数据结构与算法——普通树的定义与C++实现
C++树(兄弟孩子结构实现)
VC++ 树的孩子兄弟表示法
使用C++ 和 孩子兄弟表示法实现树
孩子兄弟表示法实现树


最近更新频繁的原因如下:
上周
上周

未来一周
未来一周

热成熟透的咸鱼 不如宅着做咸鱼

文章目录
  1. 1. 二叉树的链式存储结构
  2. 2. 二叉树的遍历
    1. 2.1. 先序遍历(PreOrder)
    2. 2.2. 中序遍历(InOrder)
    3. 2.3. 后序遍历(PostOrder)
  3. 3. 中序遍历的非递归算法
  4. 4. 二叉树的层次遍历
  5. 5. 树的存储结构
    1. 5.1. 双亲表示法
    2. 5.2. 孩子表示法
    3. 5.3. 孩子兄弟表示法(二叉树表示法)
  6. 6. C++实现
  7. 7. 参考
|