pre_in~1.cpp

经典c++程序的实现

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>

#include "..\include\book.h"


typedef int BELEM;
#include "..\include\bintree.h"

enum status {L, R};

typedef BinNode* ELEM;

#include "..\include\link.h"
#include "..\include\lstack.h"

void insert(BinNode* &root, BELEM x) {
  BinNode *p, *q;
  bool flag;

  q = new BinNode;            // 申请新结点 
  q->element = x;      q->left = NULL;    q->right = NULL;
  flag = FALSE;
  if (root == NULL)            // 直接把q当作根结点 
       root = q;
  else {
       p = root;
       do {
	if (q->element == p->element) 
	    flag = TRUE;
	if (q->element < p->element)
	    if (p->left == NULL)  {  // q可以作为p的左子结点
		p->left = q;
		flag = TRUE;
	    }
	    else p = p->left;          // 下降到p的左子树 
	else if (p->right == NULL)  {   
	    p->right = q;	// q可以作为p的右子结点
	    flag = TRUE;
	}
	else p = p->right;   // 下降到p的右子树 
       } while (!flag);
  }
}


void in_traverse(BinNode *rt) {      // Inorder traversal
  if (rt == NULL) return;            // Nothing to visit
  in_traverse(rt->left);
  cout << rt->element << " ";
  in_traverse(rt->right);
}

// 中序周游，不压入任何NIL指针 
void infix_stack1(BinNode *p) {
    Stack st;

    do {
       while (p != NULL) {          // 沿左路结点下降，并压栈               
	// 前序周游则在此写访问语句 
	// cout << p->element << " ";   
          st.push(p);
          p = p->left;
       }
       while (p == NULL && !st.isEmpty()) {                
          p = st.pop();       // 弹出栈顶的根结点 
          cout << p->element << " ";
          p = p->right;           // 下降到右子树                              
       }
    } while (p != NULL);
}

// 中序周游，压入空指针NIL 
void infix_stack2(BinNode *p) {
    Stack st;

    st.push(p);
    do {          
        while (st.top() != NULL)      // 沿左路下降，压栈 
	  st.push(st.top()->left);
        st.pop();                         // 扔掉NIL指针 
        if (!st.isEmpty()) {
            p = st.pop();
            cout << p->element;
            st.push(p->right);     // 下降进入右子树  
        }
    } while (!st.isEmpty());      
}

void prefix_stack(BinNode *p)  {
    Stack st;	

    st.push(NULL);                 // 栈底压入NIL 
    while (p != NULL)  {             
        cout << p->element << " ";    
        if (p->right != NULL)
            st.push(p->right);                       		
        if (p->left != NULL) 
            p = p->left;
        else p = st.pop();
    }
}                 

void main() {
	BinNode *root;
	BELEM key;

	root = NULL;
	cout << "input integers as the binary search key value" <<endl;
	cout << "-1 as EOF" << endl;	
	cin >> key;
	while (key != -1) {
		insert(root, key); 
		cin >> key;
	}
//	cout << "*** postorder stack ***" << endl;
//	postfix_stack(root);  cout << endl;
	cout << "*** inorder recursive ***" << endl;
	in_traverse(root);    cout << endl;
	cout << "*** inorder stack ***" << endl;
	infix_stack1(root);    cout << endl;
	cout << "*** inorder stack ***" << endl;
	infix_stack2(root);    cout << endl;
	cout << "*** preorder stack ***" << endl;
	prefix_stack(root);
}