文章目录[隐藏]
- 二叉树
- 1. 定义
- 2. 遍历
- 3. 先序遍历和中序遍历构建二叉树
- 4. 层次遍历和中序遍历构建二叉树
- 5. 求一棵二叉树的结点个数
- 6. 求一棵二叉树的叶子节点个数
- 7. 求一棵二叉树度为 1 结点个数
- 8. 查找二叉树中值为X的结点。若存在,则返回存储位置,不存在,则返回空
- 9. 求二叉树的高度
- 10. 求一棵二叉树中值为 X 的节点作为根节点的子树深度
- 11. 交换一棵二叉树的左右子树
- 12. 判断两棵树是否相似,相似返回true,不相似返回false
- 13. 设计算法利用叶子节点中的空指针域将所有叶子节点链接成一个带头节点的双链表
- 14. 假设一个仅含二元运算的算数表达式以二叉链表形式存放在二叉树T,设计算法求解算术表达式的值
- 15. 层次遍历
- 16. 判断一棵树是否为完全二叉树
- 17. 求一个二叉树的最大宽度
- 18. 设计算法构建一棵二叉排序树
- 19. 删除二叉排序树T中关键字为x的结点
- 20. 将一棵二叉排序树T分解成两棵二叉排序树T1与T2,使得T1中的所有结点关键字的值都小于key,T2中所有关键字的值都大于key
- 21. 已知二叉排序树中每一个结点值为整型,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的结点
- 22. 查找二叉排序树中所有小于key的关键字
- 23. 存在一个二叉排序树,给定一个value值,若查找value值,就返回比value值大的所有值中最小的值。若value最大就返回空
- 24. 构造一棵先序线索二叉树
- 25. 先序线索二叉树的先序遍历算法
- 26. 构造一棵中序线索二叉树
- 27. 中序线索二叉树的中序遍历算法
- 28. 树的遍历
- 29. 计算一棵以孩子兄弟链表示的树T的度
- 30. 森林的遍历
二叉树
1. 定义
typedef int ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
2. 遍历
// 先序遍历
void preOrder(BiTree T){
if(T != NULL){
printf("%c ",T->data);
preOrder(T->lchild);
preOrder(T->rchild);
}
}
// 中序遍历
void preOrder(BiTree T){
if(T != NULL){
preOrder(T->lchild);
printf("%c ",T->data);
preOrder(T->rchild);
}
}
// 后序遍历
void preOrder(BiTree T){
if(T != NULL){
preOrder(T->lchild);
preOrder(T->rchild);
printf("%c ",T->data);
}
}
3. 先序遍历和中序遍历构建二叉树
// 通过先序遍历和中序遍历数组构建二叉树的函数
BiTNode *createBiTree(ElemType preOrderList[], int preStartIndex, int preEndIndex,
ElemType inOrderList[], int inStartIndex, int inEndIndex) {
// 如果先序遍历数组的起始索引大于终止索引,返回空节点
if (preStartIndex > preEndIndex) {
return NULL;
}
// 为当前节点分配内存,并将当前先序遍历的起始元素作为节点数据
BiTNode *t = (BiTNode *) malloc(sizeof(BiTNode));
t->data = preOrderList[preStartIndex];
// 在中序遍历数组中找到当前节点的位置
int rIndex;
for (rIndex = inStartIndex; rIndex <= inEndIndex; rIndex++) {
if (inOrderList[rIndex] == t->data) {
break;
}
}
// 计算左子树的长度
int length = rIndex - inStartIndex;
// 构建左子树
t->lchild = createBiTree(preOrderList, preStartIndex + 1, preStartIndex + length,
inOrderList, inStartIndex, rIndex - 1);
// 构建右子树
t->rchild = createBiTree(preOrderList, preStartIndex + length + 1, preEndIndex,
inOrderList, rIndex + 1, inEndIndex);
// 返回构建的节点
return t;
}
4. 层次遍历和中序遍历构建二叉树
// 通过层次遍历和中序遍历数组构建二叉树的函数
BiTNode *createBiTree(ElemType levelOrderList[], int levelStartIndex, int levelEndIndex,
ElemType inOrderList[], int inStartIndex, int inEndIndex) {
// 如果层次遍历数组的起始索引大于终止索引,返回空节点
if (levelStartIndex > levelEndIndex) {
return NULL;
}
// 为当前节点分配内存,并将当前层次遍历的起始元素作为节点数据
BiTNode *t = (BiTNode *) malloc(sizeof(BiTNode));
t->data = levelOrderList[levelStartIndex];
// 在中序遍历数组中找到当前节点的位置
int rIndex;
for (rIndex = inStartIndex; rIndex <= inEndIndex; rIndex++) {
if (inOrderList[rIndex] == t->data) {
break;
}
}
// 创建左子树的层次遍历数组
ElemType leftLevelOrderList[MAX_SIZE];
int leftLevelOrderListLength = 0;
for (int i = levelStartIndex + 1; i <= levelEndIndex; i++) {
for (int j = inStartIndex; j < rIndex; j++) {
if (levelOrderList[i] == inOrderList[j]) {
leftLevelOrderList[leftLevelOrderListLength++] = levelOrderList[i];
}
}
}
// 创建右子树的层次遍历数组
ElemType rightLevelOrderList[MAX_SIZE];
int rightLevelOrderListLength = 0;
for (int i = levelStartIndex + 1; i <= levelEndIndex; i++) {
for (int j = rIndex + 1; j <= inEndIndex; j++) {
if (levelOrderList[i] == inOrderList[j]) {
rightLevelOrderList[rightLevelOrderListLength++] = levelOrderList[i];
}
}
}
// 构建左子树
t->lchild = createBiTree(leftLevelOrderList, 0, leftLevelOrderListLength - 1,
inOrderList, inStartIndex, rIndex - 1);
// 构建右子树
t->rchild = createBiTree(rightLevelOrderList, 0, rightLevelOrderListLength - 1,
inOrderList, rIndex + 1, inEndIndex);
// 返回构建的节点
return t;
}
5. 求一棵二叉树的结点个数
int getNodes(BiTree T) {
if(T == NULL) {
return 0;
}
return getNodes(T->lchild) + getNodes(T->rchild) + 1;
}
6. 求一棵二叉树的叶子节点个数
int getLeafs(BiTree T) {
if (T == NULL) {
return 0;
}
if(T->lchild == NULL && T->rchild == NULL) {
return 1;
}
return getLeafs(T->lchild) + getLeafs(T->rchild);
}
7. 求一棵二叉树度为 1 结点个数
int getSingleDegreeNodes(BiTree T) {
if(T == NULL){
return 0;
}
if(T->lchild == NULL && T->rchild != NULL) {
return 1 + getSingleDegreeNodes(T->rchild);
}
if(T->lchild != NULL && T->rchild == NULL) {
return 1 + getSingleDegreeNodes(T->lchild);
}
return getSingleDegreeNodes(T->lchild) + getSingleDegreeNodes(T->rchild);
}
8. 查找二叉树中值为X的结点。若存在,则返回存储位置,不存在,则返回空
BiTNode *getNode(BiTree T, ElemType X){
if(T == NULL){
return NULL;
}
if(T->data == X){
return T;
}
BiTNode *node = getNode(T->lchild, X);
if(node != NULL){
return node;
}
return getNode(T->rchild, X);;
}
9. 求二叉树的高度
int getBiTreeHeight(BiTree T){
if(T == NULL){
return 0;
}
int leftHeight = getBiTreeHeight(T->lchild);
int rightHeight = getBiTreeHeight(T->rchild);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
10. 求一棵二叉树中值为 X 的节点作为根节点的子树深度
int getElemNodeHeight(BiTree T, ElemType X){
BiTNode *node = getNode(T, X);
if(node == NULL){
return 0;
}
return getBiTreeHeight(node);
}
11. 交换一棵二叉树的左右子树
void swapChild(BiTree T){
if(T == NULL){
return;
}
BiTNode *temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
swapChild(T->lchild);
swapChild(T->rchild);
}
12. 判断两棵树是否相似,相似返回true,不相似返回false
bool isSimilar(BiTree T1, BiTree T2){
if(T1 == NULL && T2 == NULL){
return true;
}
if(T1 == NULL || T2 == NULL){
return false;
}
return isSimilar(T1->lchild, T2->lchild) && isSimilar(T1->rchild, T2->rchild);
}
13. 设计算法利用叶子节点中的空指针域将所有叶子节点链接成一个带头节点的双链表
// 链接叶子节点到双链表
void connectLeafNodes(BiTree T, BiTNode *&pTail) {
if(T == NULL) {
return;
}
if(T->lchild == NULL && T->rchild == NULL) {
T->lchild = pTail;
pTail->rchild = T;
pTail = T;
} else {
connectLeafNodes(T->lchild, pTail);
connectLeafNodes(T->rchild, pTail);
}
}
// 初始化叶子结点双链表
void initLeafNodeList(BiTree T) {
BiTNode *L = (BiTNode *) malloc(sizeof(BiTNode));
L->lchild = NULL;
L->rchild = NULL;
BiTNode *pTail = L;
connectLeafNodes(T, pTail);
printf("双链表中的叶子节点: ");
BiTNode *cur = L->rchild;
while(cur != NULL) {
printf("%c ", cur->data);
cur = cur->rchild;
}
printf("\n");
}
14. 假设一个仅含二元运算的算数表达式以二叉链表形式存放在二叉树T,设计算法求解算术表达式的值
// 根据操作符计算表达式的值
int evaluateExpression(char op, int leftValue, int rightValue){
switch(op){
case '+':
return leftValue + rightValue;
case '-':
return leftValue - rightValue;
case '*':
return leftValue * rightValue;
case '/':
return leftValue / rightValue;
}
}
// 递归计算二叉树中存储的算术表达式的值
int calculateExpressionValue(BiTree T){
if(T == NULL){
return 0;
}
if(T->lchild == NULL && T->rchild == NULL){
return T->data - '0';
}
int leftValue = calculateExpressionValue(T->lchild);
int rightValue = calculateExpressionValue(T->rchild);
return evaluateExpression(T->data, leftValue, rightValue);
}
15. 层次遍历
void levelOrder(BiTree T){
Queue Q;
// 初始化队列
initQueue(Q);
enQueue(Q, T);
// 队列不为空
while(!isEmptyQueue(Q)){
BiTNode *e = NULL;
// 出队
deQueue(Q, e);
printf("%c ", e->data);
// 处理左右孩子
if(e->lchild != NULL){
enQueue(Q, e->lchild);
}
if(e->rchild != NULL){
enQueue(Q, e->rchild);
}
}
}
16. 判断一棵树是否为完全二叉树
- 初始化:
- 初始化一个队列,并将二叉树的根节点入队。
- 层序遍历:
- 持续从队列中取出节点进行处理:
- 如果取出的节点不为空,将其左、右子节点依次入队。
- 如果取出的节点为空,停止继续入队,并跳出循环。
- 队列检查:
- 继续从队列中取出剩余的节点:
- 如果此时队列中仍有非空节点,说明二叉树在某个节点之后还存在非空节点,不满足完全二叉树的条件,返回
0
。 - 如果队列中都是空节点,说明是完全二叉树,返回
1
。
- 如果此时队列中仍有非空节点,说明二叉树在某个节点之后还存在非空节点,不满足完全二叉树的条件,返回
int isCompleteBiTree(BiTree T){
Queue Q;
initQueue(Q);
enQueue(Q, T);
while(!isEmptyQueue(Q)){
BiTNode *e = NULL;
deQueue(Q, e);
if(e == NULL){
break;
}
enQueue(Q, e->lchild);
enQueue(Q, e->rchild);
}
while(!isEmptyQueue(Q)){
BiTNode *e = NULL;
deQueue(Q, e);
if(e != NULL){
return 0;
}
}
return 1;
}
17. 求一个二叉树的最大宽度
- 初始化队列:
- 创建并初始化一个队列,将二叉树的根节点入队。
- 设置最大宽度变量:
- 初始化一个变量
maxWidth
用于记录当前树的最大宽度。
- 层序遍历:
- 使用循环进行层序遍历,直到队列为空为止。
- 对每一层进行处理:
- 计算当前队列中节点的数量(即当前层的节点数)。
- 逐个从队列中取出节点,如果节点不为空,记录当前层的节点数,并将该节点的左右子节点(如果存在)入队。
- 更新最大宽度:
- 比较当前层的节点数与记录的最大宽度
maxWidth
,如果当前层的宽度大于maxWidth
,则更新maxWidth
。
- 返回结果:
- 当所有层都遍历完后,返回
maxWidth
,即二叉树的最大宽度。
int maxWidth(BiTree T){
Queue Q;
initQueue(Q);
enQueue(Q, T);
int maxWidth = 0;
while(!isEmptyQueue(Q)){
int width = 0;
int nodeCount = 0;
QueueNode *temp = Q.front;
while(temp != Q.rear){
nodeCount++;
temp = temp->next;
}
for(int i = 0; i < nodeCount; i++){
BiTNode *e = NULL;
deQueue(Q, e);
if(e != NULL){
width++;
enQueue(Q, e->lchild);
enQueue(Q, e->rchild);
}
}
if(width > maxWidth){
maxWidth = width;
}
}
return maxWidth;
}
18. 设计算法构建一棵二叉排序树
typedef int ElemType;
typedef struct BSTNode{
ElemType data;
struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
void insertKey(BSTree &T, ElemType key){
if(T == NULL){
BSTNode *node = (BSTNode *) malloc (sizeof(BSTNode));
node->data = key;
node->lchild = NULL;
node->rchild = NULL;
T = node;
} else if(T->data < key){
insertKey(T->rchild, key);
} else{
insertKey(T->lchild, key);
}
}
BSTNode *createBSTree(){
BSTNode *T = NULL;
ElemType keyList[] = {40,10,45,15};
int keyListLength = 4;
for(int i = 0; i < keyListLength; i++){
insertKey(T, keyList[i]);
}
return T;
}
19. 删除二叉排序树T中关键字为x的结点
deleteNodeHelper
函数:
- 处理节点的删除逻辑。
- 当节点是叶子节点时,直接释放内存并将指针设为
NULL
。 - 当节点只有一个子节点时,用该子节点替换当前节点,并释放当前节点的内存。
- 当节点有两个子节点时,找到左子树中的最大节点(最右节点),将其右子树连接到当前节点的右子树,然后用左子树的根节点替换当前节点,最后释放当前节点的内存。
deleteNode
函数:
- 查找目标节点并调用
deleteNodeHelper
函数删除该节点。 - 如果当前节点为空,则递归查找左子树或右子树,直到找到目标节点。
void deleteNodeHelper(BSTree &T){
if(T->lchild == NULL && T->rchild == NULL){
free(T);
T = NULL;
} else if(T->lchild == NULL){
BSTNode *pNode = T;
T = T->rchild;
free(pNode);
} else if(T->rchild == NULL){
BSTNode *pNode = T;
T = T->lchild;
free(pNode);
} else{
BSTNode *pMax = T->lchild;
while(pMax->rchild != NULL){
pMax = pMax->rchild;
}
pMax->rchild = T->rchild;
BSTNode *pNode = T;
T = T->lchild;
free(pNode);
}
}
void deleteNode(BSTree &T, ElemType X){
if(T != NULL){
if(T->data == X){
deleteNodeHelper(T);
}else if(T->data > X){
deleteNode(T->lchild, X);
}else{
deleteNode(T->rchild, X);
}
}
}
20. 将一棵二叉排序树T分解成两棵二叉排序树T1与T2,使得T1中的所有结点关键字的值都小于key,T2中所有关键字的值都大于key
- 如果当前节点的值等于
key
,将左子树的节点插入到T1
,将右子树的节点插入到T2
,然后删除当前节点。 - 如果当前节点的值小于
key
,递归处理右子树(因为右子树可能包含大于key
的节点)。处理完右子树后,将当前节点断开右子树,并插入到T1
。 - 如果当前节点的值大于
key
,递归处理左子树(因为左子树可能包含小于key
的节点)。处理完左子树后,将当前节点断开左子树,并插入到T2
。
void insertNode(BSTree &T, BSTNode *node){
if(T == NULL){
T = node;
} else if(T->data < node->data){
insertNode(T->rchild, node);
} else{
insertNode(T->lchild, node);
}
}
void splitBSTree(BSTree &T, BSTree &T1, BSTree &T2, ElemType key){
if(T != NULL){
if(T->data == key){
insertNode(T1, T->lchild);
insertNode(T2, T->rchild);
free(T);
T = NULL;
} else if(T->data < key){
splitBSTree(T->rchild, T1, T2, key);
T->rchild = NULL;
insertNode(T1, T);
} else{
splitBSTree(T->lchild, T1, T2, key);
T->lchild = NULL;
insertNode(T2, T);
}
}
}
21. 已知二叉排序树中每一个结点值为整型,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的结点
- 递归遍历树:
- 通过递归遍历树,逐个访问每个节点,检查它的值是否小于
X
。
- 处理等于
X
的节点:
- 如果当前节点的值等于
X
,则删除其左子树中的所有节点(因为二叉排序树中左子树的所有节点都小于当前节点)。 - 删除操作通过调用
deleteNode
函数递归地删除整个左子树,并将该节点的左指针置为NULL
。
- 处理小于
X
的节点:
- 如果当前节点的值小于
X
,首先递归处理其右子树,删除右子树中小于X
的节点。 - 然后,将当前节点的右子树替换为右子树中的值大于或等于
X
的部分,删除当前节点。
- 处理大于
X
的节点:
- 如果当前节点的值大于
X
,则递归处理其左子树。
void deleteNode(BSTNode *node) {
if(node != NULL) {
deleteNode(node->lchild);
deleteNode(node->rchild);
node->lchild = NULL;
node->rchild = NULL;
free(node);
node = NULL;
}
}
void deleteLessThanX(BSTree &T, ElemType X) {
if(T != NULL) {
if(T->data == X) {
deleteNode(T->lchild);
T->lchild = NULL;
} else if(T->data < X) {
deleteLessThanX(T->rchild, X);
BSTNode *pNode = T;
T = T->rchild;
pNode->rchild = NULL;
deleteNode(pNode);
} else {
deleteLessThanX(T->lchild, X);
}
}
}
22. 查找二叉排序树中所有小于key的关键字
void inOrderLessThanKey(BSTree T, ElemType key){
if(T != NULL){
inOrderLessThanKey(T->lchild, key);
if(T->data < key){
printf("%d ",T->data);
inOrderLessThanKey(T->rchild, key);
}
}
}
23. 存在一个二叉排序树,给定一个value值,若查找value值,就返回比value值大的所有值中最小的值。若value最大就返回空
// 查找比给定值大的所有值中最小的值
BSTNode *findSuccessor(BSTree T, ElemType value) {
BSTNode *successor = NULL;
while (T != NULL) {
if (T->data > value) {
// 可能找到比 value 大的最小值
successor = T;
T = T->lchild; // 尝试在左子树中找到更小的可能值
} else {
// 当前节点值小于等于 value,往右子树查找
T = T->rchild;
}
}
return successor;
}
24. 构造一棵先序线索二叉树
- 处理当前节点:
- 如果当前节点的左孩子为空,将其
ltag
置为 1,并将lchild
指向前驱节点(即先序遍历中上一个访问的节点)。 - 如果前驱节点的右孩子为空,将前驱节点的
rtag
置为 1,并将rchild
指向当前节点。
-
更新前驱节点为当前节点。
-
递归处理左子树。
-
递归处理右子树。
void threadBinaryTree(ThreadTree T, ThreadNode *&preNode) {
if(T != NULL) {
if(T->lchild == NULL) {
T->ltag = 1;
T->lchild = preNode;
}
if(preNode != NULL && preNode->rchild == NULL) {
preNode->rtag = 1;
preNode->rchild = T;
}
preNode = T;
if(T->ltag == 0) {
threadBinaryTree(T->lchild, preNode);
}
if(T->rtag == 0) {
threadBinaryTree(T->rchild, preNode);
}
}
}
void startThreading(ThreadTree T) {
ThreadNode *preNode = NULL;
threadBinaryTree(T, preNode);
}
25. 先序线索二叉树的先序遍历算法
void preOrderThreadedTraversal(ThreadTree T) {
ThreadNode *pSuccessor = NULL;
ThreadNode *preNode = T;
while(preNode != NULL) {
if(preNode->ltag == 0) {
pSuccessor = preNode->lchild;
} else {
pSuccessor = preNode->rchild;
}
printf("%c ",preNode->data);
preNode = pSuccessor;
}
}
26. 构造一棵中序线索二叉树
void threadBinaryTree(ThreadTree T, ThreadNode *&preNode) {
if(T != NULL) {
threadBinaryTree(T->lchild, preNode);
if(T->lchild == NULL) {
T->ltag = 1;
T->lchild = preNode;
}
if(preNode != NULL && preNode->rchild == NULL) {
preNode->rtag = 1;
preNode->rchild = T;
}
preNode = T;
threadBinaryTree(T->rchild, preNode);
}
}
void startThreading(ThreadTree T) {
ThreadNode *preNode = NULL;
threadBinaryTree(T, preNode);
}
27. 中序线索二叉树的中序遍历算法
void inOrderThreadedTraversal(ThreadTree T) {
ThreadNode *p = T;
while(p != NULL) {
// 找到中序遍历的第一个节点
while(p->ltag == 0) {
p = p->lchild;
}
// 访问该节点
printf("%c ", p->data);
// 按照线索移动到下一个节点
while(p->rtag == 1 && p->rchild != NULL) {
p = p->rchild;
printf("%c ", p->data);
}
// 移动到右子树
p = p->rchild;
}
}
28. 树的遍历
typedef struct CSTNode {
ElemType data;
struct CSTNode *firstChild;
struct CSTNode *nextSibling;
} CSTNode, *CSTree;
// 先根遍历
void preOrderTraverse(CSTree T){
if(T != NULL){
printf("%d ", T->data);
CSTNode *pCurChild = T->firstChild;
while(pCurChild != NULL){
preOrderTraverse(pCurChild);
pCurChild = pCurChild->nextSibling;
}
}
}
// 后根遍历
void postOrderTraverse(CSTree T){
if(T != NULL){
CSTNode *pCurChild = T->firstChild;
while(pCurChild != NULL){
postOrderTraverse(pCurChild);
pCurChild = pCurChild->nextSibling;
}
printf("%d ", T->data);
}
}
29. 计算一棵以孩子兄弟链表示的树T的度
int getDegree(CSTree T){
if(T == NULL){
return 0;
}
int maxSubTreeDegree = 0;
int rootNodeDegree = 0;
CSTNode *pCurChild = T->firstChild;
while(pCurChild != NULL){
rootNodeDegree++;
int subTreeDegree = getDegree(pCurChild);
if(subTreeDegree > maxSubTreeDegree){
maxSubTreeDegree = subTreeDegree;
}
pCurChild = pCurChild->nextSibling;
}
return rootNodeDegree > maxSubTreeDegree ? rootNodeDegree : maxSubTreeDegree;
}
30. 森林的遍历
// 先根遍历
void preOrderTraverse(CSTree T){
if(T != NULL){
printf("%d ", T->data);
CSTNode *pCurChild = T->firstChild;
while(pCurChild != NULL){
preOrderTraverse(pCurChild);
pCurChild = pCurChild->nextSibling;
}
preOrderTraverse(T->nextSibling);
}
}
// 后根遍历
void postOrderTraverse(CSTree T){
if(T != NULL){
CSTNode *pCurChild = T->firstChild;
while(pCurChild != NULL){
postOrderTraverse(pCurChild);
pCurChild = pCurChild->nextSibling;
}
printf("%d ", T->data);
preOrderTraverse(T->nextSibling);
}
}