找二叉树双亲结点算法c语言

Ⅰ 以二叉链表为存储结构,如何编写算法求二叉树中结点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;
}

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

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

Ⅲ 查找双亲结点的算法

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

Ⅳ 二叉树结点的查找C语言实现

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

typedef struct bitnode
{
char data;
struct bitnode *lchild, *rchild;
}bitnode, *bitree;

void createbitree(t,n)
bitnode ** t;
int *n;
{
char x;
bitnode *q;

*n=*n+1;
printf("\n Input %d DATA:",*n);
x=getchar();
if(x!=’\n’) getchar();

if (x==’\n’)
return;

q=(bitnode*)malloc(sizeof(bitnode));
q->data=x;
q->lchild=NULL;
q->rchild=NULL;
*t=q;

printf(" This Address is: %o, Data is: %c,\n Left Pointer is: %o, Right Pointer is: %o",q,q->data,q->lchild,q->rchild);

createbitree(&q->lchild,n);
createbitree(&q->rchild,n);
return;
}

void visit(e)
bitnode *e;
{
printf(" Address: %o, Data: %c, Left Pointer: %o, Right Pointer: %o\n",e,e->data,e->lchild,e->rchild);
}

void preordertraverse(t)
bitnode *t;
{
if(t)
{
visit(t);
preordertraverse(t->lchild);
preordertraverse(t->rchild);
return ;
}else return ;
}

void countleaf(t,c)
bitnode *t;
int *c;
{
if(t!=NULL)
{
if (t->lchild==NULL && t->rchild==NULL)
{*c=*c+1;
}
countleaf(t->lchild,c);
countleaf(t->rchild,c);
}
return;
}

int treehigh(t)
bitnode *t;
{int lh,rh,h;
if(t==NULL)
h=0;
else{
lh=treehigh(t->lchild);
rh=treehigh(t->rchild);
h=(lh>rh ? lh:rh)+1;
}
return h;
}
main()
{
bitnode *t; int count=0;
int n=0;

printf("\n Please input TREE Data:\n");
createbitree(&t,&n);

printf("\n This is TREE Struct: \n");
preordertraverse(t);

countleaf(t,&count);
printf("\n This TREE has %d leaves ",count);

printf(" , High of The TREE is: %d\n",treehigh(t));
}

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

//创建二叉树是按照"二叉排序树"的原则,例如:
//输入序列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;
}

Ⅵ 求一个c语言遍历二叉树的算法

#include <stdio.h>
#include <stdlib.h>
//1 根据二叉树的性质5，结点按完全二叉树来编号，则根据结点编号，
// 就可算出其双亲结点的编号，以及该结点是左孩子还是右孩子，
// 这样一来，就可把该结点的指针赋予双亲结点的相应指针域。
// 怎样找到双亲结点呢？，在输入双亲结点的同时要把结点的指针
// 保存起来。也就是说，要设计一个指针数组，来保存每个结点指针。
// 这样，当输入下层结点时，才能找到它的双亲。
//2 回想单链表的建立过程，单链表建立过程中，只需把当前结点，
// 当成前驱结点,故只需设计一个指针变量即可。

typedef char ElementType;

typedef struct node //二叉树链表结点
{
ElementType data;
struct node *lchild,*rchild;//左、右孩子指针
}BinNode,*BinTree; //结点和结点指针的标识符

BinNode * creat(void) //建二叉树链表(返回根结点的指针)
{
int i,j;
ElementType x;
BinNode *q,*s[20];//结点指针、辅助数组(存放结点的指针,该结点有可能是双亲结点)
BinNode *t=NULL; //根结点指针(目前是空树,生成树后要返回根结点指针)

printf("\n 请输入结点编号i和结点值x");
printf("\n 如：1A 2B 3C 4D 5E 7F 00(全为0，输入结束)");
printf("\n 或：1A 2B 3C 4D 6F 7G 00(全为0，输入结束)");
printf("\n 或：1A 2B 3C 5E 7G 15M 00(全为0，输入结束)\n");
scanf("%d%c",&i,&x); //输入结点编号及结点值

while((i!=0)&&(x!=0))
{
q=(BinNode *)malloc(sizeof(BinNode));//申请结点内存
q->data=x; //保存数据
q->lchild=NULL;
q->rchild=NULL;
s[i]=q; //s[i]存放第i号结点的指针
if(i==1) //1号结点是根结点
t=q; //保存根结点指针,以备返回
else
{
j=i/2; //由该结点号求双亲结点号
if((i%2)==0)
s[j]->lchild=q; //i为偶数是左孩子,该结点指针存入双亲结点的左孩子指针
else
s[j]->rchild=q; //i为奇数是右孩子,该结点指针存入双亲结点的右孩子指针
}
scanf("%d%c",&i,&x);//继续输入结点编号和结点值
}
return t; //返回根结点的指针(二叉链表的指针)
}

void DisplayBinTree(BinTree T)//用缩进表示二叉树
{
BinTree stack[100],p; //栈(结点指针数组)、当前结点指针
int level[100]; //栈(每层根结点对应的空格 数 )
int flag[100]; //栈（flag[]=0,1,2分别表示是根结点、左子树、右子树 ）
int top,n,i; //栈顶指针，空格个数，循环变量

if(T!=NULL) //若有根结点
{
top=1; //1号结点(根结点 )
stack[top]=T; //入栈(保存根结点指针)
level[top]=1; //显示空格的个数
flag[top]=0; //根结点
while(top>0) //有根结点
{
p=stack[top]; //取根结点指针
n=level[top]; //取显示空格的个数

for(i=1;i<=n;i++)//显示空格(缩进)
printf(" ");

if(flag[top]==0) //若是根结点
printf("T:%c\n",p->data); //显示根结点
else //不是根结点
{
if(flag[top]==2) //是右子树根结点
printf("R:%c\n",p->data); //显示右子树根结点
if(flag[top]==1) //是左子树根结点
printf("L:%c\n",p->data,top); //显示左子树根结点
}

top--; //显示一个(出栈一个)结点，top-1

if(p->rchild!=NULL)//若有右孩子
{
top++; //保存一个根结点,top+1
stack[top]=p->rchild;//保存右子树根结点
level[top]=n+3;
flag[top]=2;
}
if(p->lchild!=NULL)//若有左孩子
{
top++;
stack[top]=p->lchild;//保存左子树根结点
level[top]=n+3;
flag[top]=1;
}
// printf("level[top]=%d\n",level[top]);
}
}
}

main()
{
BinNode *T; //根结点的指针
T=creat(); //建二叉树
printf("\n用缩进表示二叉树的层次(如ppt62所示):\n");
DisplayBinTree(T);
getch();
}

Ⅶ 数据结构c二叉树的算法

额 我来讲讲吧：
第一个问题 你问应该用何种方式来存储，这个问题纠结了，什么叫应该用什么方式存储，当然是都可以啦两种方式~~不过你的意思可能是哪种方式最好，如果就是进行那两种操作的话，是顺序存储方式比较好（你应该知道顺序和链式两种吧）；其实二叉树是很少用顺序方式存储的。但是由于你已经说了你是完全二叉树，那么就可以考虑顺序方式存储了；书序二叉树每个节点你可以编号，直接运算序号就可以找到父节点和两个子节点了。
第二个问题 用C++写了 就采用链式结构吧 每个节点内有lchild rchild指针分别指向左右两孩子结点;结点类型就假定Node吧:
void exchange (Node * node){
exchange(node->lchild);
exchange(node->rchild)；
Node * n;
n=node->lchild;
node->lchild=node->rchild;
node->rchild=n;
}//递归方式实现的函数
exchange(bt);
非递归算法就需要借助队列了 代码较长 不想打了；队列就是实现按层次操作每个节点；操作玩的结点一次出队，出队的同时他们的孩子一次入队，最后没有结点入队出队就算法结束了；一般都是深度优先的递归算法来使用树形结构，很少有按层次结构非递归算法的，树形结构发明出来就是让你深度搜索用的

Ⅷ c++二叉树求双亲算法问题

1、以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。
#define M 10
typedef int DataType;/*元素的数据类型*/
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BitTNode,*BiTree;
int front=0,rear=0;
BitTNode *que[10];
BitTNode *creat()
{BitTNode *t;
DataType x;
scanf("%d",&x);
if(x==0) t=NULL;
else{ t=(BitTNode *)malloc(sizeof(BitTNode));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return(t);
}/*creat*/

/* 前序遍历二叉树t */
void preorder(BiTree t)
{ if(t!=NULL)
{ printf("%4d",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}

/* 中序遍历二叉树t */
void inorder(BiTree t)
{ if(t!=NULL)
{ inorder(t->lchild);
printf("%4d",t->data);
inorder(t->rchild);
}
}

/* 后序遍历二叉树t */
void postorder(BiTree t)
{ if(t!=NULL)
{ postorder(t->lchild);
postorder(t->rchild);
printf("%4d",t->data);
}
}

void enqueue(BitTNode *t)
{if (front!=(rear+1)%M)
{ rear=(rear+1)%M;
que[rear]=t;
}
}/*enqueue*/

BitTNode * delqueue()
{ if(front==rear)return NULL;
{ front=(front+1)%M;
return (que[front]);
}
}/*delqueue*/

/* 按层次遍历二叉树t */
void levorder(BiTree t)
{ BitTNode *p;
if(t!=NULL)
{ enqueue(t);
while (front!=rear)
{ p=delqueue();
printf("%4d",p->data);
if(p->lchild!=NULL) enqueue(p->lchild);
if(p->rchild!=NULL) enqueue(p->rchild);
}
}
}/* levorder */
main()
{BitTNode *root;
root=creat();
printf("\n按先序遍历次序生成的二叉树");
printf("\n前序遍历二叉树");
preorder(root);
printf("\n中序遍历二叉树");
inorder(root);
printf("\n后序遍历二叉树");
postorder(root);
printf("\n层次顺序遍历二叉树");
levorder(root);
}

2、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
#include <stdio.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
} BTree;
BTree * createbt( )
{ BTree *q;
struct node1 *s[30];
int j,i,x;
printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");
printf("i,x = ");
scanf("%d,%c",&i,&x);
while(i != 0 && x != '$')
{ q = (BTree*)malloc(sizeof(BTree)); /*建立一个新结点q*/
q->data = x; q->left = NULL; q->right = NULL;
s[i] = q; /*q新结点地址存入s指针数组中*/
if(i != 1) /*i = 1，对应的结点是根结点*/
{ j = i / 2; /*求双亲结点的编号j*/
if(i % 2 == 0)
s[j]->left = q; /*q结点编号为偶数则挂在双亲结点j的左边*/
else
s[j]->right = q; /*q结点编号为奇数则挂在双亲结点j的右边*/
}
printf("i,x = ");
scanf("%d,%c",&i,&x);
}
return s[1]; /*返回根结点地址*/
}

void preorder(BTree *BT)
/* 前序遍历二叉树t */
{ if(BT!=NULL)
{ printf("%4c", BT ->data);
preorder(BT ->left);
preorder(BT ->right);
}
}

int BTreeDepth(BTree *BT)
{
int leftdep,rightdep;
if (BT==NULL)
return(0);
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if (leftdep>rightdep)
return(leftdep+1);
else
return(rightdep+1);
}
}

int nodecount(BTree *BT)
{
if (BT==NULL)
return(0);
else
return(nodecount(BT->left)+nodecount(BT->right)+1);
}
int leafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(1);
else
return(leafcount(BT->left)+leafcount(BT->right));
}

int notleafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(0);
else
return(notleafcount(BT->left)+notleafcount(BT->right)+1);
}

int onesoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if ((BT->left==NULL && BT->right!=NULL) ||
(BT->left!=NULL && BT->right==NULL))
return(onesoncount(BT->left)+onesoncount(BT->right)+1);
else
return(onesoncount(BT->left)+onesoncount(BT->right));
}

int twosoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL || BT->right==NULL)
return(twosoncount(BT->left)+twosoncount(BT->right));
else if (BT->left!=NULL && BT->right!=NULL)
return(twosoncount(BT->left)+twosoncount(BT->right)+1);
}

main()
{
BTree *B;
B=creatree();
printf("\n按先序遍历次序生成的二叉树");
preorder(B);
printf("\n二叉树深度:%d\n",BTreeDepth(B));
printf("总结点个数:%d\n",nodecount(B));
printf("叶子结点个数:%d\n",leafcount(B));
printf("非叶子结点个数:%d\n",notleafcount(B));
printf("具有双孩子结点个数:%d\n",twosoncount(B));
printf("具有单孩子结点个数:%d\n",onesoncount(B));
}

Ⅸ C++数据与结构，二叉树递归找双亲算法

可以在中序遍历的基础上，加几条指令.n表示层，初始值为0
下列算法是递归嵌套。
1、n++，遍历当前节点的左子树
2、n--，访问当前节点，如果节点的data==x，那么(意味着找到节点了)打印节点层数
3、n++，遍历当前节点的右子树
递归结束后，如果没有找到X节点不要忘了，打印一下没有找到。

Ⅹ C语言二叉树结点找双亲！

这个在构建数据结构的时候加个父亲节点
typedef struct BiTNode
{
struct BiTNode *lchild,*rchild,*parent;
……
}*BiTree
然后在操作的时候用parent记住上一个节点就可以了。