【数据结构-树】二叉树的基本操作

文章目录

1 链式存储的二叉树

1.1 定义

typedef struct BiTNode{
    int data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} *BiTNode, BiTree;
1
2
3
4
5

1.2 先序遍历

void PreOrder (BiTree T){
    if (T != NULL){
        访问 T 结点;
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
1
2
3
4
5
6
7

1.3 中序遍历

void InOrder (BiTree T){
    if (T != NULL){
        InOrder(T->lchild);
        访问 T 结点;
        InOrder(T->rchild);
    }
}
1
2
3
4
5
6
7

1.4 后序遍历

void PostOrder (BiTree T){
    if (T != NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        访问 T 结点;
    }
}
1
2
3
4
5
6
7

1.5 层次遍历

void LevelOrder (BiTree T){
    Queue Q; // 辅助队列
    BiTree *TNode;
    
    InitQueue(Q);
    EnQueue(Q, T); // 根节点入队
    
    while (!Empty(Q)){
        DeQueue(Q, TNode); // 队头结点出队
        访问 TNode 结点;
        if (TNode->lchild != NULL)
            EnQueue(Q, TNode->lchild); // 左孩子入队
        if (TNode->rchild != NULL)
            EnQueue(Q, TNode->rchild); // 右孩子入队
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.6 二叉树的高度

int TreeDepth (BiTree T){
    if (T == NULL)
        return 0;
    
    int lchild = TreeDepth(T->lchild);
    int rchild = TreeDepth(T->rchild);
    return max(lchild, rchild) + 1;
}
1
2
3
4
5
6
7
8

1.7 二叉树的宽度

int maxWidth = -1;
int count[MAX_NUM] = {0}; // 记录每层的结点数

// i：二叉树的第几层
void TreeWidth (BiTree T, int i){
    if (T == NULL)
        return 0;
    
    count[i]++;
    maxWidth = max(count[i], maxWidth);
    TreeWidth(T->lchild, i + 1);
    TreeWidth(T->rchild, i + 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.8 统计度为 1 的结点个数

int count = 0;

void Degree1 (BiTree T){
    if (T != NULL){
        Degree1(T->lchild);
        Degree1(T->rchild);
        if (((T->lchild == NULL) && (T->rchild != NULL)) || ((T->lchild != NULL) && (T->rchild == NULL)))
            count++;   
    }
} 
1
2
3
4
5
6
7
8
9
10

1.9 统计度为 2 的结点个数

int count = 0;

void Degree2 (BiTree T){
    if (T != NULL){
        Degree2(T->lchild);
        Degree2(T->rchild);
        if ((T->lchild != NULL) && (T->rchild != NULL))
            count++;   
    }
} 
1
2
3
4
5
6
7
8
9
10

1.10 统计度为 0 的结点个数

int count = 0;

void Degree0 (BiTree T){
    if (T != NULL){
        Degree0(T->lchild);
        Degree0(T->rchild);
        if ((T->lchild == NULL) && (T->rchild == NULL))
            count++;   
    }
} 
1
2
3
4
5
6
7
8
9
10

1.11 计算指定结点 *p 所在层次

int GetLevel (BiTree T, BiTNode *p){
	if (T == NULL) // 如果根节点为空，则所在层次为 0
		return 0;
	if (T == p) // 如果根节点即为 p，则所在层次为 1
		return 1;	
		
	int depl = GetLevel(T->lchild, p); // 获取结点 p 在左子树中的高度
	int depr = GetLevel(T->rchild, p); // 获取结点 p 在右子树中的高度
	if (depl || depr) // 若 depl 和 depr 中有一个不为 0，则取其中的最大值 + 1 即为 p 所在层次
	{
		if (depl > depr)
			return 1 + depl;
		else
			return 1 + depr;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.12 删去所有叶结点

void DelLeafNode (BiTree T){
    BiTNode *p = T;
    if (((p->lchild == NULL) && (p->rchild == NULL)) || (p == NULL)){ // 只有根结点或空树
        return;
    }
    else if ((p->lchild->lchild == NULL) && (p->lchild->rchild == NULL)){
        free(p->lchild);
        p->lchild = NULL;
    }
    else if ((p->rchild->lchild == NULL) && (p->rchild->rchild == NULL)){
        free(p->rchild);
        p->rchild = NULL;
    }
    DelLeafNode(p->lchild);
    DelLeafNode(p->rchild);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.13 交换每个结点的两个子女

void SwapNodeChild (BiTree T){
    if (T->lchild != NULL)
        SwapNodeChild(T->lchild);
    if (T->rchild != NULL)
        SwapNodeChild(T->rchild);

    Swap(T->lchild, T->rchild);
}
1
2
3
4
5
6
7
8

1.14 计算各结点中最大元素的值

int GetMaxNode (BiTree T){
    if (T == NULL) // 如果根结点为空,则最大元素之为 0
        return 0;

    int maxl = GetMaxNode(T->lchild); // 获取根结点左子树的最大元素值
    int maxr = GetMaxNode(T->rchild); // 获取根结点右子树的最大元素值

    int maxlr = (maxl > maxr) ? (maxl) : (maxr);  // 取左、右子树最大元素值中的最大值
    int maxNode = (maxlr > T->data) ? (maxlr) : (T->data); // 取左、右子树最大元素值中的最大值与根结点中的最大值
    
    return maxNode;
}
1
2
3
4
5
6
7
8
9
10
11
12

1.15 以先序次序输出所有结点的数据值及结点所在的层次

void PrintByPreOrder (BiTree T, int level){
    if(T != NULL){
        输出 level 和 T->data;
        PrintByPreOrder(T->lchild, level + 1);
        PrintByPreOrder(T->rchild, level + 1);
    }
}
1
2
3
4
5
6
7

2 顺序存储的二叉树

2.1 树的结点从数组下标 1 开始存储

2.1.1 定义

#define MAX 50

typedef struct{
    int data;
    bool empty; // 记录结点是否为空
} TreeNode;

TreeNode T[MAX+1];
1
2
3
4
5
6
7
8

初始化：

void InitTree (TreeNode &T){
    int i;
    for (i = 1; i <= MAX+1; i++)
        T[i].empty = true;
}
1
2
3
4
5

2.1.2 先序遍历

void PreOrder (TreeNode &T, int i){
    if (!T[i].empty){
        访问 T[i].data;
        
        if (2*i <= MAX)
            PreOrder(T, 2*i);
            
        if (2*i+1 <= MAX)
            PreOrder(T, 2*i+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11

2.1.3 中序遍历

void InOrder (TreeNode &T, int i){
    if (!T[i].empty){
        if (2*i <= MAX)
            InOrder(T, 2*i);
            
        访问 T[i].data;
        
        if (2*i+1 <= MAX)
            InOrder(T, 2*i+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11

2.1.4 后序遍历

void PostOrder (TreeNode &T, int i){
    if (!T[i].empty){
        if (2*i <= MAX)
            PostOrder(T, 2*i);
            
        if (2*i+1 <= MAX)
            PostOrder(T, 2*i+1);
            
        访问 T[i].data;
    }
}
1
2
3
4
5
6
7
8
9
10
11

2.1.5 层次遍历

void LevelOrder (TreeNode &T){
    int i;
    for (i = 1; i <= MAX; i++){
        if (!T[i].empty)
            访问 T[i].data;
    }
}
1
2
3
4
5
6
7

2.1.6 结点 i 的父结点

int FindFather (int i){
    return i / 2;
}
1
2
3

2.1.7 结点 i 的左孩子

int FindLeftChild (int i){
    return 2 * i;
}
1
2
3

2.1.8 结点 i 的右孩子

int FindRightChild (int i){
    return 2 * i + 1;
}
1
2
3

2.1.9 结点 i 的层数

int FindFloor (int i){
    return log(2, i) + 1; // log 以 2 为底的对数函数
}
1
2
3

2.2 树的结点从数组下标 0 开始存储

2.2.1 定义

#define MAX 50

typedef struct{
    int data;
    bool empty; // 记录结点是否为空
} TreeNode;

TreeNode T[MAX];
1
2
3
4
5
6
7
8

初始化：

void InitTree (TreeNode &T){
    int i;
    for (i = 0; i < MAX; i++)
        T[i].empty = true;
}
1
2
3
4
5

2.2.2 先序遍历

void PreOrder (TreeNode &T, int i){
    if (!T[i].empty){
        访问 T[i].data;
        
        if (2*i+1 < MAX)
            PreOrder(T, 2*i+1);
            
        if (2*i+2 < MAX)
            PreOrder(T, 2*i+2);
    }
}
1
2
3
4
5
6
7
8
9
10
11

2.2.3 中序遍历

void InOrder (TreeNode &T, int i){
    if (!T[i].empty){
        if (2*i+1 < MAX)
            InOrder(T, 2*i+1);
            
        访问 T[i].data;
        
        if (2*i+2 < MAX)
            InOrder(T, 2*i+2);
    }
}
1
2
3
4
5
6
7
8
9
10
11

2.2.4 后序遍历

void PostOrder (TreeNode &T, int i){
    if (!T[i].empty){
        if (2*i+1 < MAX)
            PostOrder(T, 2*i+1);
            
        if (2*i+2 < MAX)
            PostOrder(T, 2*i+2);
            
        访问 T[i].data;
    }
}
1
2
3
4
5
6
7
8
9
10
11

2.2.5 层次遍历

void LevelOrder (TreeNode &T){
    int i;
    for (i = 0; i < MAX; i++){
        if (!T[i].empty)
            访问 T[i].data;
    }
}
1
2
3
4
5
6
7

2.2.6 结点 i 的父结点

int FindFather (int i){
    return (i - 1) / 2;
}
1
2
3

2.2.7 结点 i 的左孩子

int FindLeftChild (int i){
    return 2 * i + 1;
}
1
2
3

2.2.8 结点 i 的右孩子

int FindRightChild (int i){
    return 2 * i + 2;
}
1
2
3

2.2.9 结点 i 的层数

int FindFloor (int i){
    return log(2, i-1) + 1; // log 以 2 为底的对数函数
}
1
2
3

相关阅读:
寻找两个正序数组的中位数 Golang leecode_4
webpack是如何解析模块的
Flutter 使用 CustomPaint 绘制基本图形
【学习笔记】设计算法（Design Algorithm）
【iMessage苹果相册推位置推】“MFI授权计划”是指一个零丁的苹果程序开发
Flask 专题
微信小程序-组件
【无标题】
厂家解读新标准GB21148-2020《足部防护安全鞋》的变化有哪些
基于ssm的大学生信息管理及就业预测系统

原文地址：https://blog.csdn.net/baidu_39514357/article/details/127562053