求節點雙親演算法

⑴ 設計一個演算法從二叉樹中來查找給定節點的雙親結點

//創建二叉樹是按照"二叉排序樹"的原則,例如:
//輸入序列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的雙親