求二叉树某一个结点的祖先序列_java

资料来源：网络整理时间：2023/3/5 20:24:23 共计：3585 浏览

求二叉树某一个结点的祖先序列？

// 创建二叉树是按照"二叉排序树"的原则,例如: // 输入序列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的右分支, // 如此类推,创建完整的二叉树. // 查找给定节点的双亲结点,用[栈],是非递归法. // // 示例演示 // 请输入结点的个数: 9 // 请连续输入9个数据(用空格隔开): 20 15 10 12 18 25 30 16 17 // 创建二叉树后 // 先序遍历序列: 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; //插入节点(非递归) 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() //创建二叉树(非递归) { BTree root=NULL; int len; int num; int i; printf("请输入结点的个数: "); scanf("%d",&len); printf("请连续输入%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; //当前二叉树的节点 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();//创建二叉树(非递归) printf("\n创建二叉树后"); 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,可以退出循环 { break; } findParent(root,x); //查找双亲结点 } printf("\n"); return 0; }

版权说明：
本网站凡注明“广州京杭原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。

·上一条：怎么在网页上截图并发给别人_java | ·下一条：在JAVA语言中switch循环语句把default写到前面并且没有break_java