编辑代码

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
#define TElemType char 
string CH = "ABC##DE#G##F###";
int w[7]={1,2,3,4,5,6,7},w1=0;
int CBT = 0;
int path[10];
typedef struct BiTNode{
	TElemType data;
    int weight;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree; 


bool InitBiTree(BiTree &T){
	T = new BiTNode;
	T->lchild = T->rchild = NULL;
	return true;
}//构造空二叉树

void CreateBiTree(BiTree &T){
//	char ch;
	char ch = CH[CBT++];
	if(ch=='#') T = NULL; 
	else{
		T = new BiTNode;
		T->data = ch;
        //T->weight =w[w1++]; 
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	} 
}//先序创建二叉树,太妙了

void PostOrderTraverse2(BiTree T){
    stack< BiTree > s;
	BiTNode *p = T;
	BiTNode *r = NULL;
	while(p||!s.empty()){
		if(p){
			s.push(p);
			p = p->lchild;
		}else{
			p = s.top();
			if(p->rchild&&p->rchild!=r)//p有右孩子，并且右孩子没被访问过 
				p = p->rchild;
			else{//p没有右孩子，或者右孩子已经被访问了 
				s.pop();//弹出p 
				cout<<p->data;
				r = p;//紧跟上一个被访问的节点 
				p = NULL;//返回父节点
                //为什么这里p右孩子被访问过就敢直接直接访问p呢？
                //在后续遍历中，如果一个节点有右孩子，那么他的后续遍历的前驱一定是他的右孩子
			}
		}
	}
}//太牛逼了

//3 此题就可以看出，只修改二叉树的指针的指向，是不需要加引用的，
//我理解的是指针本身就是地址，而修改元素值如果没有地址的话是修改不了的
//但二逼答案给的是加引用，还是按照答案来吧；
void change(BiTree &T){
    if(T){
        change(T->lchild);
        change(T->rchild);
        if(T->rchild!=NULL&&T->lchild!=NULL){
            BiTNode *c;
            c = T->lchild;
            T->lchild = T->rchild;
            T->rchild = c;
        }
    }
}
//1
int leaf(BiTree T){
    if(!T)  return 0;
    int l,r;
    l = leaf(T->lchild);
    r = leaf(T->rchild);
    if(l>0||r>0)
        return l+r;
    else 
        return 1;
}
//2
bool isTree(BiTree T1,BiTree T2){
    if(T1==NULL&&T2==NULL)
        return true;
    else if(T1==NULL||T2==NULL)
        return false;
    else if(T1->data != T2->data)
        return false;
    return (isTree(T1->lchild,T2->lchild)&&isTree(T1->rchild,T2->rchild));
}
//4
void du(BiTree T){
    if(T){
        cout<<T->data<<endl;
        du(T->lchild);
        cout<<T->data<<endl;
        du(T->rchild);
    }
}
//5 
int with(BiTree T){
    if(T==NULL) return 0;
    BiTNode* p;
    queue <BiTree> q1,q2;
    int count1,count2,sum = 0;
    q1.push(T);
    while((!q1.empty())||(!q2.empty())){
        count1 = 0;
        while(!q1.empty()){
            p = q1.front();
            if(p->lchild!=NULL)
                q2.push(p->lchild);
            if(p->rchild!=NULL)
                q2.push(p->rchild);
            q1.pop();
            count1++;
        }
        if(sum<count1)
            sum =count1;
        count2 = 0;
        while(!q2.empty()){
            p = q2.front();
            if(p->lchild!=NULL)
                q1.push(p->lchild);
            if(p->rchild!=NULL)
                q1.push(p->rchild);
            q2.pop();
            count2++;
        }
        if(sum<count2)
            sum = count2;
    }
    return sum;
}
//5 课本答案 更好
int with2(BiTree T){
    if(T==NULL) return 0;
    queue <BiTree> q;
    BiTNode* p;
    int front = 1;
    int rear = 1;
    int last = 1;
    int temp = 0,maxw = 0;
    q.push(T);
    while(front<=last){
        p = q.front();
        front++;
        q.pop();
        temp++;
        if(p->lchild){
            q.push(p->lchild);
            rear++;
        }
        if(p->rchild){
            q.push(p->rchild);
            rear++;
        }
        if(front>last){
            last = rear;
            if(temp>maxw)   maxw = temp;
            temp = 0;
        }
    }
    return maxw;
}
//6 没毛病
int du1(BiTree T){
    if(T==NULL) return 0;
    BiTNode *p;
    queue <BiTree> q;
    q.push(T);
    int count = 0;
    while(!q.empty()){
        p = q.front();
        q.pop();
        if(p->lchild){
            q.push(p->lchild);
            if(p->rchild==NULL){
                count++;
                continue;
            }
        }
        if(p->rchild){
            q.push(p->rchild);
            if(p->lchild==NULL)
                count++;
        }
    }
    return count;
}
//7
void longPath(BiTree T){
    BiTree p=T,l[10],s[10];
    int top = 0;
    int longest = 0;
    int tag[10];
    while(p||top>0){
        while(p){
            s[++top] = p;
            tag[top] = 0;
            p = p->lchild;
        }
        if(tag[top]==1)
        {
            if(!s[top]->lchild && !s[top]->rchild)
                if(top>longest){
                    for(int i=1;i<=top;i++) l[i] = s[i];
                    longest = top;
                }
            top--;
        }
        else if(top>0){
            tag[top] = 1;
            p = s[top]->rchild;
        }
    }
    for(int i=1;i<=longest;i++)
        cout<<l[i]->data;
}
void longPath2(BiTree T){
    BiTree p = T,s[10],l[10];
    int top = 0,longest = 0;
    int tag[10];
    while(p||top>0){
        while(p){
            s[++top] = p;
            tag[top] = 0;
            p = p->lchild;
        }
        if(tag[top]==1){
            if(!s[top]->lchild && !s[top]->rchild){
                if(top>longest){
                    for(int i=1;i<=top;i++) l[i] = s[i];
                    longest = top;
                } 
            }
            top--;
        }
        else if(top>0){
            tag[top] = 1;
            p = s[top]->rchild;
        }
    }
    for(int i=1;i<=longest;i++)
        cout<<l[i]->data;
}
//8
void pathc(BiTree T,char *path,int len){
    if(T){
        if(!T->lchild && !T->rchild){
            cout<<"叶子结点"<<T->data<<"到根的路径为  ";
            for(int i=len-1;i>=0;i--)
                cout<<path[i];
            cout<<endl;
        }
        else
        {
            path[len] = T->data;
            //len++;
            pathc(T->lchild,path,len+1);
            pathc(T->rchild,path,len+1);
            //len--;
        }
    }
}
int WPL(BiTree T,int len){
    if(T){
        if(!T->lchild && !T->rchild)
            return len*T->weight;
        else
            return WPL(T->lchild,len+1)+WPL(T->rchild,len+1);
    }
    else 
        return 0;
}
int main(){
	BiTree T,T2;
    char path[10];
    CreateBiTree(T2);
    CBT = 0;
	CreateBiTree(T);
    //cout<<WPL(T,0);
    //pathc(T,path,0);
    //longPath2(T);
    //du(T);
    //cout<<du1(T);
    //change(T);
    //PostOrderTraverse2(T);
    cout<<isTree(T,T2);
	//PostOrderTraverse2(T);

}