#include <iostream>#include <stack>using namespace std;#define MAX 100           //字符串最大长度typedef struct Node       //二叉树结点{    char data;    Node *lchild,*rchild;} *Btree;void createBT(Btree &t);  //先序构造二叉树void preorder(Btree &t);  //二叉树递归先序遍历void inorder(Btree &t);   //递归中序遍历void postorder(Btree &t); //递归后序遍历void preorderbyStack(Btree &t); //先序非递归遍历void inorderbyStack(Btree &t);  //中序非递归遍历void postorderbyStack(Btree &t);//后序非递归遍历/*****************最近公共父结点算法LCF*******************/int findNode1(Btree &t,char ch,char p[]); //找出结点1到根的路径int findNode2(Btree &t,char ch,char q[]); //找出结点2到根的路径void compare(char *p,char *q);            //比较两条路径，找到第一个公共结点static int i = 0;static int j = 0;/*****************最近公共父结点算法LCF*******************/void createBT(Btree &t)   //先序创建二叉树 #表示空指针{    char ch;    cin>>ch;    if(ch == ‘#‘) t = NULL;        else    {        if(!(t = new Node)) exit(1);                t ->data = http://www.mamicode.com/ch;    //递归创建二叉树" ";        preorder(t->lchild);        preorder(t->rchild);    }}void inorder(Btree &t){    if(!t)        return;    else    {        inorder(t->lchild);        cout<<t->data<<" ";        inorder(t->rchild);    }}void postorder(Btree &t){    if(!t)        return;    else    {        postorder(t->lchild);        postorder(t->rchild);        cout<<t->data<<" ";    }}void preorderbyStack(Btree &t){    stack<Node*>s;    Node *p = t;    while (p || !s.empty())    {        if(p)        {            cout<<p->data<<" ";    //先序遍历二叉树，先访问根节点，再访问左子树            s.push(p);            p = p->lchild;        }        else        {            p = s.top();            s.pop();            p = p->rchild;        }    }}void inorderbyStack(Btree &t){    stack<Node*>s;        Node *p = t;        while (p || !s.empty())    {        if(p)        {            s.push(p);            p = p->lchild;        }        else        {            p = s.top();            cout<<p->data<<" ";   //中序遍历二叉树，先访问左子树            s.pop();            p = p->rchild;        }    }}void postorderbyStack(Btree &t){    stack<Node*> s;        Node *p = t;    Node *flag = nullptr;        while (p || !s.empty())    {        if(p)                      //后序遍历先访问左结点，再右结点，最后根结点        {            s.push(p);            p = p->lchild;        }        else        {            p = s.top();            if( p->rchild&&p->rchild != flag) //如果右子树不为空且没有被访问过            {                p = p->rchild;                //转到右子树                s.push(p);                p = p->lchild;            }            else                            //如果右子树为空，当前结点为访问结点            {                s.pop();                cout<<p->data<<" ";                                flag = p;                  //把刚刚访问的结点做标记，防止重复访问                p = nullptr;               //把p置为空指针，如果不置位空。还要压入栈一次，就造成死循环            }        }    }}bool isEmpty(Btree &t){    return t == NULL?true:false;}int findNode1(Btree &t,char ch,char p[]){    if(!t)        return 0;    else if(t->data =http://www.mamicode.com/= ch)             //从所给的结点出发，搜索到达根节点的路径，并将路径记录下来"LCF is :"<<p[i+1]<<endl;}int main(){    //测试用例：abc##de#g##f###        Btree t = new Node;    createBT(t);    preorder(t);    cout<<endl;    preorderbyStack(t);    cout<<endl;    inorder(t);    cout<<endl;    inorderbyStack(t);    cout<<endl;    postorder(t);    cout<<endl;    postorderbyStack(t);    cout<<endl;        char a[MAX];    char b[MAX];            findNode1(t, ‘c‘,a);    findNode2(t, ‘e‘,b);        compare(a, b);    return 0;}