求节点双亲算法

⑴ 设计一个算法从二叉树中来查找给定节点的双亲结点

//创建二叉树是按照"二叉排序树"的原则,例如:
//输入序列201510121825301617,第1个数据是20,作为根结点,
//第2个数据是15,比20小,作为20的左分支,第3个数据是10,比20和15小,
//作为15的左分支,第4个数是12,比20和15小,但比10大,作为10的右分支,
//如此类推,创建完整的二叉树.
//查找给定节点的双亲结点,用[栈],是非递归法.
//
//示例演示
//请输入结点的个数:9
//请连续输入9个数据(用空格隔开):201510121825301617
//创建二叉树后
//先序遍历序列:201510121816172530
//中序遍历序列:101215161718202530
//后序遍历序列:121017161815302530
//
//输入要查找的结点数值(退出按CTR+Z):17
//17的双亲结点是16
//
//输入要查找的结点数值(退出按CTR+Z):30
//30的双亲结点是25
//
//20
///
//1525
///\
//101830
///
//1216
//
//17
//

#include<stdio.h>
#include<stdlib.h>

structtreeNode//二叉树的结构体
{
intdata;
structtreeNode*left;
structtreeNode*right;
};
typedefstructtreeNode*BTree;

typedefstructstack_node//栈的结构体
{
BTreebt;
	structstack_node*next;
}stack_list,*stack_link;

//插入节点(非递归)
BTreeinsertNode(BTreeroot,intvalue)
{
BTreenewnode;
BTreecurrent;
BTreeback;
newnode=(BTree)malloc(sizeof(structtreeNode));
if(newnode==NULL)
{
printf("
内存分配失败!
");
exit(1);
}
newnode->data=value;
newnode->left=NULL;
newnode->right=NULL;
if(root==NULL)
{
returnnewnode;
}
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;
}
returnroot;
}

BTreecreateTree()//创建二叉树(非递归)
{
BTreeroot=NULL;
intlen;
intnum;
inti;

printf("请输入结点的个数:");
scanf("%d",&len);
printf("请连续输入%d个数据(用空格隔开):",len);
for(i=0;i<len;i++)
{
scanf("%d",&num);
root=insertNode(root,num);
}
returnroot;
}

//检查[栈]是否是空
intisStackEmpty(stack_linkstack)
{
	if(stack==NULL)
{
return1;
}
else
{
return0;
}
}

//入栈
stack_linkpush(stack_linkstack,BTreebt)
{
	stack_linknew_node;

	new_node=(stack_link)malloc(sizeof(stack_list));
	if(!new_node)
	{
		returnNULL;
	}
	new_node->bt=bt;
	new_node->next=stack;
	stack=new_node;
	returnstack;
}

//出栈
stack_linkpop(stack_linkstack,BTree*bt)
{
	stack_linktop;

	if(isStackEmpty(stack))
	{
		*bt=NULL;
		returnNULL;
	}
	top=stack;
	*bt=top->bt;
	stack=top->next;
	free(top);
	returnstack;
}

voidfindParent(BTreebt,intx)//查找双亲结点(非递归)
{
BTreep=NULL;
stack_linkoneStack=NULL;

if(bt==NULL)return;

p=bt;//当前二叉树的节点
if(p->data==x)
{
printf("%d是根结点,没有双亲结点
",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
",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不是二叉树的结点
",x);
}

voidpreOrder(BTreep)//先序遍历(递归)
{
if(p!=NULL)
{
printf("%d",p->data);
preOrder(p->left);
preOrder(p->right);
}
}

voidinOrder(BTreep)//中序遍历(递归)
{
if(p!=NULL)
{
inOrder(p->left);
printf("%d",p->data);
inOrder(p->right);
}
}

voidpostOrder(BTreep)//后序遍历(递归)
{
if(p!=NULL)
{
postOrder(p->left);
postOrder(p->right);
printf("%d",p->data);
}
}

intmain()
{
BTreeroot=NULL;
intx;
intret;

root=createTree();//创建二叉树(非递归)

printf("
创建二叉树后");
printf("
先序遍历序列:");
preOrder(root);
printf("
中序遍历序列:");
inOrder(root);
printf("
后序遍历序列:");
postOrder(root);

while(1)
{
printf("
输入要查找的结点数值(退出按CTRL+Z):");
ret=scanf("%d",&x);
if(ret<=0)//组合键CTRL+Z,得到ret=-1,可以退出循环
{
break;
}
findParent(root,x);//查找双亲结点
}

printf("
");
	return0;
}

⑵ 以二叉链表为存储结构,如何编写算法求二叉树中结点x的双亲

如下代码是通过算法的方式求父节点，其中二叉树的创建是先序方式，如abd##e##c##

#include "stdlib.h"
typedef int Element;
struct Tree
{
Element data;
struct Tree *left;
struct Tree *right;
};

void CreateBinSortTree(struct Tree **t);
void InsertNode2Tree(struct Tree **root, Element num);
void PrintTree(struct Tree *r, int order);
struct Tree *FindParent(struct Tree *r, char ch);

int main(int argc, char* argv[])
{
printf("请输入一组字母(#表示子树为空)\n");
struct Tree *t=NULL;
CreateBinSortTree(&t);
printf("\n根左右:");
PrintTree(t,1);
printf("\n左根右:");
PrintTree(t,2);
printf("\n左右根:");
PrintTree(t,3);
printf("\n");
char ch='a';
getchar();//获取前次输入回车符
printf("请输入节点数据值");
scanf("%c",&ch);
struct Tree *temp = FindParent(t,ch);
if (temp!=NULL)
{
printf("其父节点数据值为:%c",temp->data);
}
else
{
printf("找不到父节点");
}
return 0;

}
void CreateBinSortTree(struct Tree **t)
{
char ch;
ch = getchar();
if (ch == '#')
{
*t = NULL;
return ;
}
*t = (struct Tree *)malloc(sizeof(struct Tree));
(*t)->data = ch;
CreateBinSortTree( &((*t)->left));
CreateBinSortTree( &((*t)->right));

}

void PrintTree(struct Tree *r, int order)
{
if (r == NULL)
{
return ;
}
switch(order)
{
case 1:
printf("%c ",r->data);
PrintTree(r->left,order);
PrintTree(r->right,order);
break;
case 2:
PrintTree(r->left,order);
printf("%c ",r->data);
PrintTree(r->right,order);
break;
case 3:
PrintTree(r->left,order);
PrintTree(r->right,order);
printf("%c ",r->data);
break;
}
}

struct Tree *FindParent(struct Tree *r, char ch)
{
if (r==NULL)
{
return NULL;
}
if (r->left != NULL)
{
if (r->left->data == ch)
{
return r;
}
}
if (r->right != NULL)
{
if (r->right->data == ch)
{
return r;
}
}
struct Tree *t=FindParent(r->left,ch);
if (t != NULL)
{
return t;
}
t = FindParent(r->right,ch);
return t;
}

⑶ 查找双亲结点的算法

查找双亲结点的方法：
node* search（node *par,node *cur）
{
if(cur)
{
search(cur,cur->lchild);
if(cur->data==x)return par;
search(cur,cur->rchild);
}
}
双亲结点就是父节点，一般指的是树状结构，相对于当前的节点而言，它的上层节点就叫做父节点。

⑷ 设计一个求结点x在二叉树中的双亲结点算法。

正常的方法是用非递归的二叉树后序遍历，当遍历到结点x时，栈顶就是x的双亲