提示：夫君子之行，静以修身，俭以养德
本文中主要写关于王道习题中5.3部分的习题解析
想必若是之前看过写的其他的文章，或者我之前写的一个非递归的形式，需要借助栈这种结构，并且因为处理方式是左右根 ，自然进入栈的顺序就是根右左 但是要想让左右进栈，还必须需要通过根结点 ，所以也就需要两次处理根结点，这个时候就需要一个标记，这里将标记设置为NULL
void PastTravel(BiTree* T){
stack<BiTree*> S;
if(T==NULL) return;
S.push(T);
cout<<"此时树的后序非递归遍历"<<endl;
while(!S.empty()){
BiTree* cur=S.top();//可能为空 也可能不为空
if(cur==NULL){
S.pop();
cur=S.top();
cout<<cur->data<<" ";
S.pop();
}
else{
S.push(NULL);
if(cur->Rchild)S.push(cur->Rchild);
if(cur->Lchild)S.push(cur->Lchild);
}
}
}
二叉树自下而上，自右而左
一个比较拉跨的方式就是 普通形式的递归 然后再将获得的结果集反转即可
还有一个方法就是与栈结合起来在出队的同时将结点放入栈中中
void ReLevelTravel(BiTree* T){
if(T==NULL) return;
stack<BiTree*> S;
queue<BiTree*> Q;
Q.push(T);
cout<<"正常层序遍历"<<endl;
while(!Q.empty()){
int size=Q.size();
for(int i=0;i<size;i++){
BiTree* cur=Q.front();
Q.pop();
cout<<cur->data<<" ";
S.push(cur);
if(cur->Lchild)Q.push(cur->Lchild);
if(cur->Rchild)Q.push(cur->Rchild);
}
}
cout<<endl<<"此时反转遍历是"<<endl;
while(!S.empty()){
BiTree* cur=S.top();
cout<<cur->data<<" ";
S.pop();
}
}
这里当然也是使用层序遍历 并且因为我们之前有一个size的原因使得我们本来就是分层的 只需要在一次for之后加上高度加一便可
int TreeHight(BiTree* T){
if(T==NULL) return 0;
int hight=0;
queue<BiTree*> Q;
Q.push(T);
while(!Q.empty()){
int size=Q.size();
for(int i=0;i<size;i++){
BiTree* cur=Q.front();
Q.pop();
if(cur->Lchild)Q.push(cur->Lchild);
if(cur->Rchild)Q.push(cur->Rchild);
}
hight++;
}
return hight;
}
之前我们曾做过相关解析 先序的处理方式是根左右 中序的方式是左根右 方法就是通过先序来确定根，然后通过这个根 将中序序列分出左右子树 在根据左右子树去前序中寻找左右子树的根 而且需要注意使用区间的方式，这里使用的是左闭右开的形式
oid PreOrdTree(BiTree* &T,int V1from,int V1to,int V2from,int V2to){
//这里将前序 以及中序所给序列设置为全局变量
cout<<"v1"<<"从"<<V1from<<"到"<<V1to<<endl;
cout<<"v2"<<"从"<<V2from<<"到"<<V2to<<endl;
if(V1to==V1from){
T=NULL;
return;
}
T=(BiTree*)malloc(sizeof(BiTree));
//先找先序第一个字母 就是此时树的根
int cur=V1[V1from];
T->data=cur;
//找cur在中序序列中的位置
int i=0;
while(cur!=V2[i]){
i+=1;
}
//以此i为分界线将中序分为左，中，右 根据中序左右子树的结点数量
PreOrdTree(T->Lchild,V1from+1,V1from+1+(i-V2from),V2from,i);//构建此时的左子树
PreOrdTree(T->Rchild,V1from+1+(i-V2from),V1to,i+1,V2to);//构建此时的右子树
}
使用层序遍历，有孩子的要有左右孩子 ，没有孩子的其后面所有的结点都不能有孩子，这里通过层序遍历将说有的结点分为前部分有孩子的 以及剩余部分 ，对前一部分n个结点中的n-1个判断是否是有左右 第n个结点不能是有右孩子而没有左孩子，此时前n个就满足条件了，然后遍历后面所有的 都不能有孩子 flag作为一个前部分有孩子与后部分没孩子的分界标记位
void JudgeBal(BiTree* T){
if(T==NULL) return ;
int flag=1;
queue<BiTree*> Q;
queue<BiTree*> Result1;//用来存放前一部分有孩子的
queue<BiTree*> Result2;//用于存放除前一部分之外所有的
Q.push(T);
while(!Q.empty()){
int size=Q.size();
for(int i=0;i<size;i++){
BiTree* cur=Q.front();
Q.pop();
if((cur->Lchild||cur->Rchild)&&flag==1){
Result1.push(cur);
}else flag=0;
if(flag==0){
Result2.push(cur);
}
if(cur->Lchild)Q.push(cur->Lchild);
if(cur->Rchild)Q.push(cur->Rchild);
}
}
//判断第一个结果集中的前N-1个结点
while(Result1.size()>1){
BiTree* cur=Result1.front();
if(cur->Lchild&&cur->Rchild){
}
else{
cout<<"此时不是一个完全二叉树"<<endl;
return;
}
Result1.pop();
}
//判断其中第n个结点 此时可能是只有一个左孩子
BiTree* cur=Result1.front();
if(cur->Rchild&&!cur->Lchild){
cout<<"不是一个完全二叉树"<<endl;
return ;
}
while(!Result2.empty()){
BiTree* cur=Result2.front();
if(cur->Lchild||cur->Rchild){
cout<<"不是一个完全二叉树"<<endl;
return ;
}
Result2.pop();
}
cout<<"是一个完全二叉树"<<endl;
}
这里使用任何一种遍历方式都可 。中间加一个判断和统计语句即可，这里当然是选择递归的方式了 并且将sum设置为全局变量
void SumNode(BiTree* T){
if(T==NULL){
return ;
}
SumNode(T->Lchild);
SumNode(T->Rchild);
if(T->Lchild&&T->Rchild)sum+=1;
}
这个题前面写过，这里也使用递归来写
交换T的左右子树 但是有一点需要注意就是若是你使用的是中序递归，因为之前你已经交换左子树，所有后面依然是交换和之前一样的左子树这里使用的后序 这就不需要注意这些
void ChargeTree(BiTree* T){
if(T==NULL){
return;
}
ChargeTree(T->Lchild);
ChargeTree(T->Rchild);
BiTree* cur=T->Lchild;
T->Lchild=T->Rchild;
T->Rchild=cur;
}
这里可以将先序结果存放在一个结果集中 然后取出其中第K个便可
还有一个办法就是设置一个全局变量用于统计递归的
void GetKData(BiTree* T,int K){
if(T==NULL){
return;
}
times+=1;
cout<<"time是"<<times<<endl;
if(times==K){
cout<<"你要获取的数值是"<<T->data<<endl;
return;
}
GetKData(T->Lchild,K);
GetKData(T->Rchild,K);
}
#include