Question

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

Answer 1

// 创建二叉树是按照"二叉排序树"的原则,例如:
// 输入序列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<stdio.h>
#include<stdlib.h>

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;i<len;i++)
    {
        scanf("%d",&num);
        root=insertNode(root,num);
    }
    return root;
}

//检查[栈]是否是空
int isStackEmpty(stack_link stack)
{
	if(stack == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

//入栈
stack_link push(stack_link stack,BTree bt)
{
	stack_link new_node;

	new_node=(stack_link)malloc(sizeof(stack_list));
	if(!new_node)
	{
		return NULL;
	}
	new_node->bt=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;
}

Answer 2

我会提前帮你准备.