附件&程序运行解释.txt

中序线索化的二叉树 能够对二叉树先线索化然后再中序排列 并且输出

通过附带的同部分代码的“验证中序线索正确的程序”证明中序线索化是正确的，最后在project中验证最后作
如：输入“a#b##”则输出"ab"证明中序线索化是正确的 因为输出是按照中序线索化遍历输出的

到了中序线索化的平衡二叉树
申请一个这样的节点类型：
#pragma once
typedef enum PointerTag {Link, Thread};

struct AVLTree
{
     int nData;
     struct AVLTree* pLeft;
     struct AVLTree* pRight;
     int nHeight;
     PointerTag LTag, RTag;
     AVLTree(int & v = int(), AVLTree* pLeft_ = 0, AVLTree* pRight_ = 0)
    : nData(v), pLeft(pLeft_), pRight(pRight_) { }
};
中间包括左右子指针和标记！
AVL化的程序如下：需要分情况不同以不同的方法线索化
typedef struct AVLTree AVLTree;
#include "treeabc.h"
int Max(int a, int b);
int Height(AVLTree* pNode);
AVLTree* Insert(int nData, AVLTree* pNode);
AVLTree* SingleRotateWithLeft(AVLTree* pNode);
AVLTree* SingleRotateWithRight(AVLTree* pNode);
AVLTree* DoubleRotateWithLeft(AVLTree* pNode);
AVLTree* DoubleRotateWithRight(AVLTree* pNode);
void DeleteTree(AVLTree** ppRoot);
void PrintTree(AVLTree* pRoot);


int Max(int a, int b)
{
     return (a > b ? a : b);
}

int Height(AVLTree* pNode)
{
     if (NULL == pNode)
         return -1;

     return pNode->nHeight;
}

AVLTree* Insert(int nData, AVLTree* pNode)
{
     if (NULL == pNode)
     {
         pNode = (AVLTree*)malloc(sizeof(AVLTree));
         pNode->nData = nData;
         pNode->nHeight = 0;
         pNode->pLeft = pNode->pRight = NULL;
     }
     else if (nData < pNode->nData)           // 插入到左子树中
     {
         pNode->pLeft = Insert(nData, pNode->pLeft);
         if (Height(pNode->pLeft) - Height(pNode->pRight) == 2)     // AVL树不平衡
         {
             if (nData < pNode->pLeft->nData)
             {
                 // 插入到了左子树左边, 做单旋转
                 pNode = SingleRotateWithLeft(pNode);
             }
             else 
             {
                 // 插入到了左子树右边, 做双旋转
                 pNode = DoubleRotateWithLeft(pNode);
             }
         }
     }
     else if (nData > pNode->nData)           // 插入到右子树中
     {
         pNode->pRight = Insert(nData, pNode->pRight);
         if (Height(pNode->pRight) - Height(pNode->pLeft) == 2)     // AVL树不平衡
         {
             if (nData > pNode->pRight->nData)
             {
                 // 插入到了右子树右边, 做单旋转
                 pNode = SingleRotateWithRight(pNode);
             }
             else 
             {
                 // 插入到了右子树左边, 做双旋转
                 pNode = DoubleRotateWithRight(pNode);
             }
         }
     }

     pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;

     return pNode;
}

/********************************************************************
       pNode                                 pNode->pLeft 
       /                                              \
pNode->pLeft                       ==>               pNode
            \                                        /
           pNode->pLeft->pRight                    pNode->pLeft->pRight
*********************************************************************/
AVLTree* SingleRotateWithLeft(AVLTree* pNode)
{
     AVLTree* pNode1;

     pNode1 = pNode->pLeft;
     pNode->pLeft = pNode1->pRight;
     pNode1->pRight = pNode;

     // 结点的位置变了, 要更新结点的高度值
     pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
     pNode1->nHeight = Max(Height(pNode1->pLeft), pNode->nHeight) + 1;

     return pNode1;
}

/********************************************************************
pNode                                    pNode->pRight
      \                                   /
      pNode->pRight            ==>     pNode 
      /                                    \
pNode->pRight->pLeft                      pNode->pRight->pLeft
*********************************************************************/
AVLTree* SingleRotateWithRight(AVLTree* pNode)
{
     AVLTree* pNode1;

     pNode1 = pNode->pRight;
     pNode->pRight = pNode1->pLeft;
     pNode1->pLeft = pNode;

     // 结点的位置变了, 要更新结点的高度值
     pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
     pNode1->nHeight = Max(Height(pNode1->pRight), pNode->nHeight) + 1;

     return pNode1;
}

AVLTree* DoubleRotateWithLeft(AVLTree* pNode)
{
     pNode->pLeft = SingleRotateWithRight(pNode->pLeft);

     return SingleRotateWithLeft(pNode);
}

AVLTree* DoubleRotateWithRight(AVLTree* pNode)
{
     pNode->pRight = SingleRotateWithLeft(pNode->pRight);

     return SingleRotateWithRight(pNode);
}

// 后序遍历树以删除树
void DeleteTree(AVLTree** ppRoot)
{
     if (NULL == ppRoot || NULL == *ppRoot)
         return;

     DeleteTree(&((*ppRoot)->pLeft));
     DeleteTree(&((*ppRoot)->pRight));
     free(*ppRoot);
     *ppRoot = NULL;
}

// 中序遍历打印树的所有结点, 因为左结点 < 父结点 < 右结点, 因此打印出来数据的大小是递增的
void PrintTree(AVLTree* pRoot)
{
     if (NULL == pRoot)
         return;

     static int n = 0;

     PrintTree(pRoot->pLeft);
     printf("[%d]nData = %d\n", ++n, pRoot->nData);
     PrintTree(pRoot->pRight);
}
中序线索化的程序如下：
//ThreadBiTree.cpp
#include <iostream>
#include "treeabc.h"
using namespace std;

typedef struct AVLTree AVLTree;

AVLTree *BiTree, *pre, *Thrt;  //采用全局变量使得函数能返回多个值

AVLTree *CreateBiTree(AVLTree *BiTree)  //先序递归构造二叉树
{
 char ch;  
 ch = getchar();
 if(ch == '#')  //若为叶子节点则其左右孩子均为空
  BiTree = NULL;
 else
 {
  BiTree->nData = ch;    //生成根节点
  BiTree->pLeft = (AVLTree *)malloc(sizeof(AVLTree));
  BiTree->pLeft = CreateBiTree(BiTree->pLeft); //构造左子树
  BiTree->pRight = (AVLTree *)malloc(sizeof(AVLTree));
  BiTree->pRight = CreateBiTree(BiTree->pRight); //构造右子树
 }
 return BiTree;
}

AVLTree *InThreading(AVLTree *BiTree)  //中序线索化二叉树
{
 if(BiTree)
 {
  BiTree->pLeft = InThreading(BiTree->pLeft);  //左子树线索化
  if(!BiTree->pLeft)
  {
   BiTree->LTag = Thread;
   BiTree->pLeft = pre;  
  }
  if(!pre->pRight)
  {
   pre->RTag = Thread;
   pre->pRight = BiTree;
  }
  pre = BiTree;  //保持pre指向BiTree的前驱
  BiTree->pRight = InThreading(BiTree->pRight);  //右子树线索化
 }
 return BiTree;
}
AVLTree *InOrderThreading(AVLTree *BiTree)  //中序遍历并线索化
{
 Thrt = (AVLTree *)malloc(sizeof(AVLTree));
 pre = (AVLTree *)malloc(sizeof(AVLTree));
 Thrt->LTag = Link;   //初始化头节点
 Thrt->RTag = Thread;
 Thrt->pRight = Thrt;  //右指针回指
 if(!BiTree)
  Thrt->pLeft = Thrt; //若树空则左指针回指
 else
 {
  Thrt->pLeft = BiTree;
  pre = Thrt;
  BiTree = InThreading(BiTree); //中序线索化
  pre->pRight = Thrt;  //最后一个节点线索化
  pre->RTag = Thread;
  Thrt->pRight = pre;
 }
 return BiTree;
}
void InOrderTraverse(AVLTree *BiTree)  //中序遍历线索二叉树并输出
{
 AVLTree *p;
 p = (AVLTree *)malloc(sizeof(AVLTree));
 p = Thrt->pLeft;
 while(p != Thrt && p)
 {
  while(p->LTag != Thread)
   p = p->pLeft;
  cout<<p->nData<<"      ";
  while(p->RTag == Thread && p->pRight != Thrt)
  {
   p = p->pRight;
   cout<<p->nData<<"      ";
  }
  p = p->pRight;
 }
}


最后运行的结果包含nHeight以及nDate的值 且中序遍历的值和线索化后遍历的的结果是一样的
通过分析nHeight以及nDate的值得之最后得到的树是中序线索化了的AVL树。。。
解题思路是先随机生成十个数，并且将其入树，然后AVL化，继而中序线索化。
通过验证是可行的