数据结构----Threaded Binary Tree 线索二叉树

对于任意一棵节点数为 n 的二叉树，NULL 指针的数目为  n+1 ， 线索树就是利用这些 "浪费" 了的指针的数据结构。

Definition:

"A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the node."

将一棵普通的二叉树中任一节点的     空右孩子指针 指向 中序遍历的后继节点， 空左孩子指针 指向 中序遍历的前继节点。

实际上就是利用那些空指针，使其指向节点中序遍历的后继节点，前继节点。

特点：

  1. 能够用常数空间复杂度，来进行二叉树的遍历。

  2. 在不显式使用 parent pointer 或 栈 的情况， 也能够找到节点的父亲节点， 虽然比较慢。 

         假设某一节点 k, 有一个右孩子 r。 那么 r 的 left pointer 要么是一个thread 指向 k， 要么就是一个孩子。如果 r 有一个左孩子，那么这个左孩子的 left pointer 要么是一个thread指向 k, 要么也是一个孩子，如此类推。。所以在r 的“最左”的孩子一定指向 k。

         对于k 的 左孩子的情况是类似的，也能够找到父亲节点。

/**
 * copyright @ L.J.SHOU Feb.10, 2014
 * threaded binary tree
*/
#include "threaded-binary-tree.h"
#include <iostream>
#include <cstring>
#include <cassert>
using std::cout;
using std::cin;
using std::string;
using std::endl;

typedef enum {THREAD, LINK } PointerFlag;

struct ThTreeNode{
  char val;
  ThTreeNode *left;
  ThTreeNode *right;
  PointerFlag l_tag; 
  PointerFlag r_tag;
  ThTreeNode()
    :left(NULL), right(NULL), l_tag(LINK), r_tag(LINK){}
};

// global variant: previous visited node
ThTreeNode *g_pre(NULL);

void InThreading(ThTreeNode *root)
{
  if(root == NULL) return;

  InThreading(root->left);

  if(g_pre->right == NULL){
    g_pre->r_tag = THREAD;
	g_pre->right = root;
  }
  if(root->left == NULL){
    root->l_tag = THREAD;
	root->left = g_pre;
  }
  g_pre = root;

  InThreading(root->right);
}

ThTreeNode* InOrderThreading(ThTreeNode *root)
{
  ThTreeNode *head(NULL);

  //头节点
  head = new ThTreeNode();
  head->l_tag = LINK;
  head->r_tag = THREAD;
  if(root == NULL) head->left = head;
  else{
    head->left = root; g_pre = head;
	InThreading(root);
	g_pre->right = head; g_pre->r_tag = THREAD;
	head->right = g_pre; //head->right指向中序遍历最后一个节点 
  }

  return head;
}

void InOrderTraversal(ThTreeNode *root)
{
  ThTreeNode *p = root->left; // p 指向根节点

  while(p != root){
    while(p->l_tag == LINK) p = p->left;
	cout << p->val << " ";

	while(p->r_tag == THREAD && p->right != root){
	  p = p->right;
	  cout << p->val << " ";
	}

	p = p->right;
  }
}

ThTreeNode* Destroy(ThTreeNode *root)
{
  if(root){
    if(root->l_tag == LINK)
      root->left  = Destroy(root->left);
    if(root->r_tag == LINK)
      root->right = Destroy(root->right);
	delete root;
  }
  return NULL;
}

数据结构----Threaded Binary Tree 线索二叉树

原文：http://blog.csdn.net/shoulinjun/article/details/19037819