路径

假设二叉树采用二叉链表方式存储， root指向根结点，node 指向二叉树中的一个结点，编写函数 path，计算root到 node 之间的路径，（该路径包括root结点和 node 结点）。path 函数声明如下：

bool path(BiTNode* root, BiTNode* node, Stack* s);

其中，root指向二叉树的根结点，node指向二叉树中的另一结点，s 为已经初始化好的栈，该栈用来保存函数所计算的路径，如正确找出路径，则函数返回 true，此时root在栈底，node在栈顶；如未找到，则函数返回 false, 二叉树的相关定义如下：

typedef int DataType;

typedef struct Node{
    DataType data;
    struct Node* left;
    struct Node* right;
}BiTNode, *BiTree;

栈的相关定义及操作如下：

#define Stack_Size 50
typedef BiTNode* ElemType;
typedef struct{
    ElemType elem[Stack_Size];
    int top;
}Stack;

void init_stack(Stack *S); // 初始化栈
bool push(Stack* S, ElemType x); //x 入栈
bool pop(Stack* S, ElemType *px); //出栈，元素保存到px所指的单元，函数返回true,栈为空时返回 false
bool top(Stack* S, ElemType *px); //获取栈顶元素，将其保存到px所指的单元，函数返回true，栈满时返回 false
bool is_empty(Stack* S);  // 栈为空时返回 true，否则返回 false

在提示中，树用缩进的形式展示，如二叉树 ，其缩进形式为：。

提供代码

#include <stdlib.h>
#include <stdio.h>
#include "bitree.h" //请不要删除，否则检查不通过

bool path(BiTNode* root, BiTNode* node, Stack* s){


}

参考代码

bool path(BiTNode* root, BiTNode* node, Stack* s)
{
    BiTree T = root, p=NULL;
    if (T == NULL || node == NULL || !is_empty(s))
        return false;
    while (T || !is_empty(s)) {
        while (T) {
            push(s, T);
            if (T == node)
                return true;
            T = T->left;
        }
        top(s, &T);
        if (!T->right || T->right == p) {
            p = T;
            pop(s, &T);
            T = NULL;
        } else
            T = T->right;
    }
    return false;
}

完整代码与解析

#include <stdio.h>
#include <malloc.h>
#include <conio.h>
 
typedef char DataType;
 
typedef struct Node
{
	DataType data;
	struct Node* LChild;
	struct Node* RChild;
}BiTNode, * BiTree;
 
 
void CreateBiTree(BiTree* bt)
{
	char ch;
	ch = getchar();
	if (ch == '.') *bt = NULL;
	else
	{
		*bt = (BiTree)malloc(sizeof(BiTNode)); //生成一个新结点
		(*bt)->data = ch;
		CreateBiTree(&((*bt)->LChild)); //生成左子树
		CreateBiTree(&((*bt)->RChild)); //生成右子树
	}
}
 
#define  NUM  20
 
void path(BiTree root, BiTNode* r)
{
	BiTNode* p, * q;
	int i, find = 0, top = 0;
	BiTNode* s[NUM];
	q = NULL;   /* 用q保存刚遍历过的结点 */
	p = root;
	while ((p != NULL || top != 0) && !find)
	{
		while (p != NULL)
		{
			top++;
			s[top] = p;
			p = p->LChild;
		}                /* 遍历左子树 */
		if (top > 0)
		{
			p = s[top];       /* 根结点 */
			if (p->RChild == NULL || p->RChild == q)
			{
				if (p == r)   /*找到r所指结点，则显示从根结点到r所指结点之间的路径*/
				{
					for (i = 1; i <= top; i++)
						printf("%c  ", s[i]->data);
					find = 1;
				}
				else
				{
					q = p;        /* 用q保存刚遍历过的结点 */
					top--;
					p = NULL;    /* 跳过前面左遍历，继续退栈 */
				}
			}
			else
				p = p->RChild;     /* 遍历右子树 */
		}
	}
}
/*
void path(BiTree root, char r)
{
	BiTNode  *p, *q;
	int i, find=0, top=0;
	BiTNode *s[NUM];
	q = NULL;   / * 用q保存刚遍历过的结点 * /
	p = root;
	while ( (p != NULL || top != 0) && !find )
	{
		while ( p != NULL )
		{
			top++;
			s[top] = p;
			p = p->LChild;
		}                / * 遍历左子树 * /
		if (top > 0)
		{
			p=s[top];       / * 根结点 * /
			if ( p->RChild == NULL || p->RChild == q )
			{
				if(p->data == r)   / *找到r所指结点，则显示从根结点到r所指结点之间的路径* /
				{
					for(i=1;i<=top;i++)
						printf("%c  ",s[i]->data);
					find=1;
				}
				else
				{
					q = p;        / * 用q保存刚遍历过的结点 * /
					top--;
					p = NULL;    / * 跳过前面左遍历，继续退栈 * /
				}
			}
			else
				p = p->RChild;     / * 遍历右子树 * /
		}
	}
}*/
 
 
void main()
{
	BiTree T;
	BiTNode* p;
	//	char c;
	printf("按扩展先序遍历序列建立二叉树T，请输入序列:\n");
	CreateBiTree(&T);
	/*
		printf("请输入一个字符:");
		fflush(stdin);
		scanf("%c",&c);*/
		//	path(T,c);
	p = T->LChild->RChild->LChild;
	path(T, p);
	getch();
}

解析：求从根结点到某结点间的路径

按扩展先序遍历序列建立二叉树T，请输入序列:
124..57..8..3.6..
1  2  5  7