二叉树的操作
二叉树的基本操作和一些应用，具体涉及二叉树的创建、查找、统计叶子节点、根据先序和中序或后序和中序序列恢复二叉树，以及中序线索二叉树的构建。以下是对每个主要部分的详细讲解：
1. 二叉树的结构定义
cpptypedef struct Node {
int data;
Node* lchild;
Node* rchild;
} *bitTree;
这里定义了一个 Node 结构体，用于表示二叉树的节点。每个节点包含：
data：节点的值。lchild：指向左子节点的指针。rchild：指向右子节点的指针。
bitTree 是指向 Node
类 **
型的指针，可以用来表示二叉树。
2. 创建二叉树
cppvoid createBitTree(bitTree *T) {
int data;
cin >> data;
if (data == 0) *T = NULL;
else {
*T = new Node();
(*T)->data = data;
createBitTree(&((*T)->lchild));
createBitTree(&((*T)->rchild));
}
}
createBitTree函数用于从输入构建一颗二叉树。如果输入的data是 0，表示当前节点为空，指针指向NULL。否则，为当前节点分配内存并递归地创建左子树和右子树。*T是二叉树的根节点指针，通过递归调用构建左右子树。
3. 查找指定节点
cppNode* Search(bitTree bt, int x) {
Node* p;
if (bt) {
if (bt->data == x) return bt;
if (bt->lchild) p = Search(bt->lchild, x);
if (p) return p;
if (bt->rchild) p = Search(bt->rchild, x);
if (p) return p;
}
return NULL;
}
Search函数通过递归实现二叉树的深度优先搜索，查找值为x的节点。- 从根节点开始，首先检查根节点的值是否等于目标值，如果是，返回该节点。
- 如果不是，递归查找左子树和右子树。
cppNode* Search1(bitTree bt, int x) {
if (bt == NULL) return NULL;
if (bt->data == x) return bt;
Node* p = Search1(bt->lchild, x);
if (p != NULL) return p;
return Search1(bt->rchild, x);
}
- 这是另一个查找函数，逻辑和上面相似，只是去除了
p的冗余检查，直接递归查找左子树和右子树。
4. 统计叶子节点数量
cppint countLeaf(bitTree bt) {
if (bt == NULL) return 0;
else if (bt->rchild == NULL && bt->lchild == NULL) return 1;
return countLeaf(bt->lchild) + countLeaf(bt->rchild);
}
countLeaf函数用于统计二叉树中叶子节点的数量。叶子节点是左右子树都为空的节点。- 如果当前节点是叶子节点，则返回 1；否则，递归计算左子树和右子树的叶子节点数。
5. 根据先序和中序遍历恢复二叉树
cppvoid preInOd(string preod, int i, int j, string inod, int k, int h, bitTree &T) {
T = new Node();
T->data = preod[i];
int m = k;
while (m <= h) {
if (inod[m] == T->data) break;
m++;
}
if (m == k) T->lchild = NULL;
else preInOd(preod, i+1, i+m-k, inod, k, m-1, T->lchild);
if (m == h) T->rchild = NULL;
else preInOd(preod, i+m-k+1, j, inod, m+1, h, T->rchild);
}
preInOd函数通过先序遍历和中序遍历的序列来恢复二叉树。preod[i]是当前根节点，递归构建左子树和右子树。inod用于定位当前根节点在中序序列中的位置，从而划分左右子树。
6. 根据后序和中序遍历恢复二叉树
cppvoid postInOd(string postod, int i, int j, string inod, int k, int h, bitTree &T) {
if (i > j || k > h) return;
T = new Node();
T->data = postod[j];
int m = k;
while (m <= h) {
if (inod[m] == T->data) break;
m++;
}
if (m == h) {
T->rchild = NULL;
} else {
postInOd(postod, i, i + m - k - 1, inod, m + 1, h, T->rchild);
}
if (m == k) {
T->lchild = NULL;
} else {
postInOd(postod, i, i + m - k - 1, inod, k, m - 1, T->lchild);
}
}
postInOd函数通过后序遍历和中序遍历的序列来恢复二叉树。- 从后序序列中获取根节点，并在中序序列中定位该根节点的位置，递归构建左右子树。
7. 中序线索化二叉树
cpptypedef struct hrNode {
int data;
hrNode *lchild;
hrNode *rchild;
int ltag;
int rtag;
} *bitHrNode;
hrNode结构体用于表示线索化后的二叉树节点，增加了ltag和rtag两个标志，用于指示左子指针和右子指针是否指向孩子节点（0表示指向子树，1表示指向线索）。
cppbitHrNode InOrderThr(bitHrNode T) {
hrNode* head = new hrNode();
head->ltag = 0;
head->rtag = 1;
head->rchild = head; // 建立头节点
if (!T) head->lchild = head; // 若二叉树为空，则左指针回指
else {
head->lchild = T;
pre = head;
InThreading(T);
pre->rchild = head;
pre->rtag = 1; // 最后一个节点线索化
head->rchild = pre;
}
return head;
}
InOrderThr函数用来将二叉树转换为中序线索二叉树。头节点head用来指示树的开始，并通过InThreading函数完成树的线索化。
#include<bits/stdc++.h>
using namespace std;
// 二叉树遍历的应用
typedef struct Node{
int data;
Node* rchild;
Node* lchild;
}*bitTree;
// 建立二叉树的二叉链表
void createBitTree(bitTree *T){
int data;
cin>>data;
if(data = 0) *T = NULL;
else{
*T = new Node();
(*T)->data = data;
createBitTree(&((*T)->lchild));
createBitTree(&((*T)->rchild));
}
}
// 查找
Node* Search(bitTree bt, int x){
Node* p;
if(bt){
if(bt->data == x) return bt;
if(bt->lchild) p = Search(bt->lchild, x);
if(p) return p;
if(bt->rchild) p = Search(bt->rchild, x);
if(p) return p;
}
return NULL;
}
Node* Search1(bitTree bt, int x) {
if (bt == NULL) return NULL; // 空树返回NULL
if (bt->data == x) return bt; // 当前节点是目标值，返回该节点
// 递归搜索左右子树
Node* p = Search1(bt->lchild, x);
if (p != NULL) return p; // 如果在左子树找到了目标值，直接返回
return Search1(bt->rchild, x); // 否则继续在右子树查找
}
// 统计节点数目
int countLeaf(bitTree bt){
if(bt == NULL) return 0;
else if(bt->rchild == NULL && bt->lchild == NULL) return 1;
return countLeaf(bt->lchild) + countLeaf(bt->rchild);
}
// 根据先序和中序序列恢复二叉树
void preInOd(string preod, int i, int j, string inod, int k, int h, bitTree &T){
// i, j为先序范围，k,h为中序范围, T为生成树的根
T = new Node();
T->data = preod[i];
T->rchild = NULL;
T->lchild = NULL;
int m = k; // 中序头
while(m <= h){
if(inod[m] == T->data) break;
m++;
} // 寻找中序定位
if(m == k) T->lchild = NULL;
else preInOd(preod, i+1, i+m-k, inod, k, m-1, T->lchild); // 生成左子树
if(m == h) T->rchild = NULL;
else preInOd(preod,i+m-k+1, j, inod, m+1, h, T->rchild); // 生成右子树
}
void postInOd(string postod, int i, int j, string inod, int k, int h, bitTree &T) {
if (i > j || k > h) return; // 递归出口，如果遍历区间无效，返回
// 1. 获取后序遍历的最后一个元素作为根节点
T = new Node();
T->data = postod[j];
T->rchild = NULL;
T->lchild = NULL;
// 2. 在中序遍历中找到根节点的位置
int m = k;
while (m <= h) {
if (inod[m] == T->data) break;
m++;
}
// 3. 递归构建右子树
if (m == h) {
T->rchild = NULL; // 如果根节点右边没有节点，右子树为空
} else {
postInOd(postod, i, i + m - k - 1, inod, m + 1, h, T->rchild); // 构建右子树
}
// 4. 递归构建左子树
if (m == k) {
T->lchild = NULL; // 如果根节点左边没有节点，左子树为空
} else {
postInOd(postod, i, i + m - k - 1, inod, k, m - 1, T->lchild); // 构建左子树
}
}
// 树的线索化
typedef struct hrNode{
int data;
hrNode *lchild;
hrNode *rchild;
int ltag;
int rtag;
}*bitHrNode;
// 中序线索二叉树的建立
bitHrNode pre; // 指向当前遍历节点的前驱节点
void
bitHrNode InOrderThr(bitHrNode T){
hrNode* head;
head = new hrNode();
head->ltag = 0;
head->rtag = 1;
head->rchild = head; // 建立头节点
if(!T) head->lchild = head; // 若二叉树为空，则左指针回指
else{
head->lchild = T;
pre = head;
InThreading(T); // 中序遍历进行中序线索化
pre->rchild = head;
pre->rtag = 1; // 最后一个节点线索化
head->rchild = pre;
}
return head;
}
int main(){
return 0;
}