// 创建二叉树是按照"二叉排序树"的原则,例如:
// 输入序列20 15 10 12 18 25 30 16 17, 第1个数据是20,作为根结点,
// 第2个数据是15,比20小,作为20的左分支,第3个数据是10,比20和15小,
// 作为15的左分支,第4个数是12,比20和15小,但比10大,作为10的右分支,
// 如此类推,创建完整的二叉树.
// 查找给定节点的双亲结点,用[栈],是非递归法.
//
// 示例演示
// 请输入结点的个数: 9
// 请连续输入9个数据(用空格隔开): 20 15 10 12 18 25 30 16 17
// 创建二叉树后
// 先序遍历序列: 20 15 10 12 18 16 17 25 30
// 中序遍历序列: 10 12 15 16 17 18 20 25 30
// 后序遍历序列: 12 10 17 16 18 15 30 25 30
//
// 输入要查找的结点数值(退出按CTR+Z): 17
// 17的双亲结点是16
//
// 输入要查找的结点数值(退出按CTR+Z): 30
// 30的双亲结点是25
//
// 20
// / \
// 15 25
// / \ \
// 10 18 30
// \ /
// 12 16
// \
// 17
//
#include
#include
struct treeNode //二叉树的结构体
{
int data;
struct treeNode *left;
struct treeNode *right;
};
typedef struct treeNode *BTree;
typedef struct stack_node //栈的结构体
{
BTree bt;
struct stack_node *next;
} stack_list, *stack_link;
//插入节点(非递归)
BTree insertNode(BTree root,int value)
{
BTree newnode;
BTree current;
BTree back;
newnode=(BTree)malloc(sizeof(struct treeNode));
if(newnode==NULL)
{
printf("\n内存分配失败!\n");
exit(1);
}
newnode->data=value;
newnode->left=NULL;
newnode->right=NULL;
if(root==NULL)
{
return newnode;
}
else
{
current=root;
while(current!=NULL)
{
back=current;
if(current->data > value)
current=current->left;
else
current=current->right;
}
if(back->data > value)
back->left=newnode;
else
back->right=newnode;
}
return root;
}
BTree createTree() //创建二叉树(非递归)
{
BTree root=NULL;
int len;
int num;
int i;
printf("请输入结点的个数: ");
scanf("%d",&len);
printf("请连续输入%d个数据(用空格隔开): ",len);
for(i=0;i {
scanf("%d",&num);
root=insertNode(root,num);
}
return root;
}
//检查[栈]是否是空
int isStackEmpty(stack_link stack)
{
if(stack == NULL)
{
return 1;
}
else
{
return 0;
}
}
//入栈
stack_link push(stack_link stack,BTree bt)
{
stack_link new_node;
new_node=(stack_link)malloc(sizeof(stack_list));
if(!new_node)
{
return NULL;
}
new_node->bt=bt;
new_node->next=stack;
stack=new_node;
return stack;
}
//出栈
stack_link pop(stack_link stack,BTree *bt)
{
stack_link top;
if(isStackEmpty(stack))
{
*bt = NULL;
return NULL;
}
top=stack;
*bt=top->bt;
stack=top->next;
free(top);
return stack;
}
void findParent(BTree bt,int x) //查找双亲结点(非递归)
{
BTree p=NULL;
stack_link oneStack=NULL;
if(bt == NULL) return;
p=bt; //当前二叉树的节点
if(p->data == x)
{
printf("%d是根结点,没有双亲结点\n",x);
return;
}
oneStack=push(oneStack,p);
while(isStackEmpty(oneStack) != 1) //[栈]不是空
{
oneStack=pop(oneStack,&p); //出栈
if((p->right!=NULL && p->right->data==x) ||
(p->left!=NULL && p->left->data==x))
{
printf("%d的双亲结点是%d\n",x,p->data);
while(isStackEmpty(oneStack)!=1) //清栈
{
oneStack=pop(oneStack,&p);
}
return;
}
else
{
if(p->right != NULL) //如果有右子树,入栈
{
oneStack=push(oneStack,p->right);
}
if(p->left != NULL) //如果有左子树,入栈
{
oneStack=push(oneStack,p->left);
}
}
}
printf("%d不是二叉树的结点\n",x);
}
void preOrder(BTree p) //先序遍历(递归)
{
if(p!=NULL)
{
printf("%d ",p->data);
preOrder(p->left);
preOrder(p->right);
}
}
void inOrder(BTree p) //中序遍历(递归)
{
if(p!=NULL)
{
inOrder(p->left);
printf("%d ",p->data);
inOrder(p->right);
}
}
void postOrder(BTree p) //后序遍历(递归)
{
if(p!=NULL)
{
postOrder(p->left);
postOrder(p->right);
printf("%d ",p->data);
}
}
int main()
{
BTree root=NULL;
int x;
int ret;
root=createTree();//创建二叉树(非递归)
printf("\n创建二叉树后");
printf("\n先序遍历序列: ");
preOrder(root);
printf("\n中序遍历序列: ");
inOrder(root);
printf("\n后序遍历序列: ");
postOrder(root);
while(1)
{
printf("\n输入要查找的结点数值(退出按CTRL+Z): ");
ret=scanf("%d",&x);
if(ret<=0) //组合键CTRL+Z,得到ret=-1,可以退出循环
{
break;
}
findParent(root,x); //查找双亲结点
}
printf("\n");
return 0;
}
