image.png
注意：审题注意，自己搞错了题目要求
void leveltrave(BiTree T)
{
Queue q;
BiTree bi = T;
InQueue(q,bi); //函数名称写错，使用EnQueueu,不是In
while (!IsEmpty(q))
{
DeQueue(q,bi);
visit(bi);
if (bi->lchild != NULL)
InQueue(q,bi->lchild);
if (bi->rchild != NULL)
InQueue(q,bi->rchild);
}
}
参考答案：
void InvertLevel(BiTree bt)
{
Stack s;
Queue q;
if (bt != NULL) {
InitStack(s);
InitQueue(q);
EnQueue(q,bt);
while (!IsEmpty(q))
{
DeQueue(p);
Push(s,p);
if (p->lchild)
EnQueue(q,p->lchild);
if (p->rchild)
EnQueue(q,p->rchild);
}
while (!IsEmpty(s)) {
Pop(s,p);
visit(p);
}
}
}
image.png
int BiTreeDepth(BiTree bt)
{
int depth = 0;
if (bt)
{
BiNode* Stack[maxSize];
int top = -1;
BiNode *p=bt,r=NULL;
while (p || top != -1){
if (p) {
Stack[++top] = p;
p = p->lchild;
}
else {
p = Stack[top];//这里只是访问，不是出栈
if (p->rchild != NULL && p->rchild != r) {
p = p->rchild;
Stack[++top] = p;
}
else {
p = Stack[top--];
visit(p);
if (top + 1 > depth) depth = top + 1;
r = p;
p = NULL;
}
}
}
}
return depth;
}
eg.
当访问一个结点的时候，栈中的内容恰好是*p结点的所有祖先结点，从栈
底结点到栈顶结点再到*p结点
刚好构成一个从根结点到*p结点的一条路径。很多算法使用这个特性进行求
解，比如计算根结点到某一个结点的路径，求两个结点的公共祖先结点都可以这样计算
参考答案：
算法思想：
使用层次遍历的算法，level记录当前的层次，设置变量last指向当前层最右结点。
每次层次遍历出出队时候和last比较，如果相等，层次加一，并让last指向下一层最后一个结点
eg.重要：每一层访问结束的时候加一，并且每一层访问结束的时候，下一层的所有结点已经放入了队列当中
int Btdepth(BiTree T)
{
if (T == NULL)
return 0;
int front = -1, rear = -1;
int last = 0, level = 0;
BiTree Q[maxSize];
Q[++rear] = T;
BiTree p;
while(front<rear){
p = Q[++front];
if (p->lchild != NULL)
Q[++rear] = p->lchild;
if (p->rchild != NULL)
Q[++rear] = p->rchild;
if (front == last)
level++, last = rear;
}
return level;
}
这是递归的写法，但是不适用本题
int BTdepth(BiTree bt)
{
if (bt == NULL)
return 0;
int ldep = BTdepth(bt->lchild);
int rdep = BTdepth(bt->rchild);
return ldep > rdep ? ldep + 1 : rdep + 1;
}
image.png
BiTree BuildBiTree(int A[], int B[], int L1, int R1, int L2, int R2)
{
if (L1 <= R1) {
BiNode*p = (BiNode*)malloc(sizeof(BiNode));
p->data = A[L1];
for(int i=L2;i<=R2;i++)
if (B[i] == A[L1]) {
mid = i;
break;
}
p->lchild = BuildBiTree(A,B,L1+1,mid-L2+L1,L2,mid-1);
p->rchild = BuildBiTree(A,B,mid-L2+L1+1,R1,mid+1,R2);
return p;
}
return NULL;
}
参考过程：
BiTree PreInCreat(ElemType A[], ElemType B[], int l1, int h1, int l2, int h2)
{
root = (BiTNode*)malloc(sizeof(BiTNode));
root->data = A[l1];
for (i = l2; B[i] != root->data; i++);
llen = i - l2;
rlen = h2 - i;
if (llen)
root->lchild = PreInCreat(A, B, l1 + 1，l1 + rlen, l2, l2 + len1 - 1);
else
root->lchild = NULL;
if (rlen)
root->rchild = PreInCreat(A, B, h1 - rlen + 1, h1, h2 - rlen + 1, h2);
else
root->rchild = NULL;
return root;
}
image.png
算法思想：
使用层次遍历的思想，对这个二叉树bt进行层次遍历；如果她是一个完全二叉树，那么，
她的第一个非双分支结点之后的结点应该都是叶子结点
bool isPerfectTree(BiTree bt)
{
if (bt != NULL)
{
Queue q;
BiTNode *p;
InitQueue(q);
EnQueue(q);
int flag = true;
while (!IsEmpty(q)) {
p = Pop(q);
if(p->lchild){
EnQueue(p->lchild);
if (flag == false)//如果再第一个非双分支结点之后出现了非叶结点，错误
return false;
}
if (p->rchild) {
EnQueue(p->rchild);
if (flag == false)
return false;
}
//遇到第一个非双分支结点的时候，flag标记为false
if (p->lchild == NULL || p->rchild == NULL)
flag = false;
}
}
return true;
}
参考答案：思路是完全一致的，只是实现上有一丝丝的不同
bool IsComplete(BiTree T)
{
InitQueue(Q);
if (!T)
return 1;
EnQueue(T);
while (!IsEmpty(Q)) {
DeQueue(Q,p);
if (p) {
EnQueue(p->lchild);
EnQueue(p->rchild);
}
else {
while (!IsEmpty(Q)) {
DeQueue(Q,p);
if (p)
return 0;
}
}
}
return 1;
}
image.png
int num(BiTree bt)
{
if (bt == NULL)
return 0;
int sum;
int lnum = num(bt->lchild);
int rnum = num(bt->rchild);
if (bt->lchild && bt->rchild)
sum = lnum + rnum + 1;
else
sum = lnum + rnum;
return sum;
}
参考答案：
int DsonNodes(BiTree bt)
{
if (bt == NULL)
return 0;
else if (bt->lchild != NULL && bt->rchild != NULL)
return DsonNodes(bt->lchild) + DsonNodes(bt->rchild) + 1;
else
return DsonNodes(bt->lchild) + DsonNodes(bt->rchild);
}
image.png
BiTree swap(BiTree bt)
{
if (bt == NULL)
return NULL;
BiTree LChild = bt->lchild;
BiTree RChild = bt->rchild;
bt->lchild = swap(RChild);
bt->rchild = swap(LChild);
return bt;
}
参考答案：
void swap(BiTree bt)
{
if (bt) {
swap(bt->lchild);
swap(bt->rchild);
temp = bt->lchild;
bt->lchild = bt->rchild;
bt->rchild = temp;
}
}
image.png
算法思想：
使用先序遍历的思想，当访问第k个结点的时候，返回数值
void find(BiTree bt,int k, ElemType &e)
{
BiTNode *Stack[maxSize];
int top = -1,count=0;
Stack[++top] = bt;
while (top != -1) {
p = Stack[top--];
count++;
if (count == k) {
e = p->data;
return;
}
if (p->rchild)
Stack[++top] = p->rchild;
if (p->lchild)
Stack[++top] = p->lchild;
}
}
参考方法：写的不是很好，不美观
int i = 1;
ElemType PreNode(BiTree b, int k)
{
if (b == NULL)
return '#';
if (i == k)
return b->data;
i++;
ch = PreNode(b->lchild,k);
if (ch != '#')
return ch;
ch = PreNode(b->rchild,k);
return ch;
}
image.png
算法思想：
从根结点递归访问每个结点，如果数值等于x，释放其子树每个结点
BiTree remove(BiTree bt, int x)
{
if (bt == NULL)
return NULL;
if (bt == x) {
del(bt);
return NULL;
}
bt->lchild = remove(bt->lchild);
bt->rchild = remove(bt->rchild);
return bt;
}
void del(BiTree bt)
{
if (bt != NULL) {
del(bt->lchild);
del(bt->rchild);
free(bt);
}
}
参考方法：
参考方法使用了层序遍历，差不多的
void DeleteXTree(BiTree bt)
{
if (bt) {
DeleteXTree(bt->lchild);
DeleteXTree(bt->rchild);
free(bt);
}
}
void Search(BiTree bt, ElemType x)
{
BiTree Q[maxSize];
if (bt) {
if (bt->data == x) {
DeleteXTree(bt);
exit(0);
}
InitQueue(Q);
EnQueue(Q,bt);
while (!IsEmpty(Q)) {
DeQueue(Q,p);
if (p->lchild){
if (p->lchild->data == x) {
DeleteXTree(p->lchild);
p->lchild = NULL;
}
else
EnQueue(Q,p->lchild);
}
if (p->rchild) {
if (p->rchild->data == x) {
DeleteXTree(p->rchild);
p->rchild = NULL;
}
else
EnQueue(Q,p->rchild);
}
}
}
}
image.png
算法思想：
后续遍历的非递归算法，当一个元素p出栈的时候，栈中保存的是
从p到根结点路径中p的所有祖先结点，因此每次出栈的时候判断
当前出栈的结点是不是等于x,若是，则输出所有栈中的结点
算法思想（简洁一点）：
采用非递归的后序遍历，最后访问根节点，当访问到结点值为x的时候，
栈中的所有元素均为该结点的祖先，依次出栈打印即可
bool print(BiTree bt, ElemType x)
{
if (bt == NULL)
return false;
BiTNode *Stack[maxSize];
BiTNode *p = bt,r=NULL;
int top = -1;
while (p || top != -1) {
if (p) {
Stack[++top] = p;
p = p->lchild;
}
else {
p = Stack[top]; //查看栈顶的元素
if (p->rchild != NULL && p->rchild != r) {
//如果当前结点有右子树并且没有访问过这个右子树
p = p->rchild;
/*
这两句可以加上，省略也可以
Stack[++top] = p->rchild;
p = p->rchild;
*/
}
else {
p = Stack[top--];
if (p->data == x) {
while (top != -1) {
p = Stack[top--];
visit(p);
}
return true;
}
p = NULL;
r = NULL;
}
}
}
return false;
}
算法思想：
采用非递归的后序遍历，最后访问根节点，当访问到结点值为x的时候，
栈中的所有元素均为该结点的祖先，依次出栈打印即可
参考方法：书上写的参考方法写的太不好了，直接放弃
算法思想：使用后序遍历的非递归算法，当元素出栈，栈中保存的是该元素的所有前驱结点。
这里使用了两次遍历，使用Stack1，Stack2保存结果；
typedef struct {
BiTNode *LLINK, *RLNK;
ElemTypde INFO;
}BiTNode,*BiTree;
bool ANCESTOR(BiTNode *root, BiTNode *p, BiTNode *q, BiTNode *&r)
{
BiTNode*Stack1[maxSize];
BiTNode*Stack2[maxSize];
int top1 = -1, top2 = -1;
int p1 = root, p2 = root, r1 = NULL, r2 = NULL;
while (p1 || top1 != -1) {
if (p1) {
Stack1[++top1] = p1;
p1 = p1->lchild;
}
else {
p1 = Stack1[top1];
if (p1->rchild && p1->rchild != r) {
p1 = p1->rchild;
Stack[++top1] = p1;
p1 = p1->lchild;
}
else {
p1 = Stack1[top1--];
if (p1 == p)
break; //跳出while循环
r1 = p1;
p1 = NULL;
}
}
}
while (p2 || top != -1) {
if (p2) {
Stack2[++top2] = p2;
p2 = p2->lchild;
}
else {
p2 = Stack2[top2];
if (p2->rchild && p2->rchild != r) {
p2 = p2->rchild;
Stack2[++top2] = p2;
p2 = p2->lchild;
}
else {
p2 = Stack2[top2--];
if (p2 == q)//跳出while循环
break;
r2 = p2;
p2 = NULL;
}
}
}
while (top1 > top2) p1 = Stack1[top1--];
while (top1 < top2) p2 = Stack2[top2--];
while (top1 != -1) {
if (Stack1[top1] != Stack2[top2]) {
top1--;
top2--;
}
else {
r = Stack1[top1];
return true;
}
}
return false;
}
参考答案：
算法思想：
采用后续遍历非递归算法，栈中存放二叉树的结点的指针，当访问到了某一
个结点的时候，栈中的所有元素都是该结点的祖先。我们假设p在q的前面，
那么后续遍历一定先遍历到结点p,栈中的元素都是p的祖先，此时把栈中的元
素保存到另外一个辅助栈中，继续遍历到结点q时候，将栈中的元素冲栈顶开
始和辅助栈进行匹配，第一个匹配的元素就是他们的最近公共祖先。
eg.书中给点源码可读性非常差，当然第一种方法可读性是非常好的，只是效
率会慢那么一丢丢而已，需要遍历两次，原来的代码只需要在我下面标注的
地方增加一个if判断逻辑即可，将栈中的内容复制到辅助栈中即可。
image.png
我还是写一写吧，希望某人能明白我这样做的原因，但我觉得没有人知道我
为啥还是要浪费时间重新写这个的原因。
bool ANCESTOR(BiTNode *root, BiTNode *p, BiTNode *q, BiTNode *&r)
{
BiTNode *Stack1[maxSize];
BiTNode *Stack2[maxSize];
BiTNode *Stack[maxSize];
int top1 = -1, top2 = -1,top=-1;
BiTNode *pp= root,r=NULL;
while (pp != NULL || top != -1) {
if (pp) {
Stack[++top] = pp;
pp = pp->lchild;
}
else {
pp = Stack[top];
if (pp->rchild && pp->rchild != r) {
pp = pp->rchild;
Stack[++top] = pp;
pp = pp->lchild;
}
else {
pp = Stack[top--];
//处理逻辑
if (pp == p) {
top1 = top;
for (int i = 0; i <= top; i++) Stack1[i] = Stack[i];
}
if (pp == q) {
top2 = top;
for (int i = 0; i <= top; i++) Stack2[i] = Stack[i];
}
//
r = pp;
pp = NULL;
}
}
}
/*
这里寻找他们的公共祖先
*/
return false;
}
image.png
算法思想：
使用层序遍历的思想，使用num记录每一层的结点的个数，当遍历到某一层的最后一个结点的时候，
若num>width，更新width，然后num置为0，同时把last指向下一层最后一个结点对应的下标。
int BiTreeWidth(BiTree bt)
{
Queue Q[maxSize];
int front = -1, rear = -1, last = 0,width=0,num=0;
BiTNode *p;
Q[++rear] = bt;
while (front < rear) {
p = Q[++front];
num++;
if (p->lchild)
Q[++rear] = p->lchild;
if (p->rchild)
Q[++rear] = p->rchild;
if (front == last) {
if (num > width)
width = num;
num = 0;
last = rear;
}
}
return width;
}
个人更加习惯这样的书写方式,如果没有思路我就可以使用这个看看：
void dfs(int num[], BiTree bt, int cur)
{
if (bt) {
num[cur]++;
dfs(num,bt->lchild,cur+1);
dfs(num,bt->rchild,cur+1);
}
}
int WidthOfTree(BiTree bt)
{
int num[maxSize];
for (int i = 1; i <= maxSize; i++)
num[i] = 0;
dfs(num,bt,1);
int width = 0;
for (i = 1; i <= maxSize; i++)
if (num[i] > width)
width = num[i];
}
题解的方法：
采用层次遍历的方法求出所有结点的层次，并将所有的结点和对应的层
次放在一个队列当中，然后通过扫描队列求出各层的结点总数，最大的层数
就是二叉树的宽度，相当于是一个bfs然后使用结构体作为队列的结点。
image.png
image.png
算法思想：就是先处理第一个结点，然后递归处理左右子树
#include<iostream>
#include<algorithm>
using namespace std;
void preTopost(int pre[], int post[], int L1, int R1, int L2, int R2)
{
if (L1 > R1) return;
post[R2] = pre[L1];
int len = (R1 - L1) / 2;
preTopost(pre, post, L1 + 1, L1 + len, L2, L2 + len - 1);
preTopost(pre, post, L1 + len + 1, R1, L2 + len, R2 - 1);
}
int main(void)
{
int A[16] = { 1,2,4,8,9,5,10,11,3,6,12,13,7,14,15 };
int B[16];
preTopost(A, B, 0, 14, 0, 14);
for (int i = 0; i < 15; i++) printf("%d ", B[i]);
return 0;
}
参考答案给出的方法一样：
image.png
image.png
算法思想：
使用先序遍历，这样就是从左到右遍历叶子结点，然后使用pre保存前一个叶子
BiTNode * leave(BiTree bt, BiTNode *head)
{
BiTNode *Stack[maxSize];
BiTNode p,*pre = head;
int top = -1;
Stack[++top] = bt;
while (top != -1) {
p = Stack[top--];
if (p->rchild)
Stack[++top] = p->rchild;
if (p->lchild)
Stack[++top] = p->lchild;
if (p->rchild == NULL && p->lchild == NULL) {
pre->rchild = p;
pre = p;
}
}
return head;
}
参考方法：给出的方法挺好的。
通常我们使用的先序遍历，中序遍历，后序遍历对于叶子结点的访问都是从左到右顺序，这里使用中序遍历。
算法思想：设置前驱指针pre, 初始为空，第一个叶子结点用指针head指向，遍历到了叶子结点的时候，
就把她的前驱结点的rchild指向她，最后一个叶子结点对的rchild为空。
LinkList head, pre = NULL;
LinkList leaf(BiTree bt)
{
if (bt) {
leaf(bt->lchild);
if (bt->lchild == NULL && bt->rchild == NULL) {
if (pre == NULL) {
head = bt;
pre = bt;
}
else {
pre->rchild = bt;
pre = bt;
}
}
leaf(bt->rchild);
pre->rchild = NULL;
}
return head;
}
image.png
使用递归的思想求解：
参考方法和本方法一致
bool same(BiTree bt1, BiTree bt2)
{
if (bt1 == NULL && bt2 == NULL)
return true;
if (bt1 == NULL)
return false;
if (b2 == NULL)
return false;
return same(bt1->lchild, bt2->lchild) && same(bt1->rchild,bt2->rchild);
}
image.png
image.png
首先要知道什么带权路径长度：
image.png
本人使用后序遍历的方法进行计算wpl:
算法思想：
使用后序遍历非递归算法的时候，当一个结点p出栈的时候，栈中的其他所有结点都是p的祖先结点。
使用top可以知道栈中元素的个数.
int WPL(BiTree root)
{
int sum = 0;
BiTNode *Stack[maxSize];
BiTNode *p = root,r=NULL;
int top = -1;
while (p || top != -1) {
if (p) {
Stack[++top] = p;
p = p->lchild;
}
else {
p = Stack[top--];
if (p->rchild && p->rchild != r) {
p = p->rchild;
Stack[++top] = p;
p = p->lchild;
}
else {
p = Stack[top--];
if (p->rchild == NULL && p->lchild == NULL) {
sum += top*(p->weight);
}
r = p;
p = NULL;
}
}
}
return sum;
}
image.png
参考方法中给出两种方法：一种是层序遍历，就是BFS的思想，使用一个结构
体或者多个数组就可以实现。另外一种方法是使用前序遍历思想.
简单写一下先序遍历的过程：
int WPL(BiTreee root)
{
return wpl_PreOrder(root,0);
}
int wpl_PreOrder(BiTree root,int deep)
{
static int wpl = 0;
if (root->lchild == NULL && root->rchild == NULL)
wpl += deep * root->weight;
if (root->lchild)
wpl_PreOrder(root->lchild,deep+1);
if (root->rchild)
wpl_PrOrder(root->rchild,deep+1);
return wpl;
}
