精华内容
下载资源
问答
  • title: 广义表树的兄弟孩子表示法 date: 2020-11-17 15:55:55 tags: 兄弟孩子广义表 二叉树 categories: 数据结构 用兄弟孩子广义表来表示二叉树 对比 二叉树转化来的兄弟孩子广义表和普通的兄弟孩子广义表并...

    title: 广义表之树的兄弟孩子表示法
    date: 2020-11-17 15:55:55
    tags:

    • 兄弟孩子广义表
    • 二叉树
      categories: 数据结构

    用兄弟孩子广义表来表示二叉树

    对比

    二叉树转化来的兄弟孩子广义表和普通的兄弟孩子广义表并不相同

    • 二叉树转换成的兄弟孩子广义表没有明确的一块内存结构来直接表示它是叶子节点还是双亲结点,而是通过 指针 tp 来隐式地表示,tp 指向空,表示它没有孩子节点,否则,有孩子结点

    • 普通的兄弟孩子广义表则是通过 tag = 0 或 1 来表示它是否还有孩子结点

    • 普通的广义表如果转换成树,那么转换成的是只有在叶子结点中存数据的树,根结点,和树中间的双亲节点可以理解成一级一级的括号。

    • 如果还要说不同的话,那就是二叉树中一个双亲结点最多有2 个孩子结点, 而普通的广义表则不同

    • 在求深度的时候,刚开始要设一个 max = 0来表示下一层的深度的最大值, 树转换来的兄弟孩子广义表,下一层只要有结点,那么下一层的深度必为 1 ,直接return max + 1即可,但是普通的广义表,下一层有结点的时候并不能代表下一层的深度就是 1, 因为如果下一层都是 tag为 0 的结点,那么下一层的深度就都是 0 ,不可return max + 1, 需要return maxreturn max + 1return max 的情况需要 分开讨论

    • 关于两种不同的兄弟孩子广义表求深度时候具体细节的不同,我会在下一期中具体分析

    总结

    总结一下不同的树 转换成表

    • 二叉树 转换成兄弟孩子广义表 (特殊的表,这种表没有tag 的 0 或 1 来表示它是原子结点还是表结点)
    • 普通树 转换成兄弟孩子广义表(特殊的表, 特殊同上)
    • 每一个双亲结点最多有两个孩子结点的兄弟孩子广义表 转换成树(特殊的二叉树, 只有叶子结点存数据)
    • 一个双亲结点可有任意个孩子结点的兄弟孩子广义表 转换成树(特殊的树,只有叶子结点存数据)

    代码功能

    • 根据输入的一串字符(字符按树的每一层的结点内容输入),自动建立用兄弟孩子广义表表示的二叉树
    • 先序打印树
    • 转换成兄弟孩子广义表后,在兄弟孩子广义表的基础上求树的深度

    代码附上

    // 求树的深度
    
    // 兄弟孩子存储结构的树的深度 其实和广义表的兄弟孩子存储结构求深度没有什么区别
    // 只不过标识符不一样了, 广义表的标识符是 tag , 而现在 标识符通过指向左孩子的指针来
    // 隐式表示 , 若指针为空,那么表示这个是一个 叶子节点(即广义表中的原子) 若不为空,则它还有孩子结点
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX 100
    
    typedef char Elemtype;
    typedef struct node
    {
        Elemtype data;
        // 指向本结点左孩子结点的指针,和指向本结点下一个兄弟的指针
        struct node *hp, *tp;
    } Node, *Tree;
    
    // 初始化二叉树
    void Init(Tree *);
    
    // 通过输入一串字符来初始化二叉树
    void Creat(Tree, char *, int);
    void Creat2(Tree, char *, int);
    // 输入一串字符并返回
    char *Input();
    
    // 遍历二叉树
    void PrintTree(Tree);
    
    // 求深度
    int GetDepth(Tree);
    
    int main(void)
    {
        Tree tree;
        Init(&tree);
        char *str = Input();
        Creat(tree, str, 0);
        PrintTree(tree->hp);
        printf("\n");
        int depth = GetDepth(tree->hp);
        printf("%d\n",depth);
        return 0;
    }
    // 初始化一个带头结点的二叉树
    void Init(Tree *pTree)
    {
        *pTree = (Node *)malloc(sizeof(Node));
        (*pTree)->data = '0';
        (*pTree)->hp = NULL;
        (*pTree)->tp = NULL;
    }
    char *Input()
    {
        char *s = (char *)malloc(sizeof(char) * MAX);
        memset(s, '0', sizeof(char) * MAX);
        gets(s);
        int len = strlen(s);
        // 将输入的字符串转化成下标从1开始
        for (int i = strlen(s); i > 0; i--)
            s[i] = s[i - 1];
        return s;
    }
    // 创建一个二叉树
    // 刚开始传的参数是  头指针, 字符数组, 0
    void Creat(Tree tree, char *str, int i)
    {
        // 这个函数的利用价值:
        // 当 i == 0 时,由于传进来的是头指针
        // 并且头指针指向的是头结点,和别的情况不一样
        // 所以需要在递归函数外面单独执行一次
    
        // 如果根节点就是 '0' 也就代表着这棵树是空的
        if (str[1] == '0')
            return;
    
        Node *p = (Node *)malloc(sizeof(Node));
        p->data = str[1];
        tree->hp = p;
        Creat2(p, str, 1);
    }
    void Creat2(Tree tree, char *str, int i)
    {
        tree->data = str[i];
        // 先解决这个结点的hp
        if (str[i * 2] == '0' && str[i * 2 + 1] == '0')
            tree->hp = NULL;
        else
        {
            Node *p = (Node *)malloc(sizeof(Node));
            tree->hp = p;
            Creat2(p, str, i * 2);
        }
        // 然后解决这个结点的 tp
        if (str[i + 1] == '0' || i % 2 == 1)
            tree->tp = NULL;
        else
        {
            Node *q = (Node *)malloc(sizeof(Node));
            tree->tp = q;
            Creat2(q, str, i + 1);
        }
    }
    
    // 遍历并打印二叉树
    // 传进来的是头结点中存的hp
    // 即指向根结点的指针,而不是头指针
    void PrintTree(Tree tree)
    {
        if (tree == NULL)
            printf("二叉树为空\n");
        printf("%c ", tree->data);
        if (tree->hp)
            PrintTree(tree->hp);
        if (tree->tp)
            PrintTree(tree->tp);
    }
    
    // 求深度
    int GetDepth(Node *T)
    {
    	if (!T)
    		return 0;
    	int max = 0;
    	for (Node *temp = T; temp; temp = temp->tp)
    	{
    		int depth = GetDepth(temp->hp);
    		if (max < depth)
    			max = depth;
    	}
    	return max + 1;
    }
    

    求深度算法(二)

    横向纵向都用到了递归,上面那个方法只有纵向用到了递归,横向依靠的是for循环

    // 求深度算法 2 
    int getDep(BitTree T)
    {
        // 空树返回 0
        if (!T)	return 0;
        // 求当前结点的深度 - 1(既然当前结点存在,其深度必 >= 1)
        int dep1 = getDep(T->down);
        // 求当前结点的兄弟结点的深度
        // 这个语句会在第一次执行的时候不断递归,所以当递归回来到第一次
        // 执行的函数中的时候, dep2已经是第二个结点以及第二个结点之后的所有结点中
        // 深度的最大值, 看似这个递归只比较了两个结点,实则该递归比较了一级中的所有结点
        // 省去了遍历当前层所有结点的操作
        // 横向纵向同时递归
        int dep2 = getDep(T->right);
        // 比较,若当前结点深度 大于 下一个兄弟结点,就返回当前结点深度
        // 否则 返回下一个兄弟结点的深度
        if (dep1 + 1 > dep2)
    		return dep1 + 1;
    	return dep2;
    }
    
    展开全文
  • 题目来源:严蔚敏《数据结构》C语言...试写以递归算法,以6.73题给定的树的广义表表示法的字符序列形式输出以孩子链表表示的树。 【测试数据】A(B(E,F),C(G),D) 【答案】 /*------------------------- |6.75...

    题目来源:严蔚敏《数据结构》C语言版本习题册 6.75、6.76

    【题目】6.75
    试写以递归算法,由6.73题定义的广义表表示法的字符序列,构造树的孩子链表。

    【题目】6.76
    试写以递归算法,以6.73题给定的树的广义表表示法的字符序列形式输出以孩子链表表示的树。

    【测试数据】A(B(E,F),C(G),D)
    【答案】

    /*-------------------------
     |6.75 用广义表构造树     |
     -------------------------*/
    // @Quesion:有一些格式检测不了"A(" "A()" "A)("
    Status CreateCTreeByGList(CTree *pT, int parent) {
    	// 创建新结点newNode --> 放在下标为pT->n
    	// 该结点的爸爸为parent
    	char c;
    	CNode *p, *q;
    	int newNode;
    
    	//创建newNode结点
    	newNode = pT->n; //新结点的下标
    	for (c=getchar(); c!='\n'; c=getchar() ) {
    		if (c>='A' && c<='Z') { // 结点信息
    			pT->nodes[newNode].data = c; //给结点赋值
    			pT->nodes[newNode].firstchild = NULL; //给结点赋值
    			pT->n++; //结点数+1
    
    			//newNode有爸爸,即parent
    			if (parent!=-1) {
    				//创建孩子结点
    				p = (CNode *)malloc(sizeof(CNode));if (!p) exit(OVERFLOW);
    				p->index = newNode;
    				p->next = NULL;
    				//儿子父亲相认
    				if (pT->nodes[parent].firstchild==NULL) {
    					pT->nodes[parent].firstchild = p;
    				} else {
    					for (q=pT->nodes[parent].firstchild; q->next; q=q->next) ;
    					q->next = p;
    				}
    			}
    		} else if (c=='(') { //是newNode的孩子
    			CreateCTreeByGList(pT, newNode); //开始创建newNode的孩子
    		} else if (c==',') { //是newNode的兄弟,即parent的下一个孩子
    			CreateCTreeByGList(pT, parent); //parent的下一个孩子
    			return OK; //newNode结点构造完成(自己创建了、孩子创建了、兄弟创建了)
    		} else if (c==')') { //parent构造完毕
    			return OK; 
    		} else {
    			return ERROR; //格式错误
    		}
    	}
    	return OK;
    }
    
    /*-------------------------
     |6.76 以广义表的形式输出 |
     -------------------------*/
    Status PrintAsGList(CTree T,int parent) {
    	CNode *p;
    
    	if (T.n<=0) return ERROR; 
    
    	visit(T.nodes[parent].data);
    	if (T.nodes[parent].firstchild) {
    		printf("(");
    		for (p=T.nodes[parent].firstchild; p; p=p->next) {
    			PrintAsGList(T, p->index);
    			if (p->next) printf(",");
    		}
    		printf(")");
    	}
    
    	return OK;
    }
    

    【完整代码】

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #ifndef BASE
    #define BASE
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW -2
    typedef int Status;
    typedef int bool;
    #endif
    
    #define TElemType char
    void visit(TElemType e) {
    	printf("%c", e);
    }
    #define MAX_TREE_SIZE 100
    #define maxSize 50
    
    typedef struct CNode{
    	int index; //这个孩子的结点号(注意:在严书中变量名为child)
    	struct CNode *next; //下一个孩子结点
    }CNode, *ChildPtr; //孩子结点结构(在严书中名为CTNode)
    typedef struct{
    	TElemType data;
    	CNode* firstchild;
    }PNode; //双亲结点结构(在严书中,结构名为CTBox)
    typedef struct{
    	PNode nodes[MAX_TREE_SIZE];
    	int n,r; //结点数 和 根结点的位置
    }CTree; //树结构
    
    // 先根遍历
    void SubPreOrder(CTree T, int index) {
    	CNode *child;
    	visit(T.nodes[index].data);
    	for (child=T.nodes[index].firstchild; child; child=child->next)
    		SubPreOrder(T, child->index);
    }
    void PreOrder(CTree T) {
    	SubPreOrder(T, T.r);
    }
    
    
    /*-------------------------
     |6.63 求树的深度         |
     -------------------------*/
    int SubTreeDepth(CTree T, int index) { //序号为index的子树深度
    	int max=-1; //孩子的最大深度
    	int sd; //孩子的深度
    	CNode *p;
    	if (!T.nodes[index].firstchild) return 1; //没有孩子,深度为1
    	for (p=T.nodes[index].firstchild; p; p=p->next) { //遍历该结点的所有孩子
    		sd = SubTreeDepth(T, p->index); //求孩子的深度
    		if (max<sd) max=sd;
    	}
    	return max+1; //孩子的最大深度+1
    }
    int TreeDepth(CTree T) { 
    	return SubTreeDepth(T, T.r);
    }
    
    /*-------------------------
     |6.72 将树打印成树状     |
     -------------------------*/
    void PrintAsTree(CTree T, int index, int i) {
    	/*思路
    		1. 观察题目输出的序列ABEFCGD
    		2. 此为树的先根遍历–>对应为二叉树存储的先序遍历
    		3. 前面的空格是该结点所在的层数
    	*/
    	CNode *p;
    	int cnt;
    
    	//输出空格
    	for (cnt=1; cnt<i; cnt++) printf(" ");
    	//输出元素
    	visit(T.nodes[index].data);printf("\n");
    	//遍历它的孩子
    	for(p=T.nodes[index].firstchild; p; p=p->next)
    		PrintAsTree(T, p->index, i+1);
    }
    
    // 树的层序次序+每个结点的度 --> 创建CTree
    Status CreateCTreeByLevelDegree(CTree *pT,char *levelstr, int *degree) {
    	CNode *c,*sibling;
    	int parent;
    	int i,cnt;
    	//创建结点
    	for (i=0; i<strlen(levelstr); ++i) {
    		//赋值
    		pT->nodes[i].data = levelstr[i];
    		pT->nodes[i].firstchild = NULL;
    	}
    	pT->n=strlen(levelstr); //个数
    	pT->r=0; //根结点
    
    	//为孩子找爸爸
    	parent=0; //当前的爸爸
    	i=1; //遍历孩子
    	cnt=0; //已经为parent找到了cnt个孩子
    	while (i<strlen(levelstr)) {
    		if (degree[parent]==0 || cnt==degree[parent]) { //parent没有孩子 || parent的孩子已经全部找到
    			cnt=0;
    			parent++;
    			continue;
    		}
    		cnt++; //为parent找到了一个孩子
    		//创建孩子结点
    		c = (CNode *)malloc(sizeof(CNode)); if (!c) exit(OVERFLOW);
    		c->index = i; //孩子的编号
    		c->next = NULL;
    		if (cnt==1) { //第一个孩子
    			pT->nodes[parent].firstchild = c;
    		} else { //不是第一个孩子
    			for(sibling=pT->nodes[parent].firstchild; sibling->next; sibling=sibling->next) ;
    			sibling->next = c;
    		}
    
    		i++;
    	}
    	return TRUE;
    }
    
    /*-------------------------
     |6.75 用广义表构造树     |
     -------------------------*/
    // @Quesion:有一些格式检测不了"A(" "A()" "A)("
    Status CreateCTreeByGList(CTree *pT, int parent) {
    	// 创建新结点newNode --> 放在下标为pT->n
    	// 该结点的爸爸为parent
    	char c;
    	CNode *p, *q;
    	int newNode;
    
    	//创建newNode结点
    	newNode = pT->n; //新结点的下标
    	for (c=getchar(); c!='\n'; c=getchar() ) {
    		if (c>='A' && c<='Z') { // 结点信息
    			pT->nodes[newNode].data = c; //给结点赋值
    			pT->nodes[newNode].firstchild = NULL; //给结点赋值
    			pT->n++; //结点数+1
    
    			//newNode有爸爸,即parent
    			if (parent!=-1) {
    				//创建孩子结点
    				p = (CNode *)malloc(sizeof(CNode));if (!p) exit(OVERFLOW);
    				p->index = newNode;
    				p->next = NULL;
    				//儿子父亲相认
    				if (pT->nodes[parent].firstchild==NULL) {
    					pT->nodes[parent].firstchild = p;
    				} else {
    					for (q=pT->nodes[parent].firstchild; q->next; q=q->next) ;
    					q->next = p;
    				}
    			}
    		} else if (c=='(') { //是newNode的孩子
    			CreateCTreeByGList(pT, newNode); //开始创建newNode的孩子
    		} else if (c==',') { //是newNode的兄弟,即parent的下一个孩子
    			CreateCTreeByGList(pT, parent); //parent的下一个孩子
    			return OK; //newNode结点构造完成(自己创建了、孩子创建了、兄弟创建了)
    		} else if (c==')') { //parent构造完毕
    			return OK; 
    		} else {
    			return ERROR; //格式错误
    		}
    	}
    	return OK;
    }
    
    /*-------------------------
     |6.76 以广义表的形式输出 |
     -------------------------*/
    Status PrintAsGList(CTree T,int parent) {
    	CNode *p;
    
    	if (T.n<=0) return ERROR; 
    
    	visit(T.nodes[parent].data);
    	if (T.nodes[parent].firstchild) {
    		printf("(");
    		for (p=T.nodes[parent].firstchild; p; p=p->next) {
    			PrintAsGList(T, p->index);
    			if (p->next) printf(",");
    		}
    		printf(")");
    	}
    
    	return OK;
    }
    
    
    int main() {
    /*6.75测试数据
    A(B(E,F),C(G),D)
    A
    A(B)
    A(B,C)
    A(B,C(D,E))
    */
    	CTree T;
    	T.n=0;T.r=0;
    	CreateCTreeByGList(&T, -1); //6.75
    	PrintAsGList(T, T.r); //6.76
    
    
    	return 0;
    }
    
    展开全文
  • 试写一递归算法,以6.73题给定的树的广义表表示法的字符序列形式输出以孩子-兄弟链表表示的树 【答案】 /*----------------------------------------- |6.74 以广义表的形式输出 | ------------------------...

    题目来源:严蔚敏《数据结构》C语言版本习题册 6.74

    【题目】6.74
    试写一递归算法,以6.73题给定的树的广义表表示法的字符序列形式输出以孩子-兄弟链表表示的树

    【答案】

    /*-----------------------------------------
     |6.74 以广义表的形式输出                 |
     -----------------------------------------*/
    void PrintAsGList(CSTree T) {
    	CSNode *child;
    	visit(T->data);
    	if (T->firstchild) { //有孩子
    		printf("(");
    		for (child=T->firstchild; child->nextsibling; child=child->nextsibling) {
    			PrintAsGList(child);
    			printf(",");
    		}
    		PrintAsGList(child);
    		printf(")");
    	}
    }
    

    【完整答案】

    /*-------------------
     |树-孩子兄弟表达法 |
     -------------------*/
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #ifndef BASE
    #define BASE
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW -2
    typedef int Status;
    typedef int bool;
    #endif
    
    #define TElemType char
    void visit(TElemType e) {
    	printf("%c", e);
    }
    typedef struct CSNode{
    	TElemType data;
    	struct CSNode *firstchild, *nextsibling;
    }CSNode, *CSTree;
    
    
    
    /*-------------------
     |6.59 输出T的所有边 |
     -------------------*/
    void TreePrintEdge(CSTree T) {
    	CSNode *p;
    	for (p=T->firstchild; p; p=p->nextsibling) {
    		printf("(%c,%c)\n", T->data, p->data); //输出T的孩子
    		TreePrintEdge(p); //输出p的孩子
    	}
    }
    
    /*-------------------------
     |6.60 统计叶子结点的个数 |
     -------------------------*/
    int TreeLeafCnt(CSTree T) {
    	// 树的叶子结点-->没有孩子
    	int ret=0;
    	CSNode *p;
    	if (!T) return 0;
    	else if (!T->firstchild) return 1;
    	else {
    		for (p=T->firstchild; p; p=p->nextsibling) ret += TreeLeafCnt(p);
    		return ret;
    	}
    }
    
    
    /*-------------------------
     |6.61 求树的度           |
     -------------------------*/
    int TreeDegree(CSTree T) {
    	// 最大的孩子数
    	int max=-1;
    	int cnt=0;
    	CSNode *child;
    	if (!T) return -1; //空树
    	else if (!T->firstchild) return 0; //只有一个根结点,度为0
    	else {
    		for (cnt=0,child=T->firstchild; child; child=child->nextsibling) cnt++; //求自己的度
    		max = cnt; //当前的最大值
    		for (child=T->firstchild; child; child=child->nextsibling) {
    			cnt = TreeDegree(child);
    			if (cnt>max) max=cnt;
    		}
    		return max;
    	}
    }
    
    /*-------------------------
     |6.62 求树的深度         |
     -------------------------*/
    int TreeDepth(CSTree T) {
    	int h1,h2;
    	if (!T) return 0;
    	else {
    		h1 = TreeDepth(T->firstchild)+1; //T孩子的深度+1
    		h2 = TreeDepth(T->nextsibling); //T兄弟的深度
    		return h1>h2 ? h1 : h2;
    	}
    }
    
    /*---------------------------------
     |6.66 双亲表示法-->孩子兄弟表达式|
     ---------------------------------*/
    #define MAX_TREE_SIZE 50
    
    typedef struct PTNode{
    	TElemType data;
    	int parent; //双亲的位置域
    }PTNode;
    typedef struct{
    	PTNode nodes[MAX_TREE_SIZE];
    	int r,n;
    }PTree;
    CSTree CreateCSTreeByPTree(PTree T) {
    	CSNode *tmp[MAX_TREE_SIZE]; //创建一个辅助的数组,仿照PTree结点的位置存放
    	CSNode *p, *q;
    	int i,parent;
    	
    	if (T.n<=0) return NULL;
    	for (i=0; i<T.n; i++) { //双亲表按层序存储
    		//创建新结点
    		p = (CSNode *)malloc(sizeof(CSNode)); if(!p) exit(OVERFLOW);
    		//赋值
    		p->data = T.nodes[i].data;p->firstchild=p->nextsibling=NULL;
    		//连接
    		parent=T.nodes[i].parent; //父亲
    		if (parent!=-1) { //不是根结点
    			if (tmp[parent]->firstchild==NULL) tmp[parent]->firstchild=p; //第一个孩子
    			else { //不是第一个孩子
    				for (q=tmp[parent]->firstchild; q->nextsibling; q=q->nextsibling) ; //找到最后一个孩子
    				q->nextsibling = p; //连接
    			}
    		}
    		tmp[i]=p;
    	}
    	
    	return tmp[0];
    }
    
    /*---------------------------------
     |6.67 二元组(F,C)创建CSTree      |
     ---------------------------------*/
    #define maxSize 50
    Status CreateCSTreeByDuplet(CSTree *pT) {
    	char input[5];
    	CSNode *queue[maxSize];int front,rear;
    	CSNode *p, *q;
    	
    	front=rear=0; //对队列初始化
    	for (scanf("%s", input); input[1]!='^'; scanf("%s", input)) {
    		//创建结点
    		p = (CSNode *)malloc(sizeof(CSNode)); if (!p) exit(OVERFLOW);
    		p->data=input[1];p->firstchild=p->nextsibling=NULL;
    		//入队列
    		queue[rear]=p;rear=(rear+1)%maxSize;
    		//找爸爸
    		if (input[0]=='^') { //根结点-->不需要找爸爸
    			*pT = p; //传出去
    		} else {
    			for (q=queue[front]; q->data!=input[0]; front=(front+1)%maxSize,q=queue[front]) ; //找爸爸
    			//找哥哥
    			if (!q->firstchild) q->firstchild=p; //它是最大的
    			else { //它不是最大的
    				for(q=q->firstchild; q->nextsibling; q=q->nextsibling) ; //找最近的哥哥
    				q->nextsibling = p; //和哥哥牵手
    			}
    		}
    	}
    	return OK;
    }
    
    /*-----------------------------------------
     |6.68 层次序列+每个结点的度-->构造CSTree |
     -----------------------------------------*/
    CSTree CreateCSTreeByLevelDegree(char *levelstr, int *num) {
    	int cnt,i,parent;
    	CSNode *p;
    	CSNode *tmp[maxSize];
    
    	//先创建结点
    	for (i=0; i < strlen(levelstr); ++i) {
    		p = (CSNode *)malloc(sizeof(CSNode)); if (!p) exit(OVERFLOW);
    		p->data = levelstr[i];p->firstchild=p->nextsibling=NULL;
    		tmp[i]=p;
    	}
    	//连接
    	parent=0; //孩子的爸爸
    	cnt=0; //计数器:表示已经找了几个孩子
    	i=1; //遍历结点,为他们找爸爸
    	while (i<strlen(levelstr)) {
    		if (num[parent]==0 || cnt==num[parent]) { //这个父亲没有孩子 || parent的孩子已经找完了
    			cnt=0; //计数器归0
    			parent++; //位移一位
    			continue;
    		}
    		//这个父亲有孩子(i是parent的孩子)
    		cnt++;
    		if (cnt==1) { //i是parent的第一个孩子
    			tmp[parent]->firstchild = tmp[i];
    		} else { //不是第一个孩子
    			tmp[i-1]->nextsibling = tmp[i]; //它是前面的兄弟
    		}
    		
    		i++;
    	}
    	
    	return tmp[0];
    }
    
    /*-----------------------------------------
     |6.71 以树状的形式输出                   |
     -----------------------------------------*/
    void PrintAsTree(CSTree T,int i) {
    	/*思路:
    		1. 观察题目输出的序列ABEFCGD
    		2. 此为树的先根遍历-->对应为二叉树存储的先序遍历
    		3. 前面的空格是该结点所在的层数
    	*/
    	int cnt;
    	if (T) {
    		//输出空格
    		for (cnt=1; cnt<i; cnt++) printf(" ");
    		//输出字符
    		visit(T->data);
    		printf("\n");
    
    		PrintAsTree(T->firstchild, i+1);
    		PrintAsTree(T->nextsibling, i);
    	}
    }
    
    /*-----------------------------------------
     |6.73 用广义表的形式构造                 |
     -----------------------------------------*/
    Status CreateCSTreeByGList(CSTree *pT) {
    	char c;
    
    	while (1) {
    		c = getchar();
    		if (c>='A' && c<='Z') { //根结点
    			*pT = (CSNode *)malloc(sizeof(CSNode)); if (!*pT) exit(OVERFLOW);
    			(*pT)->data = c; (*pT)->firstchild=(*pT)->nextsibling=NULL;
    		} else if (c=='(') { //是我的第一个孩子
    			CreateCSTreeByGList(&(*pT)->firstchild);
    		} else if (c==',') { //是我的兄弟
    			CreateCSTreeByGList(&(*pT)->nextsibling);
    			break; //这里要返回
    		} else
    			break;
    	}
    	return OK;
    }
    
    /*-----------------------------------------
     |6.74 以广义表的形式输出                 |
     -----------------------------------------*/
    void PrintAsGList(CSTree T) {
    	CSNode *child;
    	visit(T->data);
    	if (T->firstchild) { //有孩子
    		printf("(");
    		for (child=T->firstchild; child->nextsibling; child=child->nextsibling) {
    			PrintAsGList(child);
    			printf(",");
    		}
    		PrintAsGList(child);
    		printf(")");
    	}
    }
    
    
    int main() {
    /*6.74测试数据
    A(B(E,F),C(G),D)
    */
    	CSTree CST;
    	CreateCSTreeByGList(&CST); //6.73
    
    	PrintAsGList(CST); //6.74
    
    	return 0;
    }
    
    展开全文
  • 兄弟结点之间互相连接,在同一层,孩子结点在下一层,结构像广义表,45度观看又像二叉树。创建方式类似二叉树层序建立,也需要借助队列结构。 先处理根结点,获取第一个输入字符,保存至根结点中,将该结点入队,...
    创建:

    和二叉树一样结点内部拥有两个指针,不过不是指向左右子树,而是指向孩子结点和兄弟结点。兄弟结点之间互相连接,在同一层,孩子结点在下一层,结构像广义表,45度观看又像二叉树。创建方式类似二叉树的层序建立,也需要借助队列结构。
    先处理根结点,获取第一个输入字符,保存至根结点中,将该结点入队,然后进入循环:
    数据优先存放到某结点的子树中,然后再存放到其兄弟结点中。
    获取队头结点,并让其出队。获取输入字符,将其保存至当前结点的长子结点(第一个孩子结点,即直接与父结点相连的子结点)中,然后长子结点入队,接下来在遇到井号之前,数据会循环保存到长子结点的兄弟结点中(当前结点的所有子结点),且将兄弟结点入队。重复上述过程,直到队列为空。

    //定义结点
    typedef struct mytree
    {
        char data;
        mytree *child=nullptr;
        mytree *brother=nullptr;
    }mytree;
    
    void creat_tree(mytree *&T)
    {
        queue<mytree*> q;
        mytree *p=T;
        char ch;
        cin >> ch;
        if(ch!='#')
        {
            T=new mytree;
            T->data=ch;
            q.push(T);
        }
        while(!q.empty())
        {
            p=q.front();
            q.pop();
            cin >> ch;
            if(ch!='#')
            {
                //先将数据存放到长子中,并将其入队
                p->child=new mytree;
                p->child->data=ch;
                q.push(p->child);
                //p指向该结点的长子,在遇到#之前,接下来的字符都存放在长子的兄弟中
                p=p->child;
                cin >> ch;
                while(ch!='#')
                {
                    p->brother=new mytree;
                    p->brother->data=ch;
                    q.push(p->child);
                    p=p->brother;//指向下一个兄弟
                    cin >> ch;
                }
            }
        }
    }
    
    先根遍历:

    先访问父节点,再递归访问其子结点和兄弟结点。逻辑类似二叉树的先序遍历。

    void PreOrderTraverse(mytree *&T)
    {
        if(T!=nullptr)
        {
           cout << T->data << endl;
           PreOrderTraverse(T->child);
           PreOrderTraverse(T->brother);
        }
    }
    
    后根遍历:

    与先根遍历相反,先递归访问父节点的子结点和兄弟结点,再访问父节点。逻辑类似二叉树的后序遍历。

    void PostOrderTraverse(mytree *&T)
    {
       if(T!=nullptr)
        {
           PostOrderTraverse(T->child);
           PostOrderTraverse(T->brother);
           cout << T->data << endl;
        }
    }
    
    展开全文
  • 1、树的表示方法有哪几种?树的表示方法有以下四种,各用于不同的目的1)直观表示法以倒着的分支树的形式表示。是数据结构中最常用的树的描述方法。...4)广义表表示法将根作为由子树森林组成的表的名...
  • 广义表表示法:不常用。 左孩子右兄弟表示法:可以将多叉转化为二叉树一种表示方法,而二叉树更适合计算机表示。(也就是说一般遇到多叉,转化成二叉树) 二叉树及性质 略 二叉树存储结构 顺序存储 用...
  • 树的广义表形式有两种:括号表示法;广义表链表。 树的度:一棵树中,最大的节点的度称为树的度; 兄弟节点:具有相同父节点的节点互称为兄弟节点 树中任意节点的子节点之间没有顺序关系,这种树称为无序树,...
  • 树的基本概念

    2021-03-03 14:51:09
    树的基本概念 树的定义: 树的结构特点: 若干术语 树的表示法 图形表达法: 广义表表示法 左孩子右兄弟表示法 作用: 将多叉树转化为二叉树
  • 二叉排序树的判定.cpp

    2019-06-16 14:14:49
    二叉排序树的判定,广义表表示法创建二叉树,C语言指针的相关应用。
  • (一)树的四种表示方法:直观表示法,嵌套集合表示法,凹入表示法,广义表表示法 (二)树的5种存储方式,即:多重链表表示法,双亲表示法,孩子链表表示法,双亲孩子表示法,孩子兄弟表示法 1.多重链表表示法...
  • 2021-03-14 10:48:04
    文章目录一、树的基本概念1. 概念2. 树的表示法3....广义表表示法、 左孩子-右兄弟表示法、 双亲孩子表示法。 3. 树的逻辑结构 一对多(1:n),有多个直接后继(如家谱树、目录树等等), 但只有一个根结点,
  • 广义表表示法 双亲表表示法 左孩子右兄弟表示法 孩子链表表示法 本文采用孩子链表表示法 2. 树的基本结构及函数总览 template<class T> class Tree { public://////这里应该是private的,但后面的友员函数涉及...
  • 树的笔记

    2014-12-29 22:03:59
    1.树:是n个结点的有限集T,T为空时称空树,否则满足: ...4)广义表表示法; 3.一个结点拥有的子树数称为该结点的度;一棵树的度是指树中结点最大的度数。 4.度为零的结点称叶子或终端结点;度不为零的结点
  • 第8讲 树的定义和二叉树的顺序存储 重点二叉树的性质顺序存储 难点二叉树性质的使用 一树的定义和和基本术语 1定义...2树的表示法 图示法 广义表表示法 集合表示法 A B A B E F L G C H I M N D K J (d) 缩进表示法 A D
  • 5.1树的概念

    2017-08-14 10:42:06
    树,用递归定义为:树是N(N>0)个结点的有限集合。 其中唯一关系具有下列属性:集合中存在唯一一个结点,...树的表示方法:树型表示法、文氏图表示法、凹入图表示法、广义表表示法。 一个结点的子树的个数称为该
  • 树的创建与遍历

    2015-04-22 22:20:00
    使用孩子链表表示法表示数,采用广义表的形式输入: #define ms 5//数的度 typedef struct node{//树的孩子链表表示法 char data; node* p[ms]; }*Tree; void createTree(Tree& tree,char* p){ tree=NULL...
  • 第6章 树和二叉树;F 6.1 树的定义和基本术语 F 6.2 二叉树 F 6.3 ...图形表示法 嵌套集合表示法 广义表表示法 凹入表示法目录表示法;图形表示法;广义表表示法;A;2.若干术语 ;A;已知一棵树的集合为{,M, ,N, ,I,E, ,D, ,B
  • (3)广义表表示法 ( A ( B ( E ,F( K, L ), ), C ( G ), D ( H , I, J ) ) (4)目录表示法 (5)左孩子-右兄弟表示法 2.结构与线性结构比较:  线性结构:第一个结点无前驱,最后一个结点无后继,其他
  • 树与二叉树基础知识重点归纳 树的定义 树(Tree):有n(n>0)个结点的有限集 1)....2)....2.1)有且仅有一个结点 ...广义表表示法。即用括号和逗号表示 树的基本术语 1). 结点:树中的一个独立单元 结点的度:结点拥有的子树数
  • 特点:非线性结构,一个直接前驱,但可能有多个直接后继(1:n) 树的基本概念 1. 树的定义 树是n个(n≥0)结点的有限集。在任意一颗非空树中 ...广义表表示法 左孩子-右兄弟表示法 图形表示法 ...
  • 树基本概念 非线性结构,一个直接前驱,但可能有多个直接后继(1:n) 树的定义具有递归性,即树中还有树 根 叶子 森林 有序树 无序树 双亲 孩子 兄弟 堂兄弟 祖先 子孙 ...树的表示法 图形表示法 广义表...
  • 文章目录1.... 广义表表示法 缩进表示法 结点分类 计算机角度:终端节点和非终端节点 树的特征:根节点,分支节点,叶子结点 族谱关系:双亲结点和孩子节点,祖先结点和子孙结点,兄弟结点和
  • 广义表表示法 左孩子-右兄弟表示法 (常用于一般树转为二叉树) 树的存储 常用顺序存储和链式存储。 顺序存储: 定义:使用线性表,按一定顺序存储各个节点。 存在问题:复原困难;对于非二叉树,...
  • c++tree

    2020-11-03 09:17:31
    1树基本概念 基础讲义: 参考《数据结构_树A.ppt》 参考《数据结构_树B.ppt》 非线性结构,一个直接前驱,但可能有多个直接后继(1:n) 树的定义 1)具有递归性,即树中还有树 ...广义表表示法 左孩子-右兄弟表
  • 数的定义和基本术语 树的概念:树是n个结点的有限集合 ...广义表 凹入表示法 树的基本术语 树的结点包含一个数据元素以及若干个(并不为一个)指向其子树的分支。 结点拥有的子树数称为结点的度; 度为零的结...
  • 数据结构10.

    2016-07-30 23:57:28
    引言  一.树的基本术语 二.树的分类 三.树的表示  一.树形  二.嵌套集合  三.广义表  四.凹入表示 四.树的存储结构  1.双亲链表表示法  2.孩子链表表示法
  • 数据结构课程的内容;...广义表表示法;其他表示方法;PowerPoint 演示文稿;PowerPoint 演示文稿;6.1.4. 树的抽象数据类;6.1.4. 树的抽象数据类;6.1.4. 树的抽象数据类;6.1.5 树的逻辑结构存储;讨论3树的链式

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 122
精华内容 48
关键字:

树的广义表表示法