- #include <iostream>
- #include <stack>
- using namespace std;
- typedef struct Node{
- int data;
- struct Node *left;
- struct Node *right;
- int tag;
- Node(int val){left = right = NULL,data = val;tag = 0;}
- }Node;
- Node *InsertTree(Node *root,int val)
- {
- Node *e = NULL;
- if(root == NULL){
- e = new Node(val);
- return e;
- }else{
- if(root->data > val){
- root->left = InsertTree(root->left,val);
- }else if(root->data < val){
- root->right = InsertTree(root->right,val);
- }
- }
- return root;
- }
- void InsertTree2(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;
- }
- }
- //pre order
- void PreOrder(Node *root)
- {
- if(root != NULL){
- cout<<root->data<<" ";
- PreOrder(root->left);
- PreOrder(root->right);
- }
- }
- //mid order
- void MidOrder(Node *root)
- {
- if(root != NULL){
- MidOrder(root->left);
- cout<<root->data<<" ";
- MidOrder(root->right);
- }
- }
- //last order
- void LastOrder(Node *root)
- {
- if(root != NULL){
- LastOrder(root->left);
- LastOrder(root->right);
- cout<<root->data<<" ";
- }
- }
- //pre
- void PreOrder2(Node *root)
- {
- if(root == NULL) return;
- stack<Node *> s;
- Node *p = root;
- 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;
- }
- //mid
- void MidOrder2(Node *root)
- {
- if(root == NULL) return;
- Node *p = root;
- stack<Node *> s;
- 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;
- }
- //last
- void LastOrder2(Node *root)
- {
- if(root == NULL)return;
- Node *p = root;
- stack<Node *> s;
- 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;
- }else{
- p->tag = 1;
- p = p->right;
- }
- }
- }
- cout<<endl;
- }
- int main()
- {
- Node *root = NULL;
- int arr[] = {7,3,5,8,9,1,2,4,6};
- int len = sizeof(arr)/sizeof(int);
- for(int i = 0;i <len;i++)
- {
- //root = InsertTree(root,arr[i]);
- InsertTree2(&root,arr[i]);
- }
- cout<<"pre order:";
- PreOrder(root);
- cout<<endl;
- PreOrder2(root);
- cout<<"mid order:";
- MidOrder(root);
- cout<<endl;
- MidOrder2(root);
- cout<<"last order:";
- LastOrder(root);
- cout<<endl;
- LastOrder2(root);
- DeleteTree(root);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/270820135360.html
来源: http://www.codesnippet.cn/detail/270820135360.html