求二叉樹某一個結點的祖先序列？

// 創(chuàng)建二叉樹是按照"二叉排序樹"的原則,例如: // 輸入序列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的右分支, // 如此類推,創(chuàng)建完整的二叉樹. // 查找給定節(jié)點的雙親結點,用[棧],是非遞歸法. // // 示例演示 // 請輸入結點的個數: 9 // 請連續(xù)輸入9個數據(用空格隔開): 20 15 10 12 18 25 30 16 17 // 創(chuàng)建二叉樹后 // 先序遍歷序列: 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; //插入節(jié)點(非遞歸) 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() //創(chuàng)建二叉樹(非遞歸) { BTree root=NULL; int len; int num; int i; printf("請輸入結點的個數: "); scanf("%d",&len); printf("請連續(xù)輸入%d個數據(用空格隔開): ",len); for(i=0;ibt=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; //當前二叉樹的節(jié)點 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();//創(chuàng)建二叉樹(非遞歸) printf("\n創(chuàng)建二叉樹后"); 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,可以退出循環(huán) { break; } findParent(root,x); //查找雙親結點 } printf("\n"); return 0; }