找二叉樹雙親結點演算法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記住上一個節點就可以了。