thread.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\binthread.h"

enum status {L, R};

typedef thrBinNode* ELEM;

thrBinNode *pre;

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

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

  q = new thrBinNode;            // 申请新结点 
  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(thrBinNode *rt) {      // Inorder traversal
  if (rt == NULL) return;            // Nothing to visit
  in_traverse(rt->left);
  cout << rt->element << " ";
  in_traverse(rt->right);
}

/*
    // 中序周游，不压入任何NIL指针 
void infix_stack(thrBinNode *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_stack(thrBinNode *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(thrBinNode *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 in_thread(thrBinNode *p) {      // Inorder traversal
	if (p != NULL) {            // Nothing to visit
		in_thread(p->left);    // 递归线索化坐子树
		if (p->left == NULL) {  // 建立指向前驱的线索
			p->ltag = 1;
			p->left = pre;
		}
		if (pre->right == NULL) {  // 建立指向后继的线索
			pre->rtag = 1;
			pre->right = p;
		}
		pre = p;
		in_thread(p->right);		
    }
}
  
// rt指向二叉树的根结点，中许周游生成穿线二叉树，threadrt为指向头结点的指针
void thread(thrBinNode *rt, thrBinNode* &threadrt) {
    threadrt = new thrBinNode;
	threadrt->ltag = threadrt->rtag = 0;   // 建立头结点
	threadrt->right = threadrt;
	if (rt == NULL) 
		threadrt->left = threadrt;   // 空二叉树则形成空循环链
	else {
		threadrt->left = rt;
		pre = threadrt;
		in_thread(rt);		// 中序线索化，线索化后，pre指向最后一个结点
		pre->right = threadrt;		pre->rtag = 1;  // 线索化最后一个结点
		threadrt->right = pre; 		threadrt->rtag = 1;
	}
}

// threadrt是指向中序双向穿线树中头结点的指针，中序周游该二叉树
void inorder_threaded(thrBinNode *threadrt) {
	thrBinNode *p;
	p = threadrt->left;     // 二叉树为空时，p == threadrt
	while (p != threadrt) {
		while (p->ltag == 0)  p = p->left;   // 下降到最左
		cout << p->element << " ";		// 访问左子树为空的结点
		while (p->rtag == 1 && p->right != threadrt) { 
			p = p->right;	
			cout << p->element << " ";     // 沿线索访问后继结点
		}
		p = p->right;		// 下降到右子树
	}
}

void main() {
	thrBinNode *root, *threadrt;
	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 << "*** inorder recursive ***" << endl;
	in_traverse(root);    cout << endl;

	cout << "*** thread the binary tree ***" << endl;
	thread(root, threadrt);

	cout << "*** inorder threaded binary tree ***" << endl;
	inorder_threaded(threadrt);
}