二叉树的操作集：（二叉树的定义，遍历）

二叉树的操作集：（二叉树的定义，遍历）"/>

二叉树的操作集：（二叉树的定义，遍历）

/**
    二叉树的操作集：
    bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
    void Traversal(BinTree BT);//遍历BT树；
    BinTree NewNode(int data) //新建一个结点
    void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的
                                              //数据域修改为给定数据域。
    void Insert(BinTree *&root,int x); //在二叉树中插入一个数据域为x的新节点；
    BinTree CreateBinTree();//创建一棵二叉树；
*/

    1)递归遍历

/**二叉树的操作集：bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；void Traversal(BinTree BT);//遍历BT树；BinTree NewNode(int data) //新建一个结点void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的//数据域修改为给定数据域。void Insert(BinTree *&root,int x); //在二叉树中插入一个数据域为x的新节点；BinTree CreateBinTree();//创建一棵二叉树；1)递归遍历
*/#include <iostream>
#include <queue>
using namespace std;typedef int ElementType;
typedef struct TNode* BinTree;
struct TNode
{ElementType data;BinTree left;BinTree right;
};
typedef BinTree Position;bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
void PreTraver(BinTree BT);//前序遍历
void MidTraver(BinTree BT); //中序遍历
void BehTraver(BinTree BT); //后序遍历
void LayTraver(BinTree BT); //层次遍历     layer:层次，阶层void PrePrintLeaves(BinTree BT);//打印叶子结点
int GetHeight(BinTree BT); //获得树的高度BinTree NewNode(int data); //新建一个结点
void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的//数据域修改为给定数据域。
void Insert(BinTree &root,int x); //在二叉树中插入一个数据域为x的新节点；
BinTree CreateBinTree(int data);//创建一棵二叉树；int main()
{cout << "Hello world!" << endl;return 0;
}bool IsEmpty(BinTree BT)//BT为空，则返回true，否则返回false；
{return (BT==NULL);
}void PreTraver(BinTree BT)  //前序遍历
{if(BT){printf("%d ",BT->data);PreTraver(BT->left);PreTraver(BT->right);}
}void MidTraver(BinTree BT)  //中序遍历
{if(BT){MidTraver(BT->left);printf("%d ",BT->data);MidTraver(BT->right);}
}void BehTraver(BinTree BT)  //后序遍历
{if(BT){BehTraver(BT->left);BehTraver(BT->right);printf("%d ",BT->data);}
}void LayTraver(BinTree BT) //层次遍历
{if(!BT)return;queue<BinTree> q;q.push(BT);BinTree top;while(!q.empty()){top=q.front();q.pop();printf("%d ",top->data);if(top->left)q.push(top->left);if(top->right)q.push(top->right);}
}void PrePrintLeaves(BinTree BT) //打印叶子结点
{if(BT){if(!BT->left&&!BT->right)printf("%d ",BT->data);PrePrintLeaves(BT->left);PrePrintLeaves(BT->right);}}int GetHeight(BinTree BT) //获得树的高度
{if(BT)return max(GetHeight(BT->left),GetHeight(BT->right))+1;elsereturn 0;   //空树高度为0；
}BinTree NewNode(int data) //新建一个结点
{BinTree BT = (BinTree) malloc(sizeof(TNode));BT->data=data;BT->left=BT->right=NULL;return BT;
}void Search(BinTree BT,int x,int newdata)//在二叉树中将所有数据域为给定数据域的结点，并把他们的//数据域修改为给定数据域。
{if(BT) //递归边界{if(BT->data==x)BT->data=newdata;Search(BT->left,x,newdata);Search(BT->right,x,newdata);}
}void Insert(BinTree &root,int x) //在二叉树中插入一个数据域为x的新节点；且root需定义为引用
{if(root == NULL)root=NewNode(x);if(check(root->left,x)) // 如果x满足二叉树左孩子分支的特性Insert(root->left,x);elseInsert(root->right,x);
}BinTree CreateBinTree(int data) //创建一棵二叉树；
{BinTree BT=NULL;Insert(BT,data);return BT;
}

2)非递归遍历

///后序遍历：由于是最后访问根节点，所以根节点需要两次入队，因为先访问左节点，
///然后访问右节点，而访问右节点需要由根节点进入右节点，所以还是需要两次根节点，
///或许你会认为右根节点只需要入栈一次，当访问右节点的时候，不需要出栈，只需要取栈顶元素，
///但是你怎么知道什么时候开始已经访问了该节点的右节点，此时返回的根节点是由左孩子进入的还是由右孩子
///进入的我们是不知道的，所以还是需要根节点两次入栈。解释得有点小绕！
void BehTraver(BinTree BT)  //后序遍历
{
    BinTree top=BT,sec;
    stack<BinTree> st;
    while(top||!st.empty())
    {
        while(top)
        {
            st.push(top);
            st.push(top);
            top=top->left;
        }
        top=st.top();
        st.pop();
        if(!st.empty())
            sec=st.top();
        else
        {
            printf("%d ",top->data);
            break; //树根节点遍历后，可直接跳出循环，即结束程序
        }
        if(top==sec)
            top=top->right;
        else
        {
            printf("%d ",top->data);
            top=NULL;
        }
    }
}

/**二叉树的操作集：bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；void Traversal(BinTree BT);//遍历BT树；BinTree NewNode(int data) //新建一个结点void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的//数据域修改为给定数据域。void Insert(BinTree *&root,int x); //在二叉树中插入一个数据域为x的新节点；BinTree CreateBinTree();//创建一棵二叉树；2)非递归遍历
*//**
#include <iostream>
#include <stack>
#include <queue>
using namespace std;typedef int ElementType;
typedef struct TNode* BinTree;
struct TNode
{ElementType data;BinTree left;BinTree right;
};
typedef BinTree Position;bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
void PreTraver(BinTree BT);//前序遍历
void MidTraver(BinTree BT); //中序遍历
void BehTraver(BinTree BT); //后序遍历
void LevTraver(BinTree BT); //层次遍历BinTree CreateBinTree();//创建一棵二叉树；
void PrePrintLeaves(BinTree BT);//打印叶子结点BinTree NewNode(int data); //新建一个结点
void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的//数据域修改为给定数据域。
void Insert(BinTree &root,int x); //在二叉树中插入一个数据域为x的新节点；
BinTree CreateBinTree(int data);//创建一棵二叉树；int main()
{stack<int> st;for(int i=0;i<3;++i)st.push(i);cout << st.top() << endl;int top=st.top();top=5;cout << st.top() << endl;st.top()=6;cout << st.top() << endl;cout << "Hello world!" << endl;return 0;
}bool IsEmpty(BinTree BT)//BT为空，则返回true，否则返回false；
{return (BT==NULL);
}void PreTraver(BinTree BT)  //前序遍历
{BinTree top=BT;stack<BinTree> st;while(top||!st.empty()){while(top){printf("%d ",top->data);st.push(top);top=top->left;}top=st.top();st.pop();top=top->right;}
}void MidTraver(BinTree BT)  //中序遍历
{BinTree top=BT;stack<BinTree> st;while(top||!st.empty()){while(top){st.push(top);top=top->left;}top=st.top();st.pop();printf("%d ",top->data);top=top->right;}
}///后序遍历：由于是最后访问根节点，所以根节点需要两次入队，因为先访问左节点，
///然后访问右节点，而访问右节点需要由根节点进入右节点，所以还是需要两次根节点，
///或许你会认为右根节点只需要入栈一次，当访问右节点的时候，不需要出栈，只需要取栈顶元素，
///但是你怎么知道什么时候开始已经访问了该节点的右节点，此时返回的根节点是由左孩子进入的还是由右孩子
///进入的我们是不知道的，所以还是需要根节点两次入栈。解释得有点小绕！
void BehTraver(BinTree BT)  //后序遍历
{BinTree top=BT,sec;stack<BinTree> st;while(top||!st.empty()){while(top){st.push(top);st.push(top);top=top->left;}top=st.top();st.pop();if(!st.empty())sec=st.top();else{printf("%d ",top->data);break; //树根节点遍历后，可直接跳出循环，即结束程序}if(top==sec)top=top->right;else{printf("%d ",top->data);top=NULL;}}
}void LevTraver(BinTree BT) //层次遍历
{if(!BT)return;queue<BinTree> q;q.push(BT);BinTree top;while(!q.empty()){top=q.front();q.pop();printf("%d ",top->data);if(top->left)q.push(top->left);if(top->right)q.push(top->right);}
}void PrePrintLeaves(BinTree BT) //打印叶子结点
{if(BT){if(!BT->left&&!BT->right)printf("%d ",BT->data);PrePrintLeaves(BT->left);PrePrintLeaves(BT->right);}}int GetHeight(BinTree BT) //获得树的高度
{if(BT)return max(GetHeight(BT->left),GetHeight(BT->right))+1;elsereturn 0;   //空树高度为0；
}BinTree NewNode(int data) //新建一个结点
{BinTree BT = (BinTree) malloc(sizeof(TNode));BT->data=data;BT->left=BT->right=NULL;return BT;
}void Search(BinTree BT,int x,int newdata)//在二叉树中将所有数据域为给定数据域的结点，并把他们的//数据域修改为给定数据域。
{if(BT) //递归边界{if(BT->data==x)BT->data=newdata;Search(BT->left,x,newdata);Search(BT->right,x,newdata);}
}void Insert(BinTree &root,int x) //在二叉树中插入一个数据域为x的新节点；且root需定义为引用
{if(root == NULL)root=NewNode(x);if(check(root->left,x)) // 如果x满足二叉树左孩子分支的特性Insert(root->left,x);elseInsert(root->right,x);
}BinTree CreateBinTree(int data) //创建一棵二叉树；
{BinTree BT=NULL;Insert(BT,data);return BT;
}*/