第四章 树
4.1 二叉树的顺序存储
#define MAXSIZE 16
typedef int ElemType;
typedef struct {
ElemType data[MAXSIZE];
int size;
}Tree;
//初始化二叉树
void initTree(Tree& T) {
for (int i = 0; i < MAXSIZE; i++) {
T.data[i] = 0; //假设0表示空节点
}
T.size = 0;
}
//创建二叉树
void createTree(Tree& T) {
ElemType x;
scanf("%d", &x);
int i = 0;
while (x != 999) {
T.data[i++] = x;
T.size++;
scanf("%d", &x);
}
}
//打印二叉树
void printTree(Tree T) {
for (int i = 0; i < T.size; i++) {
printf("%d ", T.data[i]);
}
printf("\n");
}
01.已知一棵二叉树按顺序存储结构进行存储，设计一个算法，求编号分别为i和j的两个
结点的最近的公共祖先结点的值。
ElemType findCommonAncestors(Tree T, int i, int j) {
if (T.data[i] != 0 && T.data[j] != 0) { //两个结点都存在在进行后续操作
//父节点的下标为 x/2
/*
1 对应数组[1,2,3,4,5,6,7]
/ \ 对应下标[0,1,2,3,4,5,6]
2 3
/ \ / \ 注意：如果是下标从0开始，
4 5 6 7 i的左孩子下标是 i*2 +1 右孩子下标是i*2+2
i的父节点是(i-1)/2
如果下标从1开始
i的左孩子是i*2,右孩纸是i*2+1
i的父节点是i/2
*/
while (i != j) {
if (i > j) {
i /= 2;
}
else {
j /= 2;
}
}
return T.data[i];
}
return 0; //0代表为空
}
4.2二叉树的链式存储
二叉树的结构
typedef int ElemType;
typedef struct BiTNode {
ElemType data; //数据域
BiTNode* lchild; //左孩子指针
BiTNode* rchild; //右孩子指针
}BiTNode,*BiTree;
创建二叉树
//前序创建二叉树
void createTree(BiTree& T) {
ElemType x;
scanf("%d", &x);
if (x == 0) { //用0代表空结点
return;
}
else {
T = (BiTNode *)malloc(sizeof(BiTNode)); //创建结点结构
T->data = x;
T->lchild = NULL;
T->rchild = NULL;
createTree(T->lchild); //递归创建左子树
createTree(T->rchild); //递归创建右子树
}
}
二叉树的前中后序遍历（递归）
//前序遍历递归
void preOrder(BiTree T) {
if (T == NULL) {
return;
}
printf("%d ", T->data);
preOrder(T->lchild);
preOrder(T->rchild);
}
//中序遍历递归
void inOrder(BiTree T) {
if (T == NULL) {
return;
}
inOrder(T->lchild);
printf("%d ", T->data);
inOrder(T->rchild);
}
//后序遍历递归
void postOrder(BiTree T) {
if (T == NULL) {
return;
}
postOrder(T->lchild);
postOrder(T->rchild);
printf("%d ", T->data);
}
大家可以发现，前中后序遍历时只有打印位置不同，其他代码完全一样，为什么在不同的位置打印会得到3种正确的遍历结果呢？为此，我们先了解一下递归序。
void f(BiTree T) {
if (T == NULL) {
return;
}
/*
递归序：每个函数都会有三次机会来到。
第一次来打印先序，第二次来打印中序，第三次来打印后序
*/
//前序
f(T->lchild);
//中序
f(T->rchild);
//后序
}
如果在三个位置都进行打印的话，输出结果是：A B D D D B E E E B A C F F F C G G G C A
先序遍历：第一次经过时打印，先序序列：A B D E C F G
中序遍历：第二次经过时打印，中序序列：D B E A F C G
后序遍历：第三次经过时打印，后序序列：D E B F G C A
前序遍历二叉树（非递归）
//前序遍历非递归
void preOrderNoRecursion(BiTree T) {
SqStack S;
initStack(S);
BiTNode* p = T; //p作为树的遍历指针
while (p || !isEmpty(S)) { //如果p不为空或者栈中还有元素
if (p) {
printf("%d ", p->data); //打印当前结点的值
push(S, p); //当前元素
p = p->lchild; //先一直走左子树
}
else {
//如果此时遍历到了空结点，证明这条路一路走到头了，弹出后再去遍历右子树
BiTNode* top = pop(S);
p = top->rchild;
}
}
}
中序遍历二叉树（非递归）
//中序遍历非递归
void inOrderNoRecursion(BiTree T) {
SqStack S;
initStack(S);
BiTNode* p = T;
while (p || !isEmpty(S)) { //如果p不为空或者栈中还有元素
if (p) {
push(S, p); //还是一路向左走
p = p->lchild;
}
else {
BiTNode* top = pop(S); //左边到头了，弹出栈顶元素并打印
printf("%d ", top->data);
p = top->rchild; //接着去走弹出元素的右子树的路
}
}
}
后序遍历二叉树（非递归）
//后序遍历非递归
void postOrderNoRecursion(BiTree T) {
SqStack S;
initStack(S);
BiTNode* p = T;
BiTNode* last = NULL; //用来记录最近一次出栈的元素
while (p || !isEmpty(S)) {
if (p) {
push(S, p); //一直往左走并且入栈元素，直接走到头
p = p->lchild;
}
else{
BiTNode* top = peek(S); //获取栈顶元素
//当栈顶没有右孩子或者栈顶的右孩子是最近出栈的一次元素
if (top->rchild == NULL||top->rchild == last) {
last = pop(S); //出栈并更新最近出栈的元素
printf("%d ", top->data); //打印出栈元素
}
//相反
else {
p = top->rchild; //去让右孩子走同样的路
}
}
}
}
前序遍历二叉树（非递归思路2）
void preOrderNoRecursion2(BiTree T) {
SqStack S;
initStack(S);
BiTNode* p = T;
if (p) {
push(S, p); //先将第一个元素进栈
while (!isEmpty(S)) {
BiTNode* top = pop(S); //弹出栈顶元素
printf("%d ", top->data); //打印栈顶元素
if (top->rchild != NULL) { //有右孩子向将右孩子进栈
push(S,top->rchild);
}
if (top->lchild != NULL) { //有左孩子再将左孩子入栈
push(S, top->lchild);
}
}
}
}
后序遍历二叉树（非递归思路2）
//后序遍历非递归思路2
void postOrderNoRecursion2(BiTree T) {
SqStack S,S2;
initStack(S);
initStack(S2);
BiTNode* p = T;
if (p) {
push(S, p);
while (!isEmpty(S)) { //先得到头、右、左的遍历顺序，将头右左的元素依次进栈到辅助栈S2中，最终S2中保存的是头右左的逆序及左右头的顺序及后序遍历结果
BiTNode* top = pop(S);
push(S2,top);
if (top->lchild != NULL) {
push(S, top->lchild);
}
if (top->rchild != NULL) {
push(S, top->rchild);
}
}
}
while (!isEmpty(S2)) { //将S2中的元素依次出栈
BiTNode* p = pop(S2);
printf("%d ", p->data);
}
}
层次遍历二叉树
//层次遍历
void levelOrder(BiTree T) {
Queue Q;
initQueue(Q);
BiTNode* p = T;
if (p) {
enQueue(Q, p); //先将根节点元素进队
while (!isEmpty(Q)) {
BiTNode* head = deQueue(Q); //出队
printf("%d "T, head->data); //打印出队元素
if (head->lchild) { //如果出队元素有左孩子先将左孩子入队
enQueue(Q, head->lchild);
}
if (head->rchild) { //如果出队元素有右孩子再将左孩子入队
enQueue(Q, head->rchild);
}
}
}
}
4.3二叉树题目
01.试给出二叉树的自下而上、从右到左的层次遍历算法。
void inverLevelOrder(BiTree T) {
//用将层次遍历结果放到栈中，在依次打印栈中的元素即可
Queue Q;
SqStack S;
initQueue(Q);
initStack(S);
BiTNode* p = T;
if (p) {
enQueue(Q, p);
while (!isEmpty(Q)) {
BiTNode* head = deQueue(Q);//队头出队
push(S, head);
if (head->lchild) {
enQueue(Q, head->lchild); //有左孩子左孩子入队
}
if (head->rchild) {
enQueue(Q, head->rchild); //有右孩子右孩子入队
}
}
}
while (!isEmpty(S)) { //栈中此时存在的遍历层数遍历的逆序列，依次打印即可
BiTNode* cur = pop(S);
printf("%d ", cur->data);
}
printf("\n");
}
02.假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。
//非递归
int getTreeHigh2(BiTree T) {
if (T == NULL) { //如果是空树直接返回0
return 0;
}
//在进行树的层次遍历时统计树的高度
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
int count = 0; //count为最终要返回树的大小
while (!isEmpty(Q)) {
int size = Q.size; //获取当前队列的长度，表示该层有几个结点。通过for循环表示结束了该层遍历，结束之后将层数count+1。
for (int i = 0; i < size; i++) {
BiTNode* head = deQueue(Q);
if (head->lchild) {
enQueue(Q, head->lchild);
}
if (head->rchild) {
enQueue(Q, head->rchild);
}
}
count++;
}
return count;
}
//递归
int getTreeHigh(BiTree T) {
if (T == NULL) { //如果是空树直接返回0
return 0;
}
if (T->lchild == NULL && T->rchild == NULL) { //如果是叶子结点高度为1
return 1;
}
int lhigh = getTreeHigh(T->lchild); //递归求左子树的高度
int rhigh = getTreeHigh(T->rchild); //递归求右子树的高度
//总高度等于左右子树的最高度+自己的高度1
return lhigh >= rhigh ? lhigh + 1 : rhigh + 1;
}
03.求树的最小深度
/*
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
例子 3 最小深度为2
/ \
9 20
/ \
15 7
10 最小深度为3
/ \
15 20
/ \
25 30
*/
//递归版本
int minDepth(BiTree T) {
if (T == NULL) {
return 0;
}
//如果是叶子结点高度为1
/*if (T->lchild == NULL && T->rchild == NULL) {
return 1;
}*/
int lhigh = getTreeHigh2(T->lchild);
int rhigh = getTreeHigh2(T->rchild);
if (lhigh == 0) {
return rhigh + 1;
}
if (rhigh == 0) {
return lhigh + 1;
}
return lhigh <= rhigh ? lhigh + 1 : rhigh + 1;
}
//非递归使用层次遍历实现
int minDepth2(BiTree T) {
if (T == NULL) {
return 0;
}
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
int count = 0; //用来记录层数（高度）
while (!isEmpty(Q)) {
int size = Q.size;
count++;
for (int i = 0; i < size; i++) {
BiTNode* head = deQueue(Q);
if (head->lchild == NULL && head->rchild == NULL) {
return count;
}
if (head->lchild) {
enQueue(Q, head->lchild);
}
if (head->rchild) {
enQueue(Q, head->rchild);
}
}
}
return count;
}
04.判断两棵树是否相同
/*
04.给你两棵二叉树的根节点 T1 和 T2 ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
1 1
/ \ / \
2 3 2 3
20 20
/ \ / \
30 30
*/
bool isSameTree(BiTree T1, BiTree T2) {
if (T1 == NULL && T2 == NULL) {
return true;
}
if (T1 == NULL && T2 != NULL || T1 != NULL && T2 == NULL) {
return false;
}
if (T1->data != T2->data) {
return false;
}
return isSameTree(T1->lchild, T2->lchild) && isSameTree(T1->rchild, T2->rchild);
}
05.判断二叉树是不是对称的
//05.判断二叉树是不是对称的
bool checkSymmetricTree(BiTree T) {
if (T == NULL) { //认为空树是对称的
return true;
}
return check(T->lchild, T->rchild);
}
bool check(BiTree left, BiTree right) {
if (left == NULL && right == NULL) { //如果左右孩子都是空返回true
return true;
}
//如果左右孩子一个为空一个不为空返回false
if (left == NULL && right != NULL || left != NULL && right == NULL) {
return false;
}
//如果左右孩子的值不等返回false
if (left->data != right->data) {
return false;
}
return check(left->lchild, right->rchild) && check(left->rchild, right->lchild);
}
06.翻转二叉树
/*
06.给你一棵二叉树的根节点T ，翻转这棵二叉树。
例子：
4 4
/ \ / \
2 7 -> 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1
2 2
/ \ -> / \
1 3 3 1
*/
void invertTree(BiTree& T) {
if (T == NULL) {
return;
}
BiTNode* temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
invertTree(T->lchild);
invertTree(T->rchild);
}
07.判断是否为平衡二叉树
/*
07.给定一个二叉树，判断它是否是高度平衡的二叉树。
一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1
例子：
3 1
/ \ / \
9 20 2 2
/ \ / \
15 7 3 3
/ \
4 4
*/
bool isBalanced(BiTree T) {
if (T == NULL) {
return true;
}
int d1 = getTreeHigh2(T->lchild);
int d2 = getTreeHigh2(T->rchild);
return d1 - d2 <= 1 && d1 - d2 >= -1 && isBalanced(T->lchild) && isBalanced(T->rchild);
}
08.利用前序遍历结果和中序遍历结果构造二叉树
//前序遍历数组是从[L1,R1]，中序遍历数组是从[L2,R2]
BiTree f(ElemType pre[], int L1, int R1, ElemType in[], int L2, int R2) {
if (L1 > R1 || L2 > R2) {
return NULL;
}
BiTNode* head = (BiTNode*)malloc(sizeof(BiTNode));
head->data = pre[L1];
int find = L2;
while (in[find] != pre[L1]) {
find++;
}
head->lchild = f(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);
head->rchild = f(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);
return head;
}
/**
给定两个整数数组 pre 和 in ，其中 pre 是二叉树的先序遍历， in 是同一棵树的中序遍历，数组大小为n
*/
BiTree buildTree(ElemType pre[], ElemType in[], int n) {
if (n == 0) {
return NULL;
}
return f(pre, 0, n - 1, in, 0, n - 1);
}
9.利用中序遍历结果和后序遍历结果构造二叉树
BiTree f(ElemType pre[], int L1, int R1, ElemType in[], int L2, int R2) {
if(L1>R1){
return NULL;
}
BiTNode* head = (BiTNode* )malloc(sizeof(BiTNode));
head->val = post[R1];
int find = L2;
while(in[find]!=post[R1]){
find++;
}
head->left = f(post,L1,L1+find-1-L2,in,L2,find-1);
head->right = f(post,L1+find-L2,R1-1,in,find+1,R2);
return head;
}
BiTree buildTree(ElemType pre[], ElemType in[], int n) {
if (n == 0) {
return NULL;
}
return f(pre, 0, n - 1, in, 0, n - 1);
}
10.二叉树按二又链表形式存储，试编写一个判别给定二叉树是否是完全二又树的算法。
bool isComplete2(BiTree T) {
if (T == NULL) {
return true;
}
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
while(!isEmpty(Q)){
BiTNode* head = deQueue(Q);
if (head) {
enQueue(Q, head->lchild);
enQueue(Q, head->rchild);
}
else {
while (!isEmpty(Q)) {
head = deQueue(Q);
if (head) {
return false;
}
}
}
}
return true;
}
11.假设二叉树采用二叉链表存储结构存储，试设计一个算法，计算-棵给定二叉树的所有
双分支结点个数。
int getDNodesCount(BiTree T) {
/*if (T == NULL) {
return 0;
}
int d1 = getDNodesCount(T->lchild);
int d2 = getDNodesCount(T->rchild);
if (T->lchild && T->rchild) {
return 1 + d1 + d2;
}
else {
return d1 + d2;
}*/
}
int getDNodesCount2(BiTree T) {
Stack S;
initStack(S);
BiTNode* p = T;
int count = 0;
while (p || !isEmpty(S)) {
if (p) {
if (p->lchild && p->rchild) {
count++;
}
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = pop(S);
p = top->rchild;
}
}
return count;
}
12.假设二叉树采用二叉链存储结构存储，设计一个算法，求先序遍历序列中第k(1<=k<=
二叉树中结点个数)个结点的值。
//递归
int count = 1;
ElemType prefindK(BiTree T, int k) {
if (T == NULL) {
return -1;
}
if (k == count) {
return T->data;
}
count++;
ElemType x= prefindK(T->lchild, k);
if (x != -1) {
return x;
}
return prefindK(T->rchild, k);
}
//非递归
ElemType prefindK2(BiTree T, int k) {
Stack S;
initStack(S);
BiTNode* p = T;
int count = 0;//用来记录当前遍历到了第几个
while (p || !isEmpty(S)) {
if (p) {
count++;
if (count == k) {
return p->data;
}
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = pop(S);
p = top->rchild;
}
}
return -1;
}
13.已知二叉树以二叉链表存储，编写算法完成:对于树中每个元素值为x的结点，删除以它为根的子树，并释放相应的空间。
//13.已知二叉树以二叉链表存储，编写算法完成:对于树中每个元素值为x的结点，删除以它为根的子树，并释放相应的空间。
void freeNode(BiTNode* root) {
if (root) {
freeNode(root->lchild);
freeNode(root->rchild);
free(root);
}
}
void delX(BiTree& T, ElemType x) {
if (T == NULL) {
return;
}
if (T->data == x) {
freeNode(T);
return;
}
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
while (!isEmpty(Q)) {
BiTNode* head = deQueue(Q);
if (head->lchild) {
if (head->lchild->data == x) {
freeNode(head->lchild);
head->lchild = NULL;
}
else {
enQueue(Q, head->lchild);
}
}
if (head->rchild) {
if (head->rchild->data == x) {
freeNode(head->rchild);
head->rchild = NULL;
}
else {
enQueue(Q, head->rchild);
}
}
}
}
14.在二叉树中查找值为x的结点，试编写算法(用C语言)打印值为x的结点的所有祖先，假设值为x的结点不多于一个。
//14.在二叉树中查找值为x的结点，试编写算法(用C语言)打印值为x的结点的所有祖先，假设值为x的结点不多于一个。
//算法思路1
ElemType* pre = (ElemType *)malloc(sizeof(ElemType)*16);
ElemType* post = (ElemType*)malloc(sizeof(ElemType)*16);
void g(BiTree T,int *i,int *j) {
if (T == NULL) {
return;
}
pre[(*i)++] = T->data; // 存储先序遍历结果
g(T->lchild,i,j);
g(T->rchild,i,j);
post[(*j)++] = T->data; // 存储后序遍历结果
}
void findAncestors(BiTree T, ElemType x) {
int n = 0, m = 0;
g(T,&n,&m);
int i = 0;
int j = 0;
for (; i < n && pre[i] != x; i++);
for (; j < n && post[j] != x; j++);
for (int p = 0; p < i; p++) {
for (int q = j + 1; q < n; q++) {
if (pre[p] == post[q]) {
printf("%d ", pre[p]);
}
}
}
printf("\n");
}
//算法思路2，利用后序遍历找到x后，栈中所保存的元素即为祖先结点
void findAncestors2(BiTree T,ElemType x) {
if (T == NULL) {
return;
}
Stack S;
initStack(S);
BiTNode* p = T;
BiTNode* last = NULL;
while (p || !isEmpty(S)) {
if (p) {
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = peek(S);
if (top->rchild == NULL || top->rchild == last) {
last = pop(S);
if (top->data == x) {
while (!isEmpty(S)) {
last = pop(S);
printf("%d ", last->data);
}
}
}
else {
p = top->rchild;
}
}
}
}
15.假设二叉树采用二又链表存储结构，设计一个算法，求非空二叉树b的宽度(即具有结点数最多的那一层的结点个数)。
//15.假设二叉树采用二又链表存储结构，设计一个算法，求非空二叉树b的宽度(即具有结点数最多的那一层的结点个数)。
int getTreeWidth(BiTree T) {
if (T == NULL) {
return 0;
}
Queue Q;
initQueue(Q);
int max = 0;
BiTNode* p = T;
enQueue(Q, p);
while (!isEmpty(Q)) {
int size = Q.size;
max = size >= max ? size:max;
for (int i = 0; i < size; i++) {
BiTNode *head = deQueue(Q);
if (head->lchild) {
enQueue(Q,head->lchild);
}
if (head->rchild) {
enQueue(Q,head->rchild);
}
}
}
return max;
}
16.设有一棵满二又树(所有结点值均不同),巳知其先序序列为pre,
设计一个算法求其后
序序列post
void findPost(ElemType pre[], int L1, int R1, ElemType post[], int L2, int R2) {
if (R1 >= L1) {
post[R2] = pre[L1];
int mid = (R1-L1) / 2;
findPost(pre, L1 + 1, L1 + mid, post, L2, L2 + mid - 1);
findPost(pre, L1 + mid + 1, R1, post, L2 + mid, R2 - 1);
}
//if (R1 >= L1) {
// post[R2] = pre[L1];
// int mid = (L1 + R1) / 2; // 正确计算 mid 的值
// int leftLength = mid - L1; // 左子树的长度
// // 递归调用左子树
// findPost(pre, L1 + 1, L1 + leftLength, post, L2, L2 + leftLength - 1);
// // 递归调用右子树
// findPost(pre, L1 + leftLength + 1, R1, post, L2 + leftLength, R2 - 1);
//}
}
17.设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表,表头指针为head.二叉树按二叉链表方式存储，链接时用叶结点的右指针域来存放单链表指针.
//递归版本前序
BiTNode* head = NULL, * prior = NULL;
BiTNode* findAllLeafNodes(BiTree T){
if (T == NULL) {
return NULL;
}
if (T->lchild == NULL && T->rchild == NULL) {
if (prior == NULL) {
head = T;
prior = T;
}
else {
prior->rchild = T;
prior = T;
}
}
findAllLeafNodes(T->lchild);
findAllLeafNodes(T->rchild);
return head;
}
//打印测试
void printAllLeafNodes(BiTNode* root) {
BiTNode* p = root;
while (p) {
printf("%d->", p->data);
p = p->rchild;
}
printf("\n");
}
//非递归中序
BiTNode* findAllLeafNodes(BiTree T){
BiTNode* head =NULL, * pre = NULL;
Stack S;
initStack(S);
BiTNode* p = T;
while (p || !isEmpty(S)) {
if (p) {
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = pop(S);
if (top->lchild == NULL && top->rchild == NULL) {
if (pre == NULL) {
head = top;
pre = top;
}
else {
pre->rchild = top;
pre = top;
}
}
p = top->rchild;
}
}
return head;
}
18.判断两棵树是否相似
bool isSimilar(BiTree T1, BiTree T2) {
if (T1 == NULL && T2 == NULL) {
return true;
}
if (T1 == NULL && T2 != NULL || T1 != NULL && T2 == NULL) {
return false;
}
return isSimilar(T1->lchild, T2->lchild) && isSimilar(T1->rchild, T2->rchild);
}
19.设计判断二叉树是否为二叉排序树的算法
ElemType min = -32767; //表示-∞
//设计判断二叉树是否为二叉排序树的算法
bool isBinarySortTree(BiTree T) {
bool b1, b2;
if (T == NULL) { //如果是空树，认为是二叉排序树
return true;
}
else {
b1 = isBinarySortTree(T->lchild); //判断左子树是否为二叉排序树
if (b1 == false || min >= T->data) { //有一个条件不成立就不满足二叉排序树的定义返回false
return false;
}
min = T->data; //让最小值作为当前左子树的根结点，进行与右子树的比较
b2 = isBinarySortTree(T->rchild);
return b2;
}
}
//方法2，中序遍历非递归判断二叉树是否为二叉排序树
bool isBinarySortTree2(BiTree T) {
if (T == NULL) {
return true;
}
BiTNode* p = T;
Stack S;
initStack(S);
while (!isEmpty(S) || p) {
if (p) {
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = pop(S);
if (top->data <= min) {
return false;
}
min = top->data;
p = top->rchild;
}
}
return true;
}
20.设计求结点在二叉排序树中层次的算法
//设计求结点在二叉排序树中层次的算法
int getNodeHigh(BiTree T, ElemType x) {
if (T == NULL) {
return 0;
}
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
int height = 0; //用来记录层数（高度）
while (!isEmpty(Q)) {
int size = Q.size;
height++;
for (int i = 0; i < size; i++) {
BiTNode* head = deQueue(Q);
if (head->data == x) {
return height;
}
if (head->lchild) {
enQueue(Q, head->lchild);
}
if (head->rchild) {
enQueue(Q, head->rchild);
}
}
}
return 0; //0代表没找到x结点
}
//设计求结点在二叉排序树中层次的算法2
int getNodeHigh2(BiTree T, ElemType x) {
if (T ==NULL) {
return 0;
}
int height = 0;
BiTNode* p = T;
while (p) {
count++;
if (x < p->data) {
p = p->lchild;
}
else if (p->data < x) {
p = p->rchild;
}
else {
return height;
}
}
return 0;
}
//设计求结点在二叉排序树中层次的递归思路3
int getNodeHigh3(BiTree T, ElemType x,int height) {
if (T == NULL) {
return 0;
}
if (x < T->data) {
return getNodeHigh3(T->lchild, x, height+1);
}
else if (T->data < x) {
return getNodeHigh3(T->rchild, x, height+1);
}
else {
return height;
}
}
21.设计一个在链式存储构造上统计二叉树结点个数的算法
//设计一个在链式存储构造上统计二叉树结点个数的算法(递归思路1)
int nodeCount = 0;
int getCount(BiTree T) {
if (T == NULL) {
return 0;
}
getCount(T->lchild);
getCount(T->rchild);
nodeCount++;
return nodeCount;
}
//设计一个在链式存储构造上统计二叉树结点个数的算法(递归思路2)
int getCount2(BiTree T) {
if (T == NULL) {
return 0;
}
return getCount2(T->lchild) + getCount2(T->rchild) + 1;
}
22.设计在二叉排序树上查找节点X的算法
//设计在二叉排序树上查找节点X的算法
BiTNode* getX(BiTree T, BiTNode* x) {
if (T == NULL) {
return NULL; // 树为空，未找到节点 X
}
if (x->data == T->data) {
return T; // 找到了节点 X
}
else if (x->data < T->data) {
return getX(T->lchild, x); // 在左子树中查找
}
else {
return getX(T->rchild, x); // 在右子树中查找
}
}
23.创建一棵二叉排序树
//创建二叉排序树
void insertNode(BiTree& T, ElemType data) {
if (T == NULL) {
// 如果树为空，则新建节点作为根节点
BiTNode* newNode = (BiTNode*)malloc(sizeof(BiTNode));
newNode->data = data;
newNode->lchild = NULL;
newNode->rchild = NULL;
T = newNode;
}
else {
// 如果树不为空，则按照二叉排序树的性质插入节点
if (data < T->data) {
insertNode(T->lchild, data); // 插入到左子树
}
else {
insertNode(T->rchild, data); // 插入到右子树
}
}
}
24.假设二叉树采用链式存储结构进行存储，root为根节点，p为任意给点的结点，请写出求从根节点到p之间路径的非递归算法【西安电子科技大学】
void getPathToNode(BiTree root, BiTNode* p) {}
//利用二叉树的后序遍历实现
void getPathToNode(BiTree root, ElemType p) {
if (root == NULL) {
return;
}
Stack S,S2;
initStack(S);
initStack(S2); //S2用来存放路径
BiTNode* cur = root;
BiTNode* last = NULL;
while (!isEmpty(S) || cur) {
if (cur) {
push(S, cur);
cur = cur->lchild;
}
else {
BiTNode* top = peek(S);
if (top->rchild == NULL || top->rchild == last) {
if (top->data == p) {
while (!isEmpty(S)) {
push(S2, pop(S));
}
break;
}
last = pop(S);
}
else {
cur = top->rchild;
}
}
}
//打印路径
while (!isEmpty(S2)) {
BiTNode* top = pop(S2);
printf("%d->", top->data);
}
printf("\n");
}
25.已知有一棵二叉链表表示的二叉树，编写程序，输出从根结点到叶子结点的最长枝上的所有结点（假设唯一），并写出算法思想。[南京航空航天大学2006 六(10 分)]
设二叉树的结点结构是（lchild,data,rchild），其中 lchild、rchild分别为指向左、右子树根的指针，data 是字符型 数据。试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。 【北京邮电大学 1997 八(20 分)】
void findLongestPath(BiTree root) {
if (root == NULL) {
return;
}
Stack S;
initStack(S);
BiTNode* p = root;
BiTNode* last = NULL;
BiTNode* longNode = NULL;
int max = 0;
while (p || !isEmpty(S)) {
if (p) {
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = peek(S);
if (top->rchild == NULL || top->rchild == last) {
if (top->lchild == NULL && top->rchild == NULL) {
if (S.length > max) {
max = S.length;
longNode = top;
}
}
last = pop(S);
}
else {
p = top->rchild;
}
}
}
getPathToNode(root, longNode->data);
}
26.设二叉树的结点具有如下的结构：（lchild,data,rchild），指针变量 T 指向该树的根结点，试设计 一个算法打印出由根结点出发到达叶结点的所有路径
//递归1
void printAllPaths(BiTree T, int path[], int pathLen) {
if (T == NULL) {
return;
}
path[pathLen++] = T->data;
if (T->lchild == NULL && T->rchild == NULL) {
printf("Path： ");
for (int i = 0; i < pathLen; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
else {
printAllPaths(T->lchild, path, pathLen);
printAllPaths(T->rchild, path, pathLen);
}
}
//思路2递归理解回溯流程
int len = 0;
void printAllPaths2(BiTree T, int path[]) {
if (T == NULL) {
return;
}
path[len++] = T->data;
if (T->lchild == NULL && T->rchild == NULL) {
printf("Path： ");
for (int i = 0; i < len; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
else {
printAllPaths2(T->lchild, path);
printAllPaths2(T->rchild, path);
}
len--;
}
//思路3非递归
void printAllPaths2(BiTree T) {
if (T == NULL) {
return;
}
Stack S;
initStack(S);
int path[100];
int len = 0;
BiTNode* p = T;
BiTNode* last = NULL;
while (!isEmpty(S) || p) {
if (p) {
push(S, p);
path[len++] = p->data;
p = p->lchild;
}
else {
BiTNode* top = peek(S);
if (top->rchild == NULL || top->rchild == last) {
last = pop(S);
if (top->lchild == NULL && top->rchild == NULL) {
for (int i = 0; i < len; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
len--;
}
else {
p = top->rchild;
}
}
}
}
27.设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不许用栈。
BiTNode* getLastPreNode(BiTree T) {
BiTNode* p = T;
while (p) {
if (p->rchild) {
p = p->rchild;
}
else if (p->lchild) {
p = p->lchild;
}
else {
return p;
}
}
return NULL;
}
28.给你一个整数 n，求恰由 n个节点组成且节点值从 1到 n 互不相同的 二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。
//不同的二叉搜索树
int numTrees(int n) {
int* dp = (int*)malloc(sizeof(int) * (n + 1));
for (int i = 0; i < n + 1; i++) {
dp[i] = 0;
}
dp[0] = 1;
dp[1] = 1;
for (int j = 2; j < n + 1; j++) {
for (int i = 0; i < j; i++) {
dp[j] += dp[i] * dp[j - 1 - i];
}
}
/*for (int i = 0; i < n; i++) {
printf("(%d,%d)\n", i, n - 1-i);
}*/
return dp[n];
}
29.给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
//递归思路1
bool hasPathSum(BiTree root, int targetSum) {
if (root == NULL) {
return false;
}
targetSum -= root->data;
if (root->lchild == NULL && root->rchild == NULL) {
return targetSum == 0;
}
return hasPathSum(root->lchild, targetSum) || hasPathSum(root->rchild, targetSum);
}
//递归思路2
bool res = false;
int sum = 0;
void process(BiTree root, int targetSum) {
if (root == NULL) {
return;
}
sum += root->data;
if (root->lchild == NULL && root->rchild == NULL && sum == targetSum) {
res = true;
}
process(root->lchild, targetSum);
process(root->rchild, targetSum);
sum -= root->data;
}
bool hasPathSum2(BiTree root, int targetSum) {
if (root == NULL) {
return false;
}
process(root, targetSum);
return res;
}
//非递归思路1
bool hasPathSum3(BiTree root, int targetSum) {
if (root == NULL) {
return false;
}
Stack S;
initStack(S);
BiTNode* p = root;
BiTNode* last = NULL;
int sum = 0;
while (!isEmpty(S) || p) {
if (p) {
sum += p->data;
if (p->lchild == NULL && p->rchild == NULL && sum == targetSum) {
return true;
}
push(S, p);
p = p->lchild;
}
else {
BiTNode * top = peek(S);
if (top->rchild == NULL || top->rchild == last) {
last = pop(S);
sum -= last->data;
}
else {
p = top->rchild;
}
}
}
return false;
}
//非递归思路2
bool hasPathSum4(BiTree root, int targetSum) {
if (root == NULL) {
return false;
}
Stack S;
initStack(S);
BiTNode* p = root;
BiTNode* last = NULL;
while (!isEmpty(S) || p) {
if (p) {
targetSum -= p->data;
if (p->lchild == NULL && p->rchild == NULL && 0 == targetSum) {
return true;
}
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = peek(S);
if (top->rchild == NULL || top->rchild == last) {
last = pop(S);
targetSum += last->data;
}
else {
p = top->rchild;
}
}
}
return false;
}
30.如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
/*
30.如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
*/
int val = 0;
bool res = true;
void process(BiTree root) {
if (root == NULL) {
return;
}
if (root->data != val) {
res = false;
}
process(root->lchild);
process(root->rchild);
}
bool isUnivalTree(BiTree root) {
if (root == NULL) {
return true;
}
val = root->data;
process(root);
return res;
}
//递归思路2
bool process(BiTree T,int val) {
if (T == NULL) {
return true;
}
if (T->data != val) {
return false;
}
return process(T->lchild, val) && process(T->rchild, val);
}
bool isUnivalTree(BiTree root) {
if (root == NULL) {
return true;
}
return process(root, root->data);
}
31.编写递归程序将二叉树逆时针旋转 90 度打印出来
void printTreeSideways(BiTree root, int depth) {
if (root == NULL) {
return;
}
printTreeSideways(root->rchild, depth + 1);
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", root->data);
printTreeSideways(root->lchild, depth + 1);
}
32.已知一二叉树中结点的左右孩子为 lchild和 rchild，p 指向二叉树的某一结点。请编写一个非递归函数 postfirst(p),求p所对应子树的第一个后序遍历结点。【浙江大学 1998 六(10 分)】
BiTNode* postfirst(BiTree T, BiTNode *p) {
if (p == NULL) {
return NULL;
}
BiTNode* cur = p;
while (cur) {
if (cur->lchild) {
cur = cur->lchild;
}
else if (cur->rchild) {
cur = cur->rchild;
}
else {
return cur;
}
}
return NULL;
}
33.二叉树结点的平衡因子（bf）定义为该结点的左子树高度与
右子树高度之差。设二叉树结点结构为：(lchild,data,bf,rchild),
lchild,rchild 是左右儿子指针；data 是数据元素；bf 是平衡因子，编写递归及非递归算法计算二叉树中各个结点平
衡因子【中国石油大学】。
int computeHeightAndBF(BiTree& root) {
if (root == NULL) {
return 0;
}
int leftHeight = computeHeightAndBF(root->lchild);
int rightHeight = computeHeightAndBF(root->rchild);
root->bf = leftHeight - rightHeight;
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
//根据bf属性来判断二叉树是否为平衡二叉树
bool isBalanced2(BiTree root) {
if (root == NULL) {
return true;
}
if (root->bf > 1 || root->bf < -1) {
return false;
}
bool lchildInfo = isBalanced2(root->lchild);
if (lchildInfo == false) {
return false;
}
return isBalanced2(root->rchild);
}
int getHeight2(BiTree root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight2(root->lchild);
int rightHeight = getHeight2(root->rchild);
// 返回左右子树中较大的高度加上当前节点的高度（1）
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
//思路2 非递归
void computeBF(BiTree& root) {
Stack S;
initStack(S);
BiTNode* p = root;
BiTNode* last = NULL; //记录最近访问的一个元素（最近出栈）
while (p || !isEmpty(S)) {
if (p) {
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = peek(S);
//如果栈顶结点右子树为空或者已经访问过了右子树
if (top->rchild == NULL || top->rchild == last) {
last = pop(S);
int leftHeight = (top->lchild == NULL) ? 0 : getHeight2(top->lchild);
int rightHeight = (top->rchild == NULL) ? 0 : getHeight2(top->rchild);
top->bf = leftHeight - rightHeight;
}
else {
p = top->rchild;
}
}
}
}
34.设T是一棵给定的查找树,试编写一个在树中删除根结点为 a 的子树的程序,要求在删除的过程中释 放该子树所有结点所占有的存储空间,这里假设树 T 中结点所占有的存储空间是通过动态存储分配取得的, 其结点的形式为:（lchild,data,rchild）【复旦大学 1999 七、 (15 分)】
/*
34.设T是一棵给定的查找树,试编写一个在树中删除根结点为 a 的子树的程序,要求在删除的过程中释 放该子树所有结点所占有的存储空间,这里假设树 T 中结点所占有的存储空间是通过动态存储分配取得的, 其结点的形式为:（lchild,data,rchild）【复旦大学 1999 七、 (15 分)】
*/
void freeBiTNodes(BiTNode* node) {
if (node == NULL) {
return;
}
freeBiTNodes(node->lchild);
freeBiTNodes(node->rchild);
free(node);
}
void delteSubtree(BiTree& T, ElemType a) {
if (T == NULL) {
return;
}
if (T->data == a) {
freeBiTNodes(T);
T = NULL;
return;
}
if (T->data > a) {
delteSubtree(T->lchild, a);
}
else {
delteSubtree(T->rchild, a);
}
}
35.编写一算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双链表，算法返回 头结点的地址（不得开辟新的空间，在原来的树上进行修改）。【东北大学 1999 四(13 分)】
typedef int ElemType;
typedef struct BiTNode{
ElemType data;
BiTNode* lchild;
BiTNode* rchild;
bool ltag = true;
bool rtag = true;
}BiTNode,*BiTree;
BiTNode* dummyhead = NULL;
BiTNode* dummytail = NULL;
void initHead() {
dummyhead = (BiTNode*)malloc(sizeof(BiTNode));
dummyhead->lchild = NULL;
dummyhead->rchild = NULL;
dummytail = dummyhead;
}
void createLeafList(BiTree& T) {
if (T == NULL) {
return;
}
// 递归处理左子树
if (T->ltag) {
createLeafList(T->lchild);
}
// 处理叶子节点
if (T->lchild == NULL && T->rchild == NULL) {
if (T->rchild != NULL) {
dummyhead->rchild->lchild = T;
}
T->rchild = dummyhead->rchild;
T->lchild = dummyhead;
dummyhead->rchild = T;
T->ltag = false;
T->rtag = false;
}
// 递归处理右子树
if (T->rtag) {
createLeafList(T->rchild);
}
}
void createLeafList2(BiTree& T) {
if (T == NULL) {
return;
}
createLeafList(T->rchild);
createLeafList(T->lchild);
// 处理叶子节点
if (T->lchild == NULL && T->rchild == NULL) {
dummytail->rchild = T;
T->lchild = dummytail->rchild;
dummytail = T;
}
}
void createLeafList3(BiTree& T) {
if (T == NULL) {
return;
}
createLeafList(T->lchild);
// 处理叶子节点
if (T->lchild == NULL && T->rchild == NULL) {
dummytail->rchild = T;
T->lchild = dummytail->rchild;
dummytail = T;
}
createLeafList(T->rchild);
}
//打印结果
void printCreateLeafList(BiTree T) {
initHead();
createLeafList(T);
BiTNode* p = dummyhead->rchild;
while (p) {
printf("%d->", p->data);
p = p->rchild;
}
printf("\n");
}
36.在二叉树中增加一行，给定一个二叉树的根 root 和两个整数 val和 depth ，在给定的深度 depth 处添加一个值为 val的节点行。注意，根节点 root位于深度 1
/*
36.在二叉树中增加一行，给定一个二叉树的根 root 和两个整数 val和 depth ，在给定的深度 depth 处添加一个值为 val的节点行。注意，根节点root位于深度1
*/
void addOneRow(BiTree &T, int val, int depth) {
if (depth < 1) {
return;
}
//如果要在第一层加入，申请新的根结点存储val值，让原来的根节点变成新根节点的左孩子
if (depth == 1) {
BiTNode* head = (BiTNode*)malloc(sizeof(BiTNode));
head->data = val;
head->lchild = T;
head->rchild = NULL;
T = head;
return;
}
int cur = 1;
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
while (!isEmpty(Q)) {
int size = Q.size;
for (int i = 0; i < size; i++) {
BiTNode* top = deQueue(Q);
if (cur == depth - 1) {
BiTNode* left = (BiTNode*)malloc(sizeof(BiTNode));
BiTNode* right = (BiTNode*)malloc(sizeof(BiTNode));
left->data = val;
right->data = val;
left->lchild = top->lchild;
left->rchild = NULL;
right->rchild = top->rchild;
right->lchild = NULL;
top->lchild = left;
top->rchild = right;
}
else {
if (top->lchild) {
enQueue(Q, top->lchild);
}
if (top->rchild) {
enQueue(Q, top->rchild);
}
}
}
cur++;
}
}
//递归思路
int d, v;
void dfs(BiTree& T, int cur) {
if (T == NULL) {
return;
}
if (cur == d - 1) {
BiTNode* left = (BiTNode*)malloc(sizeof(BiTNode));
BiTNode* right = (BiTNode*)malloc(sizeof(BiTNode));
left->data = v;
right->data = v;
left->lchild = T->lchild;
left->rchild = NULL;
right->rchild = T->rchild;
right->lchild = NULL;
T->lchild = left;
T->rchild = right;
}
else {
dfs(T->lchild, cur + 1);
dfs(T->rchild, cur + 1);
}
}
void addOneRow2(BiTree& T, int val, int depth) {
d = depth;
v = val;
if (d == 1) {
BiTNode* head = (BiTNode*)malloc(sizeof(BiTNode));
head->data = v;
head->lchild = T;
head->rchild = NULL;
T = head;
return;
}
dfs(T, 1);
}
4.4小根堆
#define InitSize 128
typedef int ElemType;
// 定义小根堆结构体
typedef struct MinHeap {
int capacity; // 堆的最大容量
int size; // 堆中当前元素的个数
ElemType elements[InitSize]; // 堆中的元素数组，用指针数组实现
} MinHeap;
// 创建小根堆
MinHeap* createMinHeap() {
MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
heap->capacity = InitSize;
heap->size = 0;
return heap;
}
// 交换两个节点
void swap(ElemType arr[], int i, int j) {
ElemType temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 向下调整函数，维护小根堆性质
void down(MinHeap* heap, int index) {
int smallest = index;
int left = 2 * index + 1;
int right = left + 1;
if (left < heap->size && heap->elements[left] < heap->elements[smallest])
smallest = left;
if (right < heap->size && heap->elements[right] < heap->elements[smallest])
smallest = right;
if (smallest != index) {
swap(heap->elements, smallest, index);
down(heap, smallest);
}
}
// 插入新节点
void insertNode(MinHeap* heap, ElemType x) {
if (heap->size == heap->capacity) {
printf("堆已满.\n");
return;
}
int i = heap->size;
heap->size++;
heap->elements[i] = x;
while (i != 0 && heap->elements[(i - 1) / 2] > heap->elements[i]) {
swap(heap->elements, i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
//判断小根堆是否为空
bool isEmpty(MinHeap* heap) {
return heap->size == 0;
}
//弹出堆顶元素，并维持剩下元素依然为一个小根堆
ElemType poll(MinHeap* heap) {
if (isEmpty(heap)) {
return NULL;
}
swap(heap->elements, 0, heap->size - 1);
heap->size--;
down(heap, 0);
return heap->elements[heap->size];
}
int main() {
MinHeap* heap = createMinHeap();
insertNode(heap, 10);
insertNode(heap, 7);
insertNode(heap, 8);
insertNode(heap, 5);
insertNode(heap, 6);
while (!isEmpty(heap)) {
ElemType x = poll(heap);
printf("%d ", x);
}
printf("\n");
return 0;
}
4.5huffman树
37.给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为 huffman 树。（1）给出构造 huffman 树 的算法。（2）给定项及相应的权如下表：画出执行上述算法后 得到的 huffman 树。（3）并求出WPL（带权路径长度）（4）用 c 语言编写构造 huffman 树的程序. 【浙江大学 2000 七 (18 分)】
#define InitSize 128
typedef struct TreeNode {
int id; //编号
int weight; //权重
char value; //值
TreeNode* left;
TreeNode* right;
}TreeNode,*HuffmanTree ;
// 定义小根堆结构体
typedef struct MinHeap {
int capacity; // 堆的最大容量
int size; // 堆中当前元素的个数
TreeNode* elements[]; // 堆中的元素数组，用指针数组实现
} MinHeap;
// 创建小根堆
MinHeap* createMinHeap() {
MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap) + sizeof(TreeNode*) * InitSize);
heap->capacity = InitSize;
heap->size = 0;
return heap;
}
// 交换两个节点
void swap(TreeNode* arr[], int i, int j) {
TreeNode* temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 向下调整函数，维护小根堆性质
void down(MinHeap* heap, int index) {
int smallest = index;
int left = 2 * index + 1;
int right = left + 1;
if (left < heap->size && heap->elements[left]->weight < heap->elements[smallest]->weight)
smallest = left;
if (right < heap->size && heap->elements[right]->weight < heap->elements[smallest]->weight)
smallest = right;
if (smallest != index) {
swap(heap->elements, smallest, index);
down(heap, smallest);
}
}
// 插入新节点
void insertNode(MinHeap* heap, TreeNode* node) {
if (heap->size == heap->capacity) {
printf("堆已满.\n");
return;
}
int i = heap->size;
heap->size++;
heap->elements[i] = node;
while (i != 0 && heap->elements[(i - 1) / 2]->weight > heap->elements[i]->weight) {
swap(heap->elements, i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
//判断小根堆是否为空
bool isEmpty(MinHeap* heap) {
return heap->size == 0;
}
//弹出堆顶元素，并维持剩下元素依然为一个小根堆
TreeNode* poll(MinHeap* heap) {
if (isEmpty(heap)) {
return NULL;
}
swap(heap->elements, 0, heap->size - 1);
heap->size--;
down(heap, 0);
return heap->elements[heap->size];
}
// 创建 Huffman 树的函数
HuffmanTree buildHuffmanTree(int weights[], char values[], int n) {
MinHeap* heap = createMinHeap();
// 创建初始的树叶节点，并插入到小根堆中
for (int i = 0; i < n; ++i) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->id = i + 1;
newNode->weight = weights[i];
newNode->value = values[i];
newNode->left = NULL;
newNode->right = NULL;
insertNode(heap, newNode);
}
for (int i = 0; i < heap->size; i++) {
printf("%d ", heap->elements[i]->weight);
}
printf("\n");
// 循环构建 Huffman 树
while (heap->size > 1) {
TreeNode* left = poll(heap);
TreeNode* right = poll(heap);
// 创建新节点作为它们的父节点
TreeNode* parent = (TreeNode*)malloc(sizeof(TreeNode));
parent->id = -1; // 为了区分非叶子节点
parent->weight = left->weight + right->weight;
parent->value = ' ';
parent->left = left;
parent->right = right;
// 插入新节点到小根堆中
insertNode(heap, parent);
}
// 弹出堆中最后一个节点，即为 Huffman 树的根节点
TreeNode* root = poll(heap);
// 释放堆内存
free(heap);
return root;
}
// 打印 Huffman 树
void printTree(TreeNode* root) {
if (root == NULL) return;
printf("(%d, %d,%c)\n", root->id, root->weight, root->value);
printTree(root->left);
printTree(root->right);
}
// 递归计算 Huffman 树的 WPL
int calculateWPL(TreeNode* root, int depth) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) {
return root->weight * depth;
}
return calculateWPL(root->left, depth + 1) + calculateWPL(root->right, depth + 1);
}
int main() {
int weights[] = { 15,6,7,12,25,4,6,1,15 };
char values[] = { 'A','B','C','D','E','F','G','H','I' };
HuffmanTree T = buildHuffmanTree(weights, values, 9);
int res = calculateWPL(T, 0);
printTree(T);
printf("WPL = %d\n", res);
return 0;
}
4.4先序线索二叉树
typedef int ElemType;
typedef struct ThreadNode{
ElemType data; //数据域
ThreadNode* lchild;
ThreadNode* rchild; //左右孩子指针
int ltag, rtag; //前驱后继线索
}ThreadNode,*ThreadBinaryTree;
//初始化二叉树
void initTree(ThreadBinaryTree& T) {
T = NULL;
}
//创建二叉树
void createTree(ThreadBinaryTree& T) {
ElemType x;
scanf("%d", &x);
if (x == 0) {
return;
}
else {
T = (ThreadNode*)malloc(sizeof(ThreadNode));
T->data = x;
T->lchild = NULL;
T->rchild = NULL;
T->ltag = 0;
T->rtag = 0;
createTree(T->lchild);
createTree(T->rchild);
}
}
//普通二叉树的先序遍历
void printPreTree(ThreadBinaryTree T) {
if (T != NULL) {
printf("%d ", T->data);
printPreTree(T->lchild);
printPreTree(T->rchild);
}
}
//先序遍历给二叉树线索化
void preThread(ThreadBinaryTree& p, ThreadBinaryTree& pre){
if (p != NULL) {
if (p->lchild == NULL) {
p->lchild = pre;
p->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL) {
pre->rchild = p;
pre->rtag = 1;
}
pre = p;
if (p->ltag == 0) {
preThread(p->lchild, pre);
}
if (p->rtag == 0) {
preThread(p->rchild, pre);
}
}
}
//创建先序搜索二叉树
void createPreThreadTree(ThreadBinaryTree& T) {
ThreadNode* pre = NULL;
if (T != NULL) {
preThread(T, pre);
pre->rchild = NULL;
pre->rtag = 1;
}
}
//线索二叉树的先序遍历(递归)
void printPreThreadTree(ThreadBinaryTree T) {
if (T != NULL) {
printf("%d ", T->data);
if (T->ltag == 0) {
printPreThreadTree(T->lchild);
}
else {
printPreThreadTree(T->rchild);
}
}
}
//线索二叉树的先序遍历（非递归）
void printPreThreadTree2(ThreadBinaryTree T) {
ThreadNode* p = T;
while (p != NULL) {
printf("%d ", p->data);
if (p->ltag == 0) {
p = p->lchild;
}
else {
p = p->rchild;
}
}
}
4.5中序线索二叉树
//中序遍历给二叉树线索化
void inThread(ThreadBinaryTree& p, ThreadBinaryTree& pre) {
if (p != NULL) {
inThread(p->lchild, pre);
if (p->lchild == NULL) {
p->ltag = 1;
p->lchild = pre;
}
if (pre != NULL && pre->rchild == NULL) {
pre->rtag = 1;
pre->rchild = p;
}
pre = p;
inThread(p->rchild, pre);
}
}
//创建先序搜索二叉树
void createInThreadTree(ThreadBinaryTree& T) {
ThreadNode* pre = NULL;
if (T != NULL) {
inThread(T, pre);
pre->rtag = 1;
pre->rchild = NULL;
}
}
//线索二叉树的先序遍历（非递归）
void printPreThreadTree2(ThreadBinaryTree T) {
ThreadNode* first = T;
while (first->ltag == 0) {
first = first->lchild;
}
ThreadNode* p = first;
while (p != NULL) {
printf("%d ", p->data);
if (p->rtag == 0) {
p = p->rchild;
while (p->ltag == 0) {
p = p->lchild;
}
}
else {
p = p->rchild;
}
}
}
题目1：写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法。
ThreadNode* inpostPre(ThreadBinaryTree T, ThreadBinaryTree p) {
ThreadNode* q = NULL; //最终要找的p在后序中前驱结点
//p结点有右孩子的时候
if (p->rtag == 0) {
q = p->rchild;
}
//p结点无右孩子但是有左孩子时
else if (p->ltag == 0) {
q = p->lchild;
}
//同时没有左右孩子
else {
while (p->ltag == 1 && p->lchild != NULL) {
p = p->lchild;
}
if (p->ltag == 0) {
q = p->lchild;
}
}
return q;
}