# [三叉链表]利用三叉链表找后序线索二叉树的后继

```//Three.h
#ifndef THREE_H
#define THREE_H
#include <iostream>
#include <string.h>
using namespace std;

typedef struct ThreeNode
{
char data;
struct ThreeNode *lChild, *rChild, *Parent;//采用三叉链表，增加一个指向双亲的结点
Tag lTag, rTag;
}ThreeNode, *PThreeNode;

class Three
{
protected:
PThreeNode root;
public:
Three()//默认构造函数
{
root = NULL;
}
Three(PThreeNode r)//构造函数
{
root = r;
}
~Three()//析构函数
{
PThreeNode temp = First();
while(temp != root)
{
delete temp;
temp = Next(temp);
}
delete root;
}

void CreateTree(PThreeNode &e, char TreeArray[], PThreeNode Par)//已知后序序列，创建树
{
static int count = strlen(TreeArray)-1;//这里我们反其道而行之，总最后一个开始，也就是根节点
char ch = TreeArray[count--];//后序遍历的第一个字符一定为‘#‘，这样程序就不对了
if(ch == ‘#‘)
{
e = NULL;
}
else
{
e = new ThreeNode;
e->data = ch;
e->Parent = Par;
CreateTree(e->rChild, TreeArray, e);
CreateTree(e->lChild, TreeArray, e);
}
}
void CreateTree(char TreeArray[])
{
CreateTree(root, TreeArray, NULL);
}

void Print(PThreeNode &e)//后序打印二叉树
{
if(e != NULL)
{
Print(e->lChild);
Print(e->rChild);
cout << e->data << "  ";
}
}
void Print()
{
Print(root);
}

{
PThreeNode temp = First();
while(temp != root)
{
cout << temp->data << "  ";
temp = Next(temp);
}
cout << temp->data;
}

PThreeNode Find(const char &ch) //查找结点
{
PThreeNode p = First();
while (p != NULL && p->data != ch)
{
p = Next(p);
}
return p;
}
PThreeNode First() const//找到后序遍历的首位置
{
if (root == NULL)
return  NULL;
else
{
PThreeNode p = root;
while (p->lChild != NULL)
p = p->lChild;
return p;
}
}
PThreeNode Next(PThreeNode &e)//返回结点的下一位置
{
PThreeNode temp = e;
PThreeNode Par = temp->Parent;
{
return temp->rChild;
}
else if(Par->rChild == temp)
{
return Par;
}
else if(root == e)
{
return root;
}
else
{
temp = Par;
while(temp->lChild != e || temp->lTag != Thread)
{
temp = temp->rChild;
{
temp = temp->lChild;
}
}
return temp;
}
}

PThreeNode GetRoot() const//得到根节点
{
return root;
}

{
if(e !=NULL )
{

if(e->lChild == NULL)
{
e->lChild = pre;
}

if(pre != NULL && pre->rChild == NULL)
{
pre->rChild = e;
}

pre = e;
}
}

{
PThreeNode temp = NULL;
}

};

#endif```

```#include "Three.h"
#include <iostream>
using namespace std;

int main()
{
char ch[] = {‘#‘,‘#‘,‘D‘,‘#‘,‘#‘,‘G‘,‘#‘,‘E‘,‘B‘,‘#‘,‘#‘,‘#‘,‘F‘,‘C‘,‘A‘};
Three bt;
PThreeNode p;

bt.CreateTree(ch);
cout << "后序遍历的顺序为：";
bt.Print();
cout << endl;

cout << "线索化后，后序遍历的顺序为：";
cout << endl;

p = bt.Find(‘A‘);//根节点为特殊情况
if(p != bt.GetRoot())
{
p = bt.Next(p);
cout << "该结点后继为：" << p->data << endl;
}
else
cout << "该结点为线索树的最后一个元素，无后继！！！" << endl;

system("pause");
return 0;
}```

[三叉链表]利用三叉链表找后序线索二叉树的后继

(0)
(0)