二叉树用二叉链存储,链接时用叶子结点的rchild 域存放指针。请设计一个算法完成①对一棵二叉树加线索(中序);②把二叉树的叶子结点按从左到右的顺序连成一个单链表。③统计二叉树中0到2度结点个数。
中序线索化:
typedef struct tNode{
char data;
int leftThread;
struct tNode *leftChild;
struct tNode *rightChild;
int rightThread;
}ThreadBiNode;
typedef struct
{
ThreadBiNode *root;
ThreadBiNode *current;
int nextComplete;
}ThreadBiTree;
void InThread(ThreadBiNode*current, ThreadBiNode** pre)
{
if (current != NULL)
{
InThread(current->leftChild, pre);
if (current->leftChild == NULL)
{
current->leftThread = 1;
current->leftChild = *pre;
}
else current->leftThread = 0;
if (current->rightChild != NULL)
current->rightThread = 0;
else
current->rightThread = 1;
if ((*pre)->rightChild == NULL)
{
(*pre)->rightThread = 1;
(*pre)->rightChild = current;
}
else
current->rightThread = 0;
*pre = current;
InThread(current->rightChild, pre);
}
}
void CreateInThread(ThreadBiNode** root)
{
ThreadBiNode*t = *root;
ThreadBiNode* current, *pre = *root;
*root = (ThreadBiNode*)malloc(sizeof(BiTreeNode));
if(t==NULL)
{
(*root)->leftThread = 0;
(*root)->rightThread =1;
(*root)->leftChild = *root;
(*root)->rightChild = *root;
}
else
{
current = t;
(*root)->leftChild = t;
(*root)->leftThread = 0;
InThread(current, &pre);
pre->rightChild = *root;
pre->rightThread = 1;
(*root)->rightChild = pre;
(*root)->rightThread = 1;
}
}
ThreadBiNode* GetTreeNode(char item, ThreadBiNode* left, ThreadBiNode* right)
{
ThreadBiNode* p = (ThreadBiNode*)malloc(sizeof(BiTreeNode));
p->data = item;
p->leftChild = left;
p->rightChild = right;
return p;
}
void MakeCharTree(ThreadBiNode**root)
{
ThreadBiNode*b, *c, *d, *e, *f, *g;
g = GetTreeNode('G', NULL, NULL);
d = GetTreeNode('D', NULL, g);
b = GetTreeNode('B', d, NULL);
e = GetTreeNode('E', NULL, NULL);
f= GetTreeNode('F', NULL, NULL);
c = GetTreeNode('C', e, f);
*root = GetTreeNode('A', b, c);
}
void ThreadInitiate(ThreadBiTree *tree, ThreadBiNode *root)
{
tree->root = root;
tree->current = root;
if (root == NULL)
tree->nextComplete = 1;
else
tree->nextComplete = 0;
}
void First(ThreadBiTree *tree)
//定位在中序线索二叉树的第一个结点
{
tree->current = tree->root; //定位根结点
while (tree->current->leftThread == 0) //找到最左子树结点
tree->current = tree->current->leftChild;
if (tree->current == tree->root) tree->nextComplete = 1;
else tree->nextComplete = 0;
}
void Next(ThreadBiTree *tree)
//定位在中序线索二叉树当前结点的下一个结点
{
ThreadBiNode *p = tree->current->rightChild;
if (tree->nextComplete == 1) return;
if (tree->current->rightThread == 0) //若有右孩子结点
while (p->leftThread == 0) p = p->leftChild; //找到最左子树结点
tree->current = p;
if (tree->current == tree->root) tree->nextComplete = 1;
}
int EndOfNext(ThreadBiTree *tree)
//判断是否已到中序线索二叉树的最后一个结点
{
return tree->nextComplete;
}
void main_thread(void)
{
ThreadBiNode *root;
ThreadBiTree tree;
MakeCharTree(&root);
CreateInThread(&root);
printf("二叉树中序正向遍历序列为:");
ThreadInitiate(&tree, root); //循环初始化
for (First(&tree); !EndOfNext(&tree); Next(&tree))
printf("%c ", tree.current->data);
}
帮你找了一些相关方向以作参考:
http://t.csdn.cn/enpkY
二叉树的遍历和线索二叉树
https://blog.csdn.net/qq_42030496/article/details/108585478