线索二叉树C++实现

#include<iostream>
#include<stdlib.h>
#define maxsize 100

using namespace std;

typedef struct BTNode{
    char val;
    struct BTNode *lchild, *rchild;
    int ltag, rtag;
}BTNode, *BiNode;

BTNode* stack[maxsize];
int top = -1;

/**
 * 找到中序遍历的第一个起始顶点
 */
inline BTNode* First(BTNode *root){
    while(root->ltag == 0)
        root = root->lchild;
    return root;
}

/**
 * 找到中序遍历的下一个顶点，树已被中序线索化
 */
inline BTNode* InOrderNext(BTNode *root){
    if(root->rtag == 0)
        return First(root->rchild);
    else
        return root->rchild;
}

/**
 * debug，用来打印线索化之后的树的信息
 */
inline void debug(){
    for(int i = 0; i <= top; i++){
      cout << "[debug]: BTNode->[";
      cout << (void *) stack[i];
      cout << "]" << endl;
      cout << "   [val]   :" << stack[i]->val << endl;
      cout << "   [lchild]:";
      cout << (void *) stack[i]->lchild << endl;
      cout << "   [rchild]:";
      cout << (void *) stack[i]->rchild << endl;
      cout << "   [ltag]  :" << stack[i]->ltag << endl
           << "   [rtag]  :" << stack[i]->rtag << endl;
    }
}

void CreateTree(BTNode *&root);
void PreOrderThreading(BTNode *root, BTNode *&pre);
void InOrderThreading(BTNode *root, BTNode *&pre);
void PreOrderThreadingTraversal(BTNode *root);
void InOrderThreadingTraversal(BTNode *root);
void PostOrderThreading(BTNode *root, BTNode *&pre);
void PostOrderThreadingTraversal(BTNode *root);

void CreateTree(BTNode *&root){
    char c;
    cin >> c;
    if(c != '#'){
        root = (BTNode *) malloc(sizeof(struct BTNode));
        if(!root){
            cerr << "No More Memory!" << endl;
            exit(-1);
        }
        root->val = c;
        root->lchild = root->rchild = NULL;
        root->ltag = root->rtag = 0;
        CreateTree(root->lchild);
        CreateTree(root->rchild);
    }else{
        root = NULL;
    }
}

void PreOrderThreading(BTNode *root, BTNode *&pre){
    if(root){
        if(!root->lchild){
            root->lchild = pre;
            root->ltag = 1;
        }
        if(pre && !pre->rchild){
            pre->rchild = root;
            pre->rtag = 1;
        }
        pre = root;
        if(root->ltag == 0){
            PreOrderThreading(root->lchild, pre);
        }
        if(root->rtag == 0){
            PreOrderThreading(root->rchild, pre);
        }
    }
}

void PreOrderThreadingTraversal(BTNode *root){
    if(root){
        cout << root->val << " ";
        if(root->ltag == 0){
            PreOrderThreadingTraversal(root->lchild);
        }else{
            PreOrderThreadingTraversal(root->rchild);
        }
    }
}

void InOrderThreading(BTNode *root, BTNode *&pre){
    if(root){
        stack[++top] = root;
        InOrderThreading(root->lchild, pre);
        if(!root->lchild){
            root->lchild = pre;
            root->ltag = 1;
        }
        if(pre && !pre->rchild){
            pre->rchild = root;
            pre->rtag = 1;
        }
        pre = root;
        InOrderThreading(root->rchild, pre);
    }
}

void InOrderThreadingTraversal(BTNode *root){
    for(BTNode *p = First(root); p; p = InOrderNext(p))
        cout << p->val << " ";
}

void PostOrderThreading(BTNode *root, BTNode *&pre){
    if(root){
        stack[++top] = root;
        PostOrderThreading(root->lchild, pre);
        PostOrderThreading(root->rchild, pre);
        if(!root->lchild){
            root->lchild = pre;
            root->ltag = 1;
        }
        if(pre && !pre->rchild){
            pre->rchild = root;
            pre->rtag = 1;
        }
        pre = root;
    }
}

void PostOrderThreadingTraversal(BTNode *root){
    //PostOrder需要在原有的节点的类型定义上增加一个
    //parent节点，否则，遍历的时候可能会没有办法
    //回到上一层节点当中
}

int main(){
    BTNode *root, *pre = NULL;
    CreateTree(root);
    //PostOrderThreading(root, pre);
    //debug();
    //PostOrderThreadingTraversal(root);
    return 0;
}

线索二叉树C++实现

原文：https://www.cnblogs.com/dotdashdotdash/p/11863588.html