C语言数据结构-树和二叉树-路径-假设二叉树采用二叉链表方式存储， root指向根结点，node 指向二叉树中的一个结点，编写函数 path，计算root到 node 之间的路径

谁践踏了优雅 2023-01-13 04:19 102阅读 0赞

# 路径 #

假设二叉树采用二叉链表方式存储， 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

在提示中，树用缩进的形式展示，如二叉树 ![180e1befda403491986457a3916d9b0d.png][]，其缩进形式为：![a56c676ea105bf04c0718d620bdd9048.png][]。

**提供代码**

#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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1][]

[180e1befda403491986457a3916d9b0d.png]: https://img-blog.csdnimg.cn/img_convert/180e1befda403491986457a3916d9b0d.png
[a56c676ea105bf04c0718d620bdd9048.png]: /images/20221022/a52a7d16ebb342aea74d6c11befa34da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221022/b574aa2d52ea4d94a44345e777c39817.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1]: /images/20221022/d677201caa6341258b6749bf0630645a.png