算法笔记——二叉树
核心:四大非递归&递归遍历算法
非递归不要习惯性地用递归子树思想
非递归一定是一步步的执行逻辑,每一步仅能看到当前。宏观上则需要拿到之前的结点
数据结构定义
typedef char ElemType;
//二叉树定义
typedef struct BitNode
{ElemType data;struct BitNode* lchild, * rchild;
}BitNode,*BitTree;
//线索二叉树定义
typedef struct BithrNode
{ElemType data;struct BithrNode* lchild, * rchild;int ltag = 1;int rtag = 1;
}BithrNode,* BithrTree;
//链式队列
typedef struct node//结点定义
{BitNode *data;struct node* next;
}LinkNode;
typedef struct queue
{LinkNode* head, * hail;
}Queue;
//入队
void InQue(queue& q,BitNode *n)
{node* qnew = (node*)calloc(1,sizeof(node));qnew->data = n;qnew->next = NULL;q.hail->next = qnew;q.hail = qnew;
}
//出队
BitNode* OutQue(queue& q)
{if (q.head!= NULL){BitNode* pnew = q.head->data;q.head = q.head->next;return pnew;}else {return NULL;}
}
//栈
typedef struct Stack
{BitTree data[100];int length=0;
}Stack;
//入栈
void PushStack(Stack& S, BitNode* n)
{S.data[S.length++] = n;//指针数组(数据类型为指针)
}
//出栈
BitNode* PopStack(Stack& S)
{BitNode* n;if (S.length > 0){n = S.data[--S.length];return n;}else{cout << "栈空!!!" << endl;}
}
1、中序遍历非递归
难点
- 左子树重复入栈问题——结点指针每次打印完后重置,需要时出栈获得;或者控制出栈顺序,左子树访问完就能出栈
- 右子树访问完根节点丢失问题——访问右子树前打印当前出栈元素结点
主要思想
- 左子树一路入栈到叶子结点,开始出栈访问根节点
- 用上述方法遍历右子树
void InOrder_3(BitTree T)
{Stack s;BitNode* p = T;while (s.length > 0 || p){while (p){PushStack(s, p);p = p->lchild;}p = PopStack(s);if (p->rchild){cout << p->data << endl;p = p->rchild;}else{cout << p->data << endl;p = NULL;}}}
优化
- 合并相同逻辑
- 可以出栈后无条件访问右子树,因为左子树的访问条件(当前结点不为空)已经对右子树是否存在判断了
- 每次左子树入完后可以直接出栈访问右子树,右子树没有就直接出栈访问上一层根节点
void InOrder_3(BitTree T)//优化版
{Stack s;BitNode* p = T;while (s.length > 0 || p){if(p){PushStack(s, p);p = p->lchild;}else{p = PopStack(s);cout << p->data;p = p->rchild;}}}
2、先序遍历非递归
主要思想
- 根节点打印并入栈,向左子树遍历
- 出栈,访问出栈元素右节点
void PreOrder2(BitTree T)
{Stack s;BitNode* p = T;while(s.length>0||p){if (p){cout << p->data;PushStack(s, p);p = p->lchild;}else{p = PopStack(s);p = p->rchild;}}
}
3、后序遍历非递归
难点
- 如何解决父节点与左子树循环访问问题——先指针重置,每次右子树访问时拿到栈顶元素
- 如何知道右子树是否被访问过——辅助指针记录最近访问过的结点(判断当前结点右节点是否被访问过)
易错
- 记录已经访问过的右子树时刻是在每个元素出栈时,这样使得当前proximate右孩子结点被记录
主要思想
-
访问左子树,直至叶节点,过程中依次入栈
-
否则,考虑右子树和根节点访问问题
-
先拿到访问结点(栈顶元素)——由于后面的指针重置
-
若右子树存在且未被访问过
- 访问右子树,进行后续遍历。
-
若右子树不存在或者访问过
-
打印当前出栈元素
-
记录当前出栈元素(作为判别右子树是否访问到的依据)
-
访问结点重置(防止重复遍历左子树)
-
-
循环上述直至当前结点为NULL或栈空
void PostOrder_2(BitTree T)
{Stack s;BitNode* p = T, * r = NULL;//辅助指针while (p || s.length > 0){if (p){PushStack(s, p);p = p->lchild;}else {p = s.data[s.length-1];//指针回归到当前栈顶元素if (p->rchild && r != p->rchild)//右子树是否已经被访问或不存在p = p->rchild;else{r=PopStack(s);//记录当前出栈cout << r->data;p = NULL;//指针重置,防止重复进入左子树}}}
}
4、二叉树自右向左、自底向上遍历
难点
- 怎么搜索到最底层——使用逆序层次遍历方式,这样尾元素即为最底层最右
易错
- 链式队列,入队思想是先创建结点,在把结点加入尾结点的next,此时head不参与;因此在初始化时需要将head和hail同时指向首个入队结点
主要思想
- 层次入队(队列法)
- 逆序打印入队元素(栈)
void Reverse(BitTree T)
{Queue q;q.hail = (node*)calloc(1, sizeof(node));q.head = q.hail;q.hail->data = T;node* n = q.head;BitNode* t = T;while (1)//层次入队{if (t->lchild)InQue(q, t->lchild);if(t->rchild)InQue(q, t->rchild);n= n->next;if (n != NULL)t = n->data;else//遇到没有结点可以导向时break;}Stack s;while (q.head)//入栈后出栈即逆序打印{PushStack(s, OutQue(q));}while (s.length > 0){cout << PopStack(s)->data << endl;}
}
优化
入栈操作可以和层次入队合并,边入队列,边出队列,边进栈
5、二叉树非递归求高度
三种方法
-
利用后序遍历非递归
-
利用层次遍历
-
利用递归算法
1.后续遍历非递归
主要思想
利用后续遍历中,访问完左右子树出栈即回到上一层,此时层数减一,而入栈则进入下一层,层数加一。通过计算各结点层数,并保留最大的层数从而计算出高度
void searchHigh(BitNode*T)
{int count = 0;Stack s;BitNode* t = T;BitNode* r = NULL;int max_count = 0;while (t || s.length > 0){if (t){PushStack(s, t);t = t->lchild;count++;}else{t = s.data[s.length - 1];if (t->rchild && r != t->rchild){t = t->rchild;//此处仍是在当前根节点下,因此不用count++}else{r=PopStack(s);if (count > max_count)max_count = count;count--;//每次出栈则count值减一t = NULL;}}}cout <<max_count<< endl;
}
2.层次遍历
主要思想
- 记录每层的level,到下一层时level+1
- 判断不同层——通过是否到达当前层的最右结点
- 当前层最右结点——通过访问到上一层的最右结点并对其左、右子树依次入队后得到。
int searchHigh2(BitNode* T)
{int level = 0,r= 0;BitNode* Queue[50];int front=-1,last = -1;BitNode* p = T;Queue[++last] = T;Queue[++last] = p->lchild;Queue[++last] = p->rchild;while (front != last){p = Queue[++front];if (front!=r){if (p->lchild)Queue[++last] = p->lchild;if (p->rchild)Queue[++last] = p->rchild;}else{r = last;level++;}}return level;
}
易错
容易在初始条件上出问题,第一次需要把T的左右子树无条件进
3.递归算法
主要思想
- 递归左子树和右子树的层级
- 递归出口:
- 叶子结点的子树为0
- 非叶子结点max{左子树、右子树}+1
int searchHigh3(BitNode* T)
{int lnode = 0, rnode = 0;//必须设置到当前内部变量if (T){lnode = searchHigh3(T->lchild);rnode = searchHigh3(T->rchild);}elsereturn 0;if (lnode>rnode){return lnode+ 1;}else{return rnode + 1;}
}
易错
关于递归算法初始变量问题(全局or局部)——不能设置为全局变量
会覆盖之前的数值,因此对于不同的函数栈,设置不同的lnode和rnode。变量设置在栈区(写在函数内部),这样就会仅作用在当前栈。
6、先序序列+中序序列建立二叉链表
难点
- 可以通过先序序列,将其中序序列分为左右子树,但是如何将一个子树不断集合化为结点——递归思想
- 怎么让左右子树递归过程中指向不为一个集合而是一个结点——递归出口为结点;并且左右指针域指向递归函数(通过赋值语句调用递归函数)
- 在数组存储结构下,怎么实现子树集合划分的过程——递归函数中传入界限范围
主要思想
- 根据先序序列确定根节点
- 根据根节点在中序序列中划分左右子树,同时在先序序列中划分子树对应的根节点,一直这样划分下去,直至划分集合仅含一个结点。
- 关键在于左右子树划分
BuildTree_FAI(F, I, F1 + 1, F1+left, I1, i-1);
BuildTree_FAI(F, I, F1+left+1, F2, i+1, I2);
BitNode* BuildTree_FAI(char F[], char I[], int F1, int F2, int I1, int I2)
//F1、F2先序序列头,尾部;I1、I2中序序列头尾
{BitNode* root;root = (BitNode*)calloc(1, sizeof(BitNode));root->data = F[F1];//划分int i=I1;for (; F[F1] != I[i]; i++);int left = i-I1;int right = I2-i;if (left>0){root->lchild = BuildTree_FAI(F, I, F1 + 1, F1+left, I1, i-1);}elseroot->lchild=NULL;if (right >0){root->rchild = BuildTree_FAI(F, I, F1+left+1, F2, i+1, I2);}elseroot->rchild=NULL;return root;
}
易错
-
在中序序列中找右子树的根节点时,需要在先序序列中右移:左子树的结点数目;而不是1!!!找左子树的根直接右移一个单位即可
- 注意在先序中,根节点位置——根左(根左右)右(根左右)
-
一定要注意,不仅仅是在中序序列中有界限划分,先序序列也有界限划分
-
字符串数组作为实参传递时,会自动将其变为字符串类型,此时如果分配空间小于n+1(由于多存了个‘\0’)则会报错
-
如这样定义:
-
则会
-
查看
-
-
当不满足进入左子树或者右子树条件时候,不是return NULL这样会将当前结点给设为NULL。直接将当前结点左孩子或者右孩子设为NULL即可
7、判定完全二叉树
难点
- 判断非完全条件
- 有结点右子树无左子树则不为完全二叉树
- 从残缺子树结点开始,存在结点有子树
- 非空树
主要思想
- 层次遍历
- 结点左右子树都存在,左右子树入队
- 结点左子树或者右子树为空
- 若有右子树无左子树则不为完全二叉树
- 否则从当前结点开始,若存在一个结点有子树则不为完全二叉树
- 遍历完毕,为完全二叉树
bool IsComplete(BitTree T)
{if(!T)//空树return true;Queue q;q.hail = (node*)calloc(1,sizeof(node));q.head = q.hail;BitNode* p = T;while (q.head){if (p->lchild && p->rchild)//左右子树都存在{InQue(q, p->lchild);InQue(q, p->rchild);}else{if (p->rchild && !p->lchild){return false;}else{if (p->lchild){InQue(q, p->lchild);q.head = q.head->next;}break;}}q.head = q.head->next;p = q.head->data;}while (q.head)//有残缺子树结点开始{if (q.head->data->lchild || q.head->data->rchild)return false;q.head = q.head->next;}return true;
}
8、计算二叉树双分支结点个数
主要思想
-
层次遍历
-
递归
f(T)=0//T=NULL f(T)=f(T->lchild)+f(T->rchild)+1//T为双节点 f(T)=f(T->lchild)+f(T->rchild)//T不为双节点
void exchange(BitTree& T)
{if (T == NULL)return;BitNode* t;if (T->lchild || T->rchild){t = T->rchild;T->rchild = T->lchild;T->lchild = t;exchange(T->lchild);exchange(T->rchild);}elsereturn;
}
9、先序遍历第k个结点
易错
试图用递归和k的值控制
然而,会出现多次return——由于函数栈需要依次出栈,而不是在你return掉后其他函数都中断出栈。这个结果最后是C
ElemType kPreOrder(BitTree T,int &k)
{k = k - 1;if (T && k > 0){kPreOrder(T->lchild, k);kPreOrder(T->rchild, k);}elsereturn T->data;
}
在尝试通过k>0控制出栈后发现,最后没有return值了…推测结果应该是取决于最后一次函数出栈是否有return
解决
通过全局变量保存结点值,同时将不符合条件的函数栈直接不执行操作
void kPreOrder(BitTree T,int &k,char &a)
{k = k - 1;if (T && k > 0){if(k>0)kPreOrder(T->lchild, k,a);if(k>0)kPreOrder(T->rchild, k,a);}elsea= T->data;
}
10、删除特定值的结点,并释放相应空间
主要思想
- 通过搜索功能和删除功能两个函数组合实现
- 删除功能
- 采用后续递归思想
- 搜索功能
- 无法采用递归,会导致结点异常(指针没有设置为空就被释放掉内容)
- 故使用层次遍历的队列形式
//删除元素为x的结点,释放对应空间
void Delete(BitTree T)
{if (T){Delete(T->lchild);Delete(T->rchild);free(T);}
}
void SearchX(BitTree T, char x)
{Queue q;q.hail = (node*)calloc(1, sizeof(node));q.head = q.hail;q.head->data = T;BitNode* p = T;while (q.head){if (p->lchild){if (p->lchild->data == x){Delete(p->lchild);p->lchild = NULL;}elseInQue(q, p->lchild);}if (p->rchild){if (p->rchild->data == x){Delete(p->rchild);p->rchild = NULL;}elseInQue(q, p->rchild);}q.head = q.head->next;if(q.head)p = q.head->data;}
}
易错
没有考虑到根节点为指定元素问题
if (T->data == x){Delete(T);exit(0);}
11、查找某个结点的所有祖先
主要思想
- 非递归的后序遍历
void SearchPath(BitNode* T,ElemType x)
{Stack s;BitNode* p = T;BitNode* r = NULL;//右结点访问标记while (p || s.length > 0){if (p){PushStack(s, p);p = p->lchild;}else{p=s.data[s.length-1];//拿到栈顶if (p->rchild && p->rchild != r)p = p->rchild;else{if (p->data == x){while (s.length > 0){cout << PopStack(s)->data << endl;}exit(0);}else{r=PopStack(s);p = NULL;//避免左子树循环}}}}cout << "查找元素不存在" << endl;
}
12、找到两个结点的最近公共祖先
主要思想
- 后序遍历非递归
- 辅助栈,栈元素匹配
易错
- 第一次匹配到p后没有继续执行后续,导致循环执行赋值辅助栈语句
- 栈的匹配是从栈顶开始,也就是数组最后一个元素开始,而不是首元素!
//找到两个结点的最近公共祖先
BitNode* SearchParent(BitTree T, BitNode* q1, BitNode* q2)
{Stack s;Stack s1;BitNode* r = NULL, * p = T;while (p || s.length > 0){if (p){PushStack(s, p);p = p->lchild;}else{p = s.data[s.length - 1];if (p->rchild && p->rchild != r)p = p->rchild;else{if (p == q1){for (int i = 0; i < s.length; i++)PushStack(s1, s.data[i]);}if (p == q2){for (int i = s.length-1; i >0 ; i--)for (int j = s1.length-1; j >0; j--)//从后往前比,栈顶开始if (s.data[i] == s1.data[j])return s.data[i];}r=PopStack(s);//这一步一定要无条件执行不能放在elsep = NULL;}}}return NULL;
}
13、求二叉树宽度
主要思想
二叉树层次遍历的分层思想
int Width(BitTree T)
{if (!T){return 0;}int b = 1,count =0;//记录每层结点数Queue q;q.hail = (node*)calloc(1, sizeof(node));q.head = q.hail;q.head->data = T;BitNode* p = T,*r=T;//r指向当前最右结点while ( q.head){if (p->lchild){InQue(q, p->lchild);count++;}if (p->rchild){InQue(q, p->rchild);count++;}if (p == r){r = q.hail->data;if (b < count)b = count;count = 0;}q.head = q.head->next;if(q.head)p = q.head->data;}return b;
}
14、满二叉树已知先序求后序
这个题我的算法比答案更简单!
主要思想
- 采用递归思想,分别对左右子树求后序
- 输出条件
- 当前子树仅有一个结点
- 当前左右子树都打印完,直接输出根节点(子树中,先序序列最左边的元素)
void OutputPostOreder(char* A, int l, int r)
{if (l != r){int mid = (l + r) / 2;OutputPostOreder(A, l + 1, mid);OutputPostOreder(A, mid+1,r);cout << A[l];//左右子树输出完毕}elsecout << A[l];//仅有一个结点
}
15、将二叉树叶节点串联成一个单链表,右指针域放下一个结点
难点
- 如何依次从左至右访问到叶节点
- 中序遍历使得叶节点顺序为从左至右
- 访问叶节点通过条件判断方式
- 叶节点满足左右子树为空
- 指针丢失
- 在递归函数中,由于先执行了下一层在接着返回上层的调用,而此时上层保留当前的值未获得到下层修改后对应值,因此上次head始终为NULL
- 解决:设置全变量,避免传参
- 指针指向导致前部所连接丢失
- 解决:设置一个头指针,同时一个遍历指针
BitNode* Q15_head=NULL;//头指针,保存整条链
BitNode* Q15_p=NULL;//遍历指针
void LinkLeaf(BitNode* T)
{if (T){LinkLeaf(T->lchild);if (T->lchild == NULL && T->rchild == NULL){if (Q15_head == NULL){Q15_head = T;Q15_p = Q15_head;}else{Q15_p->rchild = T;Q15_p = Q15_p->rchild;}}elseLinkLeaf(T->rchild);}return;
}
16、判断二叉树是否相似(相似: T 1 , T 2 T1,T2 T1,T2都为空二叉树且都只有一个根节点,或左子树右子树均相似)
主要思想
- 递归思想
- 比较当前结点是否相似
- 在当前结点相似情况下比较左右子树是否相似
- 分别保存在right 和left中
- 当前结点的相似受左右子树是否都相似影响
int IsSimilarity(BitNode* T1, BitNode* T2)
{int right = 0;int left = 0;if (T1 == NULL && T2 == NULL)return 1;else if (T1==NULL || T2==NULL)return 0;else{left = IsSimilarity(T1->lchild, T2->lchild);right = IsSimilarity(T1->rchild, T1->rchild);return (left && right);}
}
17、中序线索二叉树中查找指定节点在后序序列中的前驱结点
主要思想
- 按情况分析
- 若当前结点有直接右孩子
- 为右孩子
- 若当前结点有直接左孩子
- 为左孩子
- 若当前结点左孩子为空
- 说明是最左结点,无前驱
- 一直搜索到它存在左子树的根节点
- 根节点的左孩子为前驱
- 若当前结点有直接右孩子
BithrTree SearchPostOrder(BithrNode* p)
{if (p->rtag == 0)return p->rchild;else if (p->ltag == 0)return p->lchild;else if (p->lchild == NULL)return NULL;//最左结点无前驱else{while (p->ltag = 1 && p->lchild != NULL)//直到找到有直接左子树的或者已经遍历到最左了p = p->lchild;if (p->ltag == 0)return p->lchild;elsereturn NULL;}
}
易错
- 为什么是一直要找到有直接左子树的呢?
- 后序遍历是左右根,而中序序列是左根右,它的前驱是它的最左结点。只要能找到有一个结点有直接左子树,那么无论该节点是直接祖先还是原始祖先,找到的左孩子是右孩子的前驱
18、【2014真题】求二叉树的带权路径长度
带权路径长度:二叉树中所有叶节权值与路径长度之积的总和
结点结构:left、weight、right
难点
- 递归算法中如何使得二叉树每一层匹配到对应层数
- 只需形式结合即可(注意不能用deep++/deep–这种而是要用deep+1这样的具体数值)
- 每一层的参数为当前层所传入的值,因此能做到回退的效果、
- 递归函数如何保存累加值
- 使用static静态变量或者全局变量
int PreOrderx(BitTree T,int deep)
{static int sum = 0;//静态变量存储if (T){PreOrderx(T->lchild,deep+1);PreOrderx(T->rchild,deep+1);if (T->lchild == NULL && T->rchild == NULL){sum += deep * T->data;}}return sum;
}
int CalculateWPL(BitTree T)
{return PreOrderx(T, 1);
}
19、【2017真题】表达式转中缀表达式输出
难点
-
如果采用递归方式则对于叶节点会出现括号情况如((a)+(b))
void PrintZhongzhui(BitTree T) {if (T){cout << "(";PrintZhongzhui(T->lchild);cout << T->data;PrintZhongzhui(T->rchild);cout << ")";} }
-
非递归算法中加括号的时机
- 且加括号必须在打印当前值之前就加,难以判断时机
非递归要求更高难做!
主要思想
- 解决根节点加括号和叶节点加括号问题
- 加括号问题——由于遍历是自上而下的,故顺序是先加括号后打印值,只需判断是不是叶节点加括号即可
- 根节点括号问题——分别传入左右子树中间打印根节点值即可
void PrintZhongzhui(BitTree T)
{if (T){if (T->lchild || T->rchild)//递归到非叶节点层,先打印左括号cout << "(";PrintZhongzhui(T->lchild);cout << T->data;PrintZhongzhui(T->rchild);if (T->lchild || T->rchild)cout << ")";//递归完成非叶节点层,打印右括号}
}
void PrintZ(BitTree T)//避免根节点算式打印括号
{PrintZhongzhui(T->lchild);cout << T->data;PrintZhongzhui(T->rchild);
}