bintra~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 char BELEM;
#include "..\include\bintree.h"

enum status {L, R};

typedef struct {
	BinNode* point;
	status tag;
} 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);
}

void postfix_stack(BinNode *rt) {
       
	Stack st;
    BinNode *p;
    ELEM  elem;
				  
    if (rt == NULL) return;
    p = rt;
    while (1) {
       while (p != NULL) {       // 沿左路分支下降 
	// cout << p->element << ' ';  // 前序周游在此加访问语句
	elem.point = p;
          elem.tag = L;
          st.push(elem);
          p = p->left;
       }                
       elem = st.pop();
       p = elem.point;
       // cout << p->element << ' ';  // 中序周游在此加访问语句
       while (elem.tag == R) {    // 从右路返回 
	cout << p->element << ' ';		// 后序访问 
	if (st.isEmpty())
	    return;
          elem = st.pop();
          p = elem.point;
       }
       // 左路返回进入右路 
       elem.tag = R;
       st.push(elem);     p = p->right;
    }             
}


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

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

void prefix_stack(BinNode *p)  {
    Stack st;	
    ELEM  elem;                       

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

void main() {
	BinNode *root;

	BELEM key;

	root = NULL;
	cout << "characters as the binary search key value" <<endl;
	cout << "X as EOF" << endl;	

	cin >> key;
	while (key != 'X') {		
		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_stack(root);    cout << endl;
	cout << "*** preorder stack ***" << endl;
	prefix_stack(root);
}