- #include <iostream>
- #include <stack>
- #include <queue>
- using namespace std;
- typedef struct Node{
- int data;
- Node *left;
- Node *right;
- int tag;
- Node(int val):data(val),left(NULL),right(NULL),tag(0){}
- }Node;
- //插入二叉树节点--递归实现
- Node *InsertTree(Node *root,int val)
- {
- Node *e = NULL;
- if(root == NULL){
- e = new Node(val);
- if(e == NULL) return NULL;
- return e;
- }else{
- if(val < root->data){
- root->left = InsertTree(root->left,val);//创建左子树
- }
- else if(val > root->data){
- root->right = InsertTree(root->right,val);//创建右子树
- }
- }
- return root; //递归函数返回时返回的根节点
- }
- //在二叉树中插入节点--非递归实现
- void InsertTree_(Node **root,int val)
- {
- if(root == NULL) return;
- Node *e = new Node(val);
- if(e == NULL) return;
- if(*root == NULL){
- *root = e;
- }else{
- Node *p = *root,*pre = NULL;
- while(p != NULL){
- pre = p;
- if(e->data < p->data){
- p = p->left;
- }
- else if(e->data > p->data){
- p = p->right;
- }else{//有相同的元素就退出
- delete e;
- return;
- }
- }
- if(e->data < pre->data){
- pre->left = e;
- }else{
- pre->right = e;
- }
- }
- }
- //销毁二叉树
- void DeleteTree(Node *root)
- {
- if(root != NULL){
- if(root->left != NULL){
- DeleteTree(root->left);
- }
- if(root->right != NULL){
- DeleteTree(root->right);
- }
- cout<<"delete :"<<root->data<<endl;
- delete root;
- }
- }
- //递归先序遍历二叉树
- void PreOrder(Node *root)
- {
- if(root != NULL){
- cout<< root->data <<" ";
- PreOrder(root->left);
- PreOrder(root->right);
- }
- }
- //递归中序遍历二叉树
- void MidOrder(Node *root)
- {
- if(root != NULL){
- MidOrder(root->left);
- cout<<root->data<<" ";
- MidOrder(root->right);
- }
- }
- //递归后续遍历二叉树
- void LastOrder(Node *root)
- {
- if(root != NULL){
- LastOrder(root->left);
- LastOrder(root->right);
- cout<<root->data<<" ";
- }
- }
- //非递归先序遍历
- void PreOrder_(Node *root)
- {
- if(root == NULL) return;
- Node *p = root;
- stack<Node *> s;
- while(!s.empty() || p != NULL)
- {
- while( p != NULL){
- cout<<p->data <<" ";
- s.push(p);
- p = p->left;
- }
- if(!s.empty()){
- p = s.top();
- s.pop();
- p = p->right;
- }
- }
- cout<<endl;
- }
- //非递归中序遍历
- void MidOrder_(Node *root)
- {
- if(root == NULL) return;
- stack<Node *> s;
- Node *p = root;
- while(!s.empty()|| p != NULL)
- {
- //将左子树压入栈中
- while(p != NULL){
- s.push(p);
- p = p->left;
- }
- //当栈不为空时弹出左子树,输出左子树的值再遍历右子树
- if(!s.empty())
- {
- p = s.top();
- cout<<p->data<<" ";
- s.pop();
- p = p->right; //将右子树压入栈中
- }
- }
- cout<<endl;
- }
- //非递归后续遍历
- //需要判断根结点的左右子树是否都遍历过了
- void LastOrder_(Node *root)
- {
- if(root == NULL) return;
- stack<Node *> s;
- Node *p = root;
- while(!s.empty() || p != NULL)
- {
- while(p != NULL){
- s.push(p);
- p = p->left;
- }
- if(!s.empty())
- {
- p = s.top();//弹出左子树
- //如果左子树已经遍历
- if(p->tag == 1)
- {
- cout<<p->data<<" ";
- s.pop();
- p = NULL; //为了弹出p的父结点
- }else{
- p->tag = 1;
- p = p->right;
- }
- }
- }
- cout<<endl;
- }
- //广度优先遍历二叉树
- void LevelOrder(Node *root)
- {
- if(root == NULL)return;
- queue<Node *> queue;
- Node *p = NULL;
- //根结点入队
- queue.push(root);
- while(!queue.empty())
- {
- p = queue.front(); //取出队首元素
- cout<<p->data<<" ";
- queue.pop();
- if(p->left != NULL)
- queue.push(p->left);
- if(p->right != NULL)
- queue.push(p->right);
- }
- cout<<endl;
- }
- //判断是否为二叉排序树,通过中序遍历,中序遍历的输出结果是从小到大排列的,
- //从跟节点开始记录每次弹出的数,如果比后一个弹出的数大,说明不是二叉排序树
- //是返回1,不是返回 0,错误 返回 -1
- int IsSortedTree(Node *root)
- {
- if(root == NULL) return -1;
- Node *p = root;
- stack<Node *> s;
- int pre_data = 0;
- while(!s.empty() || p != NULL)
- {
- while(p != NULL){
- s.push(p);
- p = p->left;
- }
- if(!s.empty())
- {
- p = s.top();
- if(pre_data == 0 || pre_data < p->data)
- {
- pre_data = p->data;
- }
- if(pre_data > p->data){
- return 0;
- }
- s.pop();
- p = p->right;
- }
- }
- return 1;
- }
- int main()
- {
- /*
- Node *root = NULL;
- int arr[] = {8,2,5,1,7,9,3,6,0,4};
- int len = sizeof(arr)/sizeof(int);
- for(int i = 0; i < len;i++){
- //root = InsertTree(root,arr[i]);
- InsertTree_(&root,arr[i]);
- }
- */
- Node *root = NULL;
- Node* a = new Node(1);
- Node* b = new Node(2);
- Node* c = new Node(3);
- root = a;
- a->left = b;
- a->right = c;
- cout<<"pre order :";
- PreOrder(root);
- cout<<endl;
- cout<<"\\t ";
- PreOrder_(root);
- cout<<"mid order :";
- MidOrder(root);
- cout<<endl;
- cout<<"\\t ";
- MidOrder_(root);
- cout<<"last order :";
- LastOrder(root);
- cout<<endl;
- cout<<"\\t ";
- LastOrder_(root);
- cout<<"Level Order:";
- LevelOrder(root);
- int ret = IsSortedTree(root);
- if(ret == 1){
- cout<<"Is BST"<<endl;
- }else{
- cout<<"Is NOT BST"<<endl;
- }
- DeleteTree(root);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/280820135375.html
来源: http://www.codesnippet.cn/detail/280820135375.html