虚心请教，对于线索二叉树的一些问题
问题为:不知道怎么把线索为1的前后驱元素的地址放在对应的指针区域中
例如下面的二叉树:
A
B E
C D F
就是不知道怎么把C的后驱元素的地址指针指向B D的前驱元素指向B后驱指向A。。。。
希望能有大佬可以完善一下代码，或者讲一下方法，我再去琢磨一下
#include<stdio.h>
#include<stdlib.h>
typedef char TYPE;
//线索为0为孩子节点
//线索为1为前后驱线索
typedef struct tree
{
struct tree *left;
char clue_left;//左
TYPE data;
char clue_right;//右
struct tree *right;
}clue_pot,*tree;
inclute_tree(tree *p)
{
char c;
scanf("%c",&c);
if(c==' ')
{
*p = NULL;
}
else
{
*p = (clue_pot *)malloc(sizeof(clue_pot));
(*p)->data = c;
(*p)->clue_left = '0';
(*p)->clue_right = '0';
inclute_tree(&(*p)->left);
inclute_tree(&(*p)->right);
}
}
change_tree(clue_pot *head)
{
if( head != NULL)
{
if(change_tree(head->left)==1)
{
head->clue_left='1';
}
if(change_tree(head->right)==1)
{
head->clue_right='1';
head->right = pre->left;
}
}
else
{
return 1;
}
}
check_tree(tree root,int numb)
{
if(root != NULL)
{
printf("%c在第%d层\n",root->data,numb);
printf("左线索:%c,左边指针地址:%p,本身地址:%p,右线索:%c,右边指针地址:%p\n",root->clue_left,root->left,root,root->clue_right,root->right);
check_tree(root->left,numb+1);
check_tree(root->right,numb+1);
}
}
int main()
{
tree test=NULL;
inclute_tree(&test);
change_tree(test);
check_tree(test,1);
return 0;
} {:10_266:}琢磨一晚上了 {:9_223:}自己琢磨出来了，代码分享一下，做了挺多注释的
#include<stdio.h>
#include<stdlib.h>
typedef char TYPE;
//线索为0为孩子节点
//线索为1为前后驱线索
typedef struct tree
{
struct tree *left;//存放左下节点的地址
char clue_left;//如果左下还有节点，值为0，代表当前为左下的父节点，left存放的为下一个节点地址；如果左下为空，值为1。当值为1时候按中序排序left存放上一个节点地址
TYPE data;//储存节点存放的信息
char clue_right;//如果右下还有节点，值为0，代表当前为右下的父节点，left存放的为下一个节点地址；如果左下为空，值为1。当值为1时候按中序排序left存放上一个节点地址
struct tree *right;//存放右下节点的地址
}clue_pot,*tree;//定义一个树的节点；定义一个指向树的节点的指针
//初始化二叉树，递归方法
//用前序输入空格代表没有下一个节点
inclute_tree(tree *p)
{
char c;
scanf("%c",&c);
if(c==' ')
{
*p = NULL;
}
else
{
*p = (clue_pot *)malloc(sizeof(clue_pot));
(*p)->data = c;
(*p)->clue_left = '0';
(*p)->clue_right = '0';
inclute_tree(&(*p)->left);
inclute_tree(&(*p)->right);
}
}
tree pre; //定义一个全局变量（指向二叉树节点的指针类型）
//如果线索为0的话 在叶子层的左右指针要按 中序排序 指回上一个节点，此时pre的作用就来了
//作用：用于递归到最后一层时把最后一层节点赋值到这，结束后回到上一层时，此时操作这个变量（最后一层节点）的右节点指针指向当前节点（从最后一层回退）的地址
tree two;
change_tree(clue_pot *head)
{
if( head != NULL)
{
//首先递归到最左下角的树节点
if(change_tree(head->left)==1)
{
head->clue_left='1';
head->left = pre;
}
if(pre->right==NULL)
{
pre->right = head;
pre = head;
}
pre = head;
if(change_tree(head->right)==1)
{
head->clue_right='1';
}
}
else
{
return 1;
}
}
check_tree(tree root,int numb)
{
if(root != NULL)
{
printf("%c在第%d层\n",root->data,numb);
printf("左线索:%c,左边指针地址:%p,本身地址:%p,右线索:%c,右边指针地址:%p\n",root->clue_left,root->left,root,root->clue_right,root->right);
if(root->clue_left=='1'&&root->clue_right=='1')
return 0;
getchar();
check_tree(root->left,numb+1);
check_tree(root->right,numb+1);
}
}
//迭代查询二叉树
//打印则为按照中序排序的顺序进行打印
check_tree2(tree root,tree end)
{
while(root->left != end)
{
root = root->left;
}
//循环出来root 为左边最末的节点
while(root != NULL)
{
printf("左线索:%c,左边指针地址:%p,本身地址:%p,data内容:%c,右线索:%c,右边指针地址:%p\n",root->clue_left,root->left,root,root->data,root->clue_right,root->right);
root = root->right;
}
}
int main()
{
tree test=NULL;
inclute_tree(&test);
two = (clue_pot *)malloc(sizeof(clue_pot));
two->left = test;
two->right = two;
two->clue_right='0';
pre = two;
change_tree(test);
pre->left = two;
check_tree2(test,two);
return 0;
}
页:
[1]