精华内容
下载资源
问答
  • 本程序主要介绍使用c语言的树数据结构,比较全面的介绍和使用多叉树
  • c语言多叉树转二叉树

    千次阅读 2016-12-05 19:25:13
    多叉树转二叉树原理: 二叉树节点的左子树为对应多叉树节点的第一个孩子,右子树为多叉树中它的右兄弟,以此类推 #include #include #define M 5 /* 多叉树最大子数量为5 */ typedef struct mtree_node { int val;...

    C语言练手.多叉树转二叉树

    原理: 二叉树节点的左子树为对应多叉树节点的第一个孩子,右子树为多叉树中它的右兄弟,以此类推

    #include <stdio.h>
    #include <stdlib.h>
    
    #define M 5  /* 多叉树最大子数量为5 */
    
    typedef struct mtree_node
    {
        int val;
    	struct mtree_node *subTree[M];
    }MTREE_NODE;   /* 多叉树结构 */
    
    
    typedef struct btree_node
    {
        int val;
    	struct btree_node *offspring; /* 左子树 */
    	struct btree_node *sibling; /* 右子树 */
    }BTREE_NODE; /* 二叉树结构 */
    
    
    static int to_btree(struct mtree_node *pmnode, struct btree_node *pbroot)
    {
            int i = 0;
    	BTREE_NODE *ptmep;
    
    
    	pbroot->val = pmnode->val;
    
    
    	if (pmnode->subTree[0] == NULL) {
    		pbroot->offspring = NULL;
    		return 0;
    	}
    	
    	BTREE_NODE *pbnode = (BTREE_NODE *)malloc(sizeof(BTREE_NODE));
    	pbroot->offspring = pbnode;
    	to_btree(pmnode->subTree[0],pbnode);
    	
        i = 1;
    	ptmep = pbnode;
    	while (i < M && pmnode->subTree[i] != NULL) {
    		BTREE_NODE *pbnode = (BTREE_NODE *)malloc(sizeof(BTREE_NODE));
    		ptmep->sibling = pbnode;
    		ptmep = pbnode;
    
    
    		to_btree(pmnode->subTree[i],pbnode);
    		i++;
    	}
    	ptmep->sibling = NULL;
    
    
    	return 0;
    }
    
    
    static int btree_print(BTREE_NODE *proot)
    {
        BTREE_NODE *pnode = proot;
    	
    	printf("%d",pnode->val);
    
    
    	if (pnode->offspring != NULL) {
    		btree_print(pnode->offspring);
    	}
    	if (pnode->sibling != NULL) {
    		btree_print(pnode->sibling);
    	}
    
    
    	free(proot);
    	return 0;
    }
    
    
    int main (int args, char *argv[])
    {
        MTREE_NODE *mtree;
    	BTREE_NODE *btree;
        MTREE_NODE *mtemp;
    	MTREE_NODE *mstemp;
    	int i = 0;
    	int j = 0;
    	
        mtree = (MTREE_NODE *)malloc(sizeof(MTREE_NODE));
        mtree->val = 0;
    	
    /* 为了测试构建一颗多叉树 */
    	for (;i<3;i++) {
    	    mtemp = (MTREE_NODE *)malloc(sizeof(MTREE_NODE));
    		mtree->subTree[i] = mtemp;
    		mtemp->val = i+1;
    		for(j=0;i<2 && j<3;j++) {
    			mstemp = (MTREE_NODE *)malloc(sizeof(MTREE_NODE));
    			mtemp->subTree[j] = mstemp;
    			mstemp->val = j+4+3*i;
    		}
    	}    
    	
    	if (mtree == NULL) {
    		return 0;
    	}
    
    
    	btree = (BTREE_NODE *)malloc(sizeof(BTREE_NODE));
    
    /* 可将任意多叉树转换成二叉树,参数为多叉树和二叉树的根节点 */
    	to_btree(mtree,btree);
    
    
    	btree_print(btree); /* 前序遍历打印二叉树,测试用 */
    	
    	return 0;
    }	

    展开全文
  • 一种C语言字典创建和搜索的示例,可以创建一种无论增加多少单词,搜索速度依然 = 该语言字母数 * 单词长度 的效率的存储结构。一个demo
  • 多叉树的建立以及后序非递归遍历,希望对学习数据结构的同学有所帮助,也对树一部分有更深的了解。
  • Problem Description A graph G with n×m nodes forms a n×m grid with n×m vertices. (n−1)×m weighted edges connect the vertices of adjacent rows, and n×(m−1) weighted edges connect the vertices ...
  • 多叉树的基本操作(C++实现)

    千次阅读 2020-11-12 00:40:17
    文章目录前言创建多叉树展示多叉树销毁一颗多叉树前序遍历(递归&非递归)递归写法非递归写法后序遍历(递归&非递归)递归写法非递归写法层次遍历计算多叉树的高度计算多叉树叶子节点的个数打印输出根节点到所有...

    前言

    我们都知道如何表达一颗二叉树:使用结构体记录每个节点的数据(data),指向左节点的指针(*left)和指向右节点的指针(*right)。我们一般会把二叉树节点的结构体定义如下:

    typedef struct node
    {
    	char data;		// 节点数据	
    	struct node *left, *right;	// 指向左节点和右节点的指针
    }BT;
    

    但是多叉树就不好这么表示了,因为我们不知道多叉树的每个节点的子节点上限是多少,这样多叉树节点的结构体就不好写了。因此实际操作时,我们一般会把多叉树写成二叉链的形式:

    typedef struct node
    {
        char data;		// 节点数据
        struct node *fir, *sib;		// 指向第一个子节点和下一个兄弟节点的指针
    }TR;
    

    我们把上述儿子兄弟的节点表达方式成为多叉树的二叉链表达。举个例子,比如我们的多叉树长这个样子:

    A
    B
    C
    D
    E
    F
    G

    则它的二叉链表达为:

    A
    B
    NULL
    E
    F
    NULL
    NULL
    NULL
    C
    NULL
    D
    G
    NULL
    NULL
    NULL

    每个节点的依旧只有左右节点,但是它们的实际含义已经和二叉树节点的左右节点不一样了。比如当前我们考察的节点为node,则二叉链node的左节点(node.fir)代表node的第一个子节点,可以发现图中E的左节点为F,说明FE的第一个子节点;C的左节点为NULL,说明C没有子节点。这些观察都符合原来在多叉树中的观察结果。
    node的右节点node.sib代表node的兄弟节点,也就是在多叉树中与node同层且在node右侧的那一个节点。比如C的右节点为D,说明在多叉树中,C的同层的右边那个节点为D,这也是合理的。

    继而对于这样的树的操作与二叉树相比会有所不同。下面在这样的一颗多叉树上实现如下的功能:

    TR *createTR(char *in, char *pre, int k);   //  创建一棵树
    void showTR(TR *T);     // 展示一棵树   A(B,C(E,F))这样的形式
    TR *destroy(TR *T);     //  销毁一棵树
    void preorder(TR *T);   // 前序遍历
    void postorder(TR *T);  // 后序遍历
    void layer(TR *T);      // 层次遍历
    int height(TR *T);      // 树的高度
    int leaf(TR *T);        // 计算叶子的数量
    void getpath1(TR *T);   // 打印根到叶子节点的所有路径(dfs)
    void allpath(TR *T,char *path,int n);   // 配合getpath1完成递归
    void getpath2(TR *T);   // 基于后序遍历的非递归找路径
    void getpath3(TR *T);   // 基于层次遍历的非递归找路径
    void longestPath(TR *T);    // 输出根节点到叶子节点所有路径中最长的那些路径 
    void insert(TR *T, char s1, char s2);  // 在data为s1的节点下插入data为s2的子节点
    // 若s1有子节点,则将s2放入s1的末尾;若s1没有子节点,则将s2作为新的节点插入
    TR *delsub(TR *T, char s);      // 递归地销毁根节点data为s的子树
    TR *lca(TR *T, char s1, char s2);   // 寻找s1和s2的最近公共祖先
    void mirror(TR *T);     // 多叉树逆置
    

    具体细节有时间再写~~~


    创建多叉树

    我们使用多叉树对应的二叉链的前序遍历与中序遍历作为输入创建一颗多叉树,这和二叉树的创建几乎无异。

    TR *createTR(char *in, char *pre, int k)
    {
        if (k <= 0)
        {
            return NULL;
        }
        else
        {
            TR *node = new TR;         // 创建一个新节点
            node->data = pre[0];      // 新节点的data为当前先序遍历的开头,也就是本层递归创建的树的根节点
            int i;
            for (i = 0; in[i] != pre[0]; ++ i);     // 在中序遍历中寻找根节点,i代表根节点在中序遍历中的索引
            node->fir = createTR(in, pre + 1, i);	// 创建二叉链的左分支的根节点
            node->sib = createTR(in + i + 1, pre + i + 1, k - i  - 1);	// 创建二叉链的右分支的根节点
            return node;
        }
    }
    

    展示多叉树

    我们将以前序的顺序输出一颗多叉树,假设我们的多叉树如下:

    A
    B
    C
    D
    E
    F
    G

    那么我们的输出为

    A(B(E,F),C,D(G))
    

    代码如下:

    void showTR(TR *T)
    {
        if (T)
        {
            cout << T->data;
            if (T->fir)
            {
                cout << "(";
                TR *p = T->fir;
                showTR(p);
                p = p->sib;
                while (p)
                {
                    cout << ",";
                    showTR(p);
                    p = p->sib;
                }
                cout << ")";
            }
        }
    }
    

    销毁一颗多叉树

    销毁以T为根节点的一整颗多叉树。通过递归实现。

    TR *destroy(TR *T)
    {
        if (!T)
        {
            return NULL;
        }
        else
        {
            TR *p = T->fir, *p2;
            while(p)
            {
                p2 = p->sib;     // 因为p会被销毁,所以需要一个p2来保存指向的节点地址
                destroy(p);
                p = p2;
            }
            delete T;
            return NULL;
        }
    }
    

    前序遍历(递归&非递归)

    多叉树的前序遍历写法和二叉树的一模一样,这里提供递归和非递归两种写法。

    递归写法

    递归写法没什么好说的,直接写就是了。

    void preorder(TR *T)
    {
        if (T)
        {
            cout << T->data << " ";
            preorder(T->fir);
            preorder(T->sib);
        }
    }
    

    非递归写法

    非递归通过栈的数据结构来完成,也就是每次弹栈时将弹出元素的右左节点依次入栈。

    void preorder(TR *T)
    {
        TR *s[N], *p;       // 使用栈来模拟递归
        int top = 0;
        s[top] = T;     // 根节点先入栈
    
        while (top >= 0)
        {
            p = s[top --];  // 先取出栈顶元素
            cout << p->data << " ";
    
            // 按先右再左的顺序将出栈元素的fir和sib入栈
            if (p->sib)
            {
                s[++ top] = p->sib;
            }     
            if (p->fir)
            {
                s[++ top] = p->fir;
            }
        }
    }
    

    后序遍历(递归&非递归)

    由于多叉树的子节点数量不确定,所以在多叉树中无法实现中序遍历,因此,只有前序遍历、后序遍历和层次遍历。

    关于后序遍历,可以证明,多叉树(二叉链,也就是儿子兄弟表示法)的后序遍历等同于二叉树的中序遍历。因此,我们只需要把二叉树中中序遍历的写法应用到多叉树的后序遍历中就行了。此处同样提供递归与非递归两种写法。

    递归写法

    void postorder(TR *T)
    {
        if (T)
        {
            postorder(T->fir);
            cout << T->data << " ";
            postorder(T->sib);
        }
    }
    

    非递归写法

    非递归写法同样是使用栈的数据结构,需要注意的是,我们需要每次都把最靠左的分支先搜索完。再进入右分支。

    void postorder(TR *T)
    {
        // 多叉树的后序遍历的写法对应于二叉树的中序遍历
        TR *s[N], *p = T;
        int top = -1;
    
        while (top >= 0 || p)
        {
            // 先将目前节点的全部子节点入栈
            while (p)
            {
                s[++ top] = p;
                p = p->fir;
            }
            // 打印栈顶元素,并进入栈顶元素的兄弟节点
            p = s[top --];
            cout << p->data << " ";
            p = p->sib;
        }
    }
    

    层次遍历

    层次遍历一般通过非递归的写法实现,我们通过队列的数据结构来实现。基本原理和二叉树的层次遍历几乎无异:每次讲一个元素弹栈后,将该元素的所有的子节点入队。只不过此时要通过sib指针来遍历获得一个节点下所有的子节点。

    void layer(TR *T)
    {
        TR *q[N], *p;       // 通过队列来完成层次遍历
        int front, rear;
        front = rear = 0;
        q[rear ++] = T;     // 根节点先入队
    
        while (front != rear)       // 循环的结束条件为队列为空
        {
            // 基本逻辑很简单,每打印队首的元素,就将队首的所有节点全部入队
            p = q[front ++];
            cout << p->data << " ";
            p = p->fir;
    
            while (p)
            {
                q[rear ++] = p;
                p = p->sib;
            }
        }
    }
    

    计算多叉树的高度

    同二叉树一样,此处还是通过递归完成高度的计算。不同的是,左右节点递归返回的高度的意义不一样:多叉树的二叉链表示中,左节点代表它的第一个子节点,右节点代表下一个兄弟节点,显然兄弟节点会相对高处子节点,所以我们需要对返回的左节点加一,以保证它和右节点在“同一个高度”进行比较。

    int height(TR *T)
    {
        if (!T)
        {
            return 0;
        }
        else
        {
            int h1, h2;
            h1 = height(T->fir) + 1;       // 由于T的子节点比兄弟节点低一层,所以需要加一
            h2 = height(T->sib);
            return max(h1, h2);
        }
    }
    

    计算多叉树叶子节点的个数

    一个简单的递归就可以完成,不过请注意二叉链的结构特征。用mermaid画个图举个例子:

    A
    B
    NULL
    E
    NULL
    NULL
    C
    NULL
    D
    NULL
    NULL

    递归边界自然是T==NULL时,此时返回0就行;如果在T非空的情况下,T->fir==NULL,说明当前的T是二叉链中的一个出度为1的点,同时也是原来的多叉树中的一个叶子,比如图中的C点,这个时候C应该把D的递归结果leaf(T->sib)(此处假设T->data=='C')返回,否则最后传到根节点A时,D分支的叶子数量信息就丢失了;同时C递归返回的信息还需要+1,因为C本身就是多叉树中的叶子。

    如果是二叉链中出度为2的节点,比如B,它本身在多叉树中也不是叶子,所以直接把两个分支的统计情况加起来向上递归即可。

    总的程序如下:

    int leaf(TR *T)
    {
        if (!T)
            return 0;
        else if (!T->fir)
            return 1 + leaf(T->sib);	// 二叉链的结构特性导致需要把兄弟节点返回的个数加一
        else  
            return leaf(T->fir) + leaf(T->sib);
    }
    

    打印输出根节点到所有叶子节点的路径(深度优先-递归)

    此处通过两个函数完成:getpath1函数负责完成存储路径的数组*path的创建,并把根节点加入*path中,然后调用allpath函数;allpath函数通过递归实现深度优先搜索。

    代码如下:

    void getpath1(TR *T)
    {
        char path[N];
        path[0] = T->data;
        allpath(T, path, 1);
    }
    
    void allpath(TR *T, char *path, int n)
    {
        if (!T->fir)
        {
            for (int i = 0; i < n; ++ i)
                cout << path[i] << " ";
            cout << endl;
        }
        if (T->fir)
        {
            path[n] = T->fir->data;
            allpath(T->fir, path, n + 1);
        }
        if (T->sib)
        {
            path[n - 1] = T->sib->data;
            allpath(T->sib, path, n);
        }
    }
    

    打印输出根节点到所有叶子节点的路径(基于后序遍历-非递归)

    由于我们是通过栈实现非递归的后序遍历,这带来一个好处:每次将叶子节点弹出栈时,由于其父节点先入栈,所以叶子节点的父节点往上的一堆节点都还在栈中。我们可以利用这一特性,在每次弹出叶子节点时,顺便将栈中元素全部打印,这就是我们需要的路径了。代码如下:

    void getpath2(TR *T)    // 基于后序遍历的路径搜索
    {
        TR *s[N], *p = T;
        int top = -1;
    
        while (top >= 0 || p)
        {
            while (p)
            {
                s[++ top] = p;
                p = p->fir;
            }
    
            p = s[top];
            if (!p->fir)    // 当前弹出的元素没有子节点,说明该节点为叶子,打印此时的栈内元素便是路径
            {
                for (int i = 0; i <= top; ++ i)
                    cout << s[i]->data << " ";
                cout << endl;
            }
            top --;
            p = p->sib;
        }
    }
    

    打印输出根节点到所有叶子节点的路径(基于层次遍历-非递归)

    由于层次遍历的过程中,不断有节点的父节点被弹出,因此,我们需要记录每个节点的父节点在队列中的位置,这样,一旦我们找到一个叶子节点,就可以顺着父亲节点的索引一路倒着将路径打印出来了。

    为此我们创建一个结构体QU

    typedef struct queue
    {
        int fa;		// 记录node节点的父节点在队列中的索引
        TR *node;		// 指向TR节点的指针
    }QU;
    

    代码如下:

    void getpath3(TR *T)
    {
        QU q[N];
        TR *p;
        int front, rear;
        front = rear = 0;
        q[rear].node = T;
        q[rear].fa = -1;
        rear ++;
    
        while (front != rear)
        {
            p = q[front].node;
            if (!p->fir)
            {
                for (int i = front; i != -1; i = q[i].fa)
                    cout << q[i].node->data << " ";
                cout << endl;
            }
            else
            {
                p = p->fir;
                while (p)
                {
                    q[rear].node = p;
                    q[rear].fa = front;
                    rear ++;
                    p = p->sib;
                }
            }
            front ++;
        }
    }
    

    输出根节点到叶子节点所有路径中最长的那些路径

    思路很简单,我们先通过height函数计算出树的高度,这个高度不就等于整棵树所有根节点到叶子节点的路径中最长路径长度吗?

    然后通过上述的三种打印路径的算法,每次打印路径前,都统计一下打印路径的长度,如果长度等于树的高度,说明这是一条最长的路径,那么就打印;反之,则不打印。

    void longestPath(TR *T)
    {
        int max_length = height(T);
    
        QU q[N];
        TR *p;
        int front, rear;
        front = rear = 0;
        q[rear].fa = -1;
        q[rear].node = T;
        rear ++;
    
        while (front != rear)
        {
            p = q[front].node;
            if (!p->fir)
            {
                int length = 0;
                for (int i = front; i != -1; i = q[i].fa)
                    length ++;
                if (length == max_length)
                {
                    for (int i = front; i != -1; i = q[i].fa)
                        cout << q[i].node->data << " ";
                    cout << endl;
                }
            }
            else
            {
                p = p->fir;
                while (p)
                {
                    q[rear].fa = front;
                    q[rear].node = p;
                    rear ++;
                    p = p->sib;
                }
            }
            front ++;
        }
    }
    

    递归实现节点的插入

    我再把这个函数做的事情说得清楚些:在data为s1的节点下插入data为s2的子节点。若s1有子节点,则将s2放入s1的末尾;若s1没有子节点,则将s2作为新的节点插入。
    这个就比较简单了,不再过多废话了。

    void insert(TR *T, char s1, char s2)        // 递归实现节点的插入
    {
        if (T)
        {
            if (T->data == s1)
            {
                TR *node = new TR;
                node->fir = node->sib = NULL;
                node->data = s2;
                if (T->fir)		// 当前节点有子节点,则找到最后一个子节点
                {
                    TR *p =  T->fir;
                    while (p->sib)
                        p = p->sib;
                    p->sib = node;
                }
                else	// 当前节点没有子节点,则直接作为当前节点的子节点
                {
                    T->fir = node;
                }
            }
            else
            {
                insert(T->fir, s1, s2);
                insert(T->sib, s1, s2);
            }
        }
    }
    

    删除子树

    功能:给定多叉树的根节点和需要删除的节点的data。删除以data为根节点的子树。

    这个需要注意,如果我们删除的节点有兄弟节点,我们就需要把它的兄弟节点和之前的节点接上,否则一删除该节点,其兄弟节点后面那一块也都全没了=_=

    TR *delsub(TR *T, char s)
    {
        if (!T)
        {
            return NULL;
        }
        else if (T->data == s)
        {
            return destroy(T);
        }
        else
        {
            if (T->fir && T->fir->data == s)	// 如果当前节点的子节点就是我们要删除的节点,则需要把其子节点的兄弟节点做处理(当然,如果)
                T->fir = T->fir->sib;
            delsub(T->fir, s);
    
            if (T->sib && T->sib->data == s)
                T->sib = T->sib->sib;
            delsub(T->sib, s);
            return T;
        }
    }
    

    递归实现最近公共祖先查询

    最近祖先又称为lca,相信看到这里的同学都知道lca是怎么一回事,我就懒得写了。直接上代码:

    TR *lca(TR *T, char s1, char s2)
    {
        if (!T)
            return NULL;
        if (T->data == s1 || T->data == s2)
            return T;
        else
        {
            TR *s[3], *p = T->fir, *q;	// s数组记录以T的各个子节点为根节点进行的lca查询中,返回值非NULL的那些节点
            int top = 0;
            while (p)
            {
                q = lca(p, s1, s2);
                if (q)
                    s[top ++] = q;
                p = p->sib;
            }
    
            if (top == 0)
                return NULL;
            if (top == 2)
                return T;
            else
                return s[0];        
        }
    }
    

    多叉树逆置

    将一颗多叉树做镜像,比如我们的多叉树如下:

    A
    B
    D
    E
    F
    C

    那么逆置后的多叉树如下:

    A
    C
    B
    F
    E
    D

    代码如下,我们通过递归来实现:

    void mirror(TR *T)
    {
        TR *p, *p2;
        if (!T || !T->fir)
            return;
        else
        {
            p = T->fir;
            T->fir = NULL;
            while (p)       // 通过头插法来逆置
            {
                mirror(p);
                p2 = p->sib;
                p->sib = T->fir;
                T->fir = p;
                p = p2;
            }
        }
    }
    

    验证

    最后可以通过如下的主函数验证函数结果:

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #define N 100
    using namespace std;
    
    main()
    {
        char pre[]="ABEFCDGHIJ",in[]="EFBCHIJGDA";  // 目标多叉树对应的二叉链的先序遍历和中序遍历
        TR *header = NULL;
        int length = strlen(pre);
    
        header = createTR(in, pre, length); // 创建一颗多叉树
        cout << "创建的树为:" << endl;
        showTR(header);
        cout << endl;
    
        cout << "前序遍历:" << endl;
        preorder(header);
        cout << endl;
    
        cout << "后序遍历:" << endl;
        postorder(header);
        cout << endl;
    
        cout << "层次遍历:" << endl;
        layer(header);
        cout << endl;
    
        cout << "树的高度为:" << endl;
        cout << height(header) << endl;
    
        cout << "树的叶子数量为:" << endl;
        cout << leaf(header) << endl;
    
        cout << "从根节点到子节点的所有路径(递归):" << endl;
        getpath1(header);
        cout << endl;
    
        cout << "从根节点到子节点的所有路径(后序遍历):" << endl;
        getpath2(header);
        cout << endl;
    
        cout << "从根节点到子节点的所有路径(层次遍历):" << endl;
        getpath3(header);
        cout << endl;
    
        cout << "根节点到叶子节点的最长路径有:" << endl;
        longestPath(header);
        cout << endl;
    
        cout << "插入新节点后的树:" << endl;
        insert(header, 'E', 'X');
        insert(header, 'A', 'K');
        insert(header, 'I', 'L');
        showTR(header);
        cout << endl;
    
        TR *p;
        p = lca(header, 'X', 'F');
        cout << "距离X和F最近的共同祖先是:" << p->data << endl;
        p = lca(header, 'K', 'L');
        cout << "距离K和L最近的共同祖先是:" << p->data << endl;
        p = lca(header, 'L', 'H');
        cout << "距离L和H最近的共同祖先是:" << p->data << endl;
    
        cout << "删除I分支后,树为:" << endl;
        header = delsub(header, 'I');
        showTR(header);
        cout << endl;
    
        cout << "删除E分支后,树为:" << endl;
        header = delsub(header, 'E');
        showTR(header);
        cout << endl;
        
        mirror(header);
        cout << "逆置后的多叉树为:" << endl;
        showTR(header);
        cout << endl;
    
        cout << "销毁树" << endl;
        destroy(header);
    }
    
    

    输出结果:

    创建的树为:
    A(B(E,F),C,D(G(H,I,J)))
    前序遍历:
    A B E F C D G H I J
    后序遍历:
    E F B C H I J G D A
    层次遍历:
    A B C D E F G H I J 
    树的高度为:
    4
    树的叶子数量为:
    6
    从根节点到子节点的所有路径(递归):
    A B E
    A B F
    A C
    A D G H
    A D G I
    A D G J
    
    从根节点到子节点的所有路径(后序遍历):
    A B E
    A B F 
    A C
    A D G H
    A D G I
    A D G J
    
    从根节点到子节点的所有路径(层次遍历):
    C A
    E B A
    F B A
    H G D A
    I G D A
    J G D A
    
    根节点到叶子节点的最长路径有:
    H G D A
    I G D A 
    J G D A
    
    插入新节点后的树:
    A(B(E(X),F),C,D(G(H,I(L),J)),K)
    距离X和F最近的共同祖先是:B
    距离K和L最近的共同祖先是:A
    距离L和H最近的共同祖先是:G
    删除I分支后,树为:
    A(B(E(X),F),C,D(G(H,J)),K)
    删除E分支后,树为:
    A(B(F),C,D(G(H,J)),K)
    逆置后的多叉树为:
    A(K,D(G(J,H)),C,B(F))
    销毁树
    
    展开全文
  • 多叉树应用(多叉树创建, 遍历)

    千次阅读 2017-11-03 17:32:01
    多叉树创建, 遍历...

    1. 项目上遇到了一个典型的多叉树应用案例, 记录一下。

    (1)

    //结构

    typedef struct  st_OriTree
    {
    	int levelValue;    //树的level
    	int orderValue;    //排序值
    	QString nameValue; //当前节点名称
    	QString preNameValue; //前置节点名称
    	QMultiMap<int, st_OriTree *> childrenList; //子节点列表
    }OriTree;


    
    (2)
    

    //创建多叉树,要求: 节点不允许重复。在构建的时候, 层次优先遍历树结构,查找重复节点。

    void TNDataCache::appendTreeNode(OriTree **head, OriTree node)
    {
    	if (*head == nullptr)
    		return;
    
    	QQueue<OriTree*> queue;
    	queue.append(*head);
    
    	bool isExist = false;
    	OriTree* p = nullptr;
    	OriTree* q = *head;
    	while (!queue.isEmpty())
    	{
    		p = queue.front();
    		queue.pop_front();
    		if (p != nullptr)
    		{
    			for (int i = 0; i < p->childrenList.count(); i++)
    			{
    				if (p->childrenList.values().at(i)->preNameValue == node.preNameValue
    					&& p->childrenList.values().at(i)->levelValue == node.levelValue)
    				{
    					if (p->childrenList.values().at(i)->nameValue == node.nameValue)
    					{
    						isExist = true;
    						break;
    					}
    					continue;
    				}
    				if (p->childrenList.values().at(i)->levelValue == node.levelValue - 1
    					&& p->childrenList.values().at(i)->nameValue == node.preNameValue)
    				{
    					q = p->childrenList.values().at(i);
    				}
    				queue.append(p->childrenList.values().at(i));
    			}
    		}
    	}
    	if (!isExist && q!= nullptr)
    	{
    		//create new node
    		OriTree * newNode = new OriTree();
    		if (newNode == nullptr || p == nullptr)
    		{
    			qDebug() << "new OriTree node failed , node Name :" << node.nameValue;
    			return;
    		}
    		newNode->feedValue = node.feedValue;
    		newNode->levelValue = node.levelValue;
    		newNode->nameValue = node.nameValue;
    		newNode->orderValue = node.orderValue;
    		newNode->preNameValue = node.preNameValue;
    		Q_ASSERT(q->feedValue == nullptr);
    		if (q->feedValue != nullptr)
    		{
    			qDebug() << "new OriTree build tree error, node Name" << node.nameValue;
    			return;
    		}
    		q->childrenList.insert(node.orderValue, newNode);
    	}
    }

    (3) 

    // 层次优先遍历多叉树结构(利用队列实现),按层,深度输出节点名称。 如果逆向输出,需要借助栈

    void travel(OriTree * tree)
    {
    	if (tree == nullptr)
    		return;
    
    	QQueue<OriTree*> qTree;
    	qTree.append(tree);
    	
    	OriTree* p = nullptr;
    	while (!qTree.isEmpty())
    	{
    		p = qTree.front();
    		qTree.pop_front();
    		if (p != nullptr)
    		{
    			for (int i = 0; i < p->childrenList.count(); i++)
    			{
    				qDebug() << p->childrenList.values().at(i)->nameValue;
    				qTree.append(p->childrenList.values().at(i));
    			}
    		}
    	}
    }
    (4)

    //(递归)深度优先遍历多叉树,输出所有叶子路径, Queue<OriTree *>pathQueue ;

    void travel(OriTree * tree)
    {
    	pathQueue.append(tree);
    	if (tree == nullptr || tree->childrenList.values().count() == 0)
    	{
    		//一条路径遍历完毕,此时pathQueue为完整的节点路径
    		qDebug() << pathQueue.size();
    		//将最后入队的节点pop
    		pathQueue.pop_back();
    		return;
    	}
    	for (int i = 0; i < tree->childrenList.values().count(); i++)
    	{
    		BuildTreeItem(tree->childrenList.values().at(i));
    		if (i == tree->childrenList.values().count() - 1)
    		{
    			pathQueue.pop_back(); //当前节点 pop
    		}
    	}
    }

    ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    以下内容来自博客: 

    http://www.cnblogs.com/unixfy/p/3486179.html

    多叉树的设计、建立、层次优先遍历和深度优先遍历

    多叉树的设计、建立、层次优先遍历和深度优先遍历

             早起曾实现过一个简单的多叉树《实现一个多叉树》。其实现原理是多叉树中的节点有两个域,分别表示节点名以及一个数组,该数组存储其子节点的地址。实现了一个多叉树建立函数,用于输入格式为A B。A表示节点的名字,B表示节点的子节点个数。建立函数根据用户的输入,首先建立一个新的节点,然后根据B的值进行深度递归调用。用户输入节点的顺序就是按照深度递归的顺序。另外,我们实现了一个层次优先遍历函数。该函数用一个队列实现该多叉树的层次优先遍历。首先将根节点入队列,然后检测队列是否为空,如果不为空,将队列出队列,访问出队列的节点,然后将该节点的子节点指针入队列,依次循环下去,直至队列为空,终止循环,从而完成整个多叉树的层次优先遍历。

             本文我们将还是介绍一个多叉树,其内容和之前的实现差不多。

             首先,用户的多叉树数据存储在一个文件中,格式如下:


    每行的第一个元素指定一个节点,其中第一行指定了该多叉树的根节点。第二个元素表示该节点有几个子节点,紧接着后面跟了几个子节点。

             根据以上数据文件,其对应的多叉树应该是如下:

    我们想得到结果是将书中的节点按深度进行输出,比如先输出深度最深的节点:x e j,然后输出深度为2的节点:d f i,之后再输出深度为1的节点:g cC z bBbB,最后输出根节点:aA。

             按照深度将节点输出,很显然是用层次优先遍历的方法解决。层次优先遍历的实现原理就是从根节点开始,利用队列实现。

             另外,我们想得到从根节点开始到叶子节点直接所有节点名字加起来最长的一个路径,比如上面的树中存在以下几条路径:

                                                     aA g d x

                                                     aA g d e

                                                     aA g d j

                                                     aA cC

                                                     aA z f

                                                     aA z i

                                                     aA bBbB



    显然,在这些路径中,aA bBbB是所有路径上节点名字加起来最长的一个路径。求解从根节点到叶子节点上的所有路径,利用深度优先遍历更为合适。

             下面我们讨论一下多叉树节点应该如何建立。首先多叉树的节点应该如何定义,节点除了有自身的名字外,还要记录其子节点有多少个,每个子节点在哪里,所以我们需要增加一个记录子节点个数的域,还要增加一个数组,用来记录子节点的指针。另外,还要记录多叉树中每个节点的深度值。

             在读取数据文件的过程中,我们顺序扫描整个文件,根据第一个名字,建立新的节点,或者从多叉树中找到已经有的节点地址,将后续的子节点生成,并归属于该父节点,直至扫描完整个数据文件。

             读取完整个文件后,也就建立了多叉树,之后,我们利用队列对多叉树进行广度优先遍历,记录各个节点的深度值。并将其按照深度进行输出。

             获取从根节点到子节点路径上所有节点名字最长的路径,我们利用深度优先遍历,递归调用深度优先遍历函数,找到最长的那个路径。

             初次之外,还需定义队列结构体,这里使用的队列是循环队列,实现相关的队列操作函数。还有定义栈的结构体,实现栈的相关操作函数。另外对几个内存分配函数、字符串拷贝函数、文件打开函数进行了封装。需要注意的一点就是当操作完成后,需要对已经建立的任何东西都要销毁掉,比如中途建立的队列、栈、多叉树等,其中还包含各个结构体中的指针域。

             另外,函数测试是用户在命令行模式下输入程序名字后面紧跟数据文件的形式。

             该程序的主要部分有如下几点:

             1.多叉树节点的定义和生成一个新节点

             2.数据文件的读取以及多叉树的建立

             3.根据节点名字在多叉树中查找节点的位置

             4.多叉树的层次优先遍历

             5.多叉树的深度优先遍历

             6.队列的定义以及相关操作函数实现

             7.栈的定义以及相关操作函数实现

             8.消毁相关已经建立好的队列、栈、多叉树等

             9.测试模块

             下面我们给出相关的程序实现,具体细节可以查看代码和注释说明。


    // 多叉树的建立、层次遍历、深度遍历

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define M 100+1 // 宏定义,定义最大名字字母长度
    
    // 定义多叉树的节点结构体
    typedef struct node_t
    {
        char* name;               // 节点名
        int   n_children;         // 子节点个数
        int   level;              // 记录该节点在多叉树中的层数
        struct node_t** children; // 指向其自身的子节点,children一个数组,该数组中的元素时node_t*指针
    } NODE; // 对结构体重命名
    
    // 实现一个栈,用于后续操作
    typedef struct stack_t
    {
        NODE** array; // array是个数组,其元素为NODE*型指针
        int    index; // 指示栈顶元素
        int    size;  // 栈的大小
    } STACK; // 重命名
    
    // 实现一个队列,用于后续操作
    typedef struct queue_t
    {
        NODE** array; // array是个数组,其内部元素为NODE*型指针
        int    head;  // 队列的头
        int    tail;  // 队列的尾
        int    num;   // 队列中元素的个数
        int    size;  // 队列的大小
    } QUEUE;
    
    // 这里的栈和队列,都是用动态数组实现的,另一种实现方式是用链表
    
    // 内存分配函数
    void* util_malloc(int size)
    {
        void* ptr = malloc(size);
    
        if (ptr == NULL) // 如果分配失败,则终止程序
        {
            printf("Memory allocation error!\n");
            exit(EXIT_FAILURE);
        }
    
        // 分配成功,则返回
        return ptr;
    }
    
    // 字符串赋值函数
    // 对strdup函数的封装,strdup函数直接进行字符串赋值,不用对被赋值指针分配空间
    // 比strcpy用起来方便,但其不是标准库里面的函数
    // 用strdup函数赋值的指针,在最后也是需要free掉的
    char* util_strdup(char* src)
    {
        char* dst = strdup(src);
    
        if (dst == NULL) // 如果赋值失败,则终止程序
        {
            printf ("Memroy allocation error!\n");
            exit(EXIT_FAILURE);
        }
    
        // 赋值成功,返回
        return dst;
    }
    
    // 对fopen函数封装
    FILE* util_fopen(char* name, char* access)
    {
        FILE* fp = fopen(name, access);
    
        if (fp == NULL) // 如果打开文件失败,终止程序
        {
            printf("Error opening file %s!\n", name);
            exit(EXIT_FAILURE);
        }
    
        // 打开成功,返回
        return  fp;
    }
    
    // 实现一些栈操作
    
    // 栈的初始化
    STACK* STACKinit(int size) // 初始化栈大小为size
    {
        STACK* sp;
    
        sp = (STACK*)util_malloc(sizeof (STACK));
        sp->size  = size;
        sp->index = 0;
        sp->array = (NODE**)util_malloc(size * sizeof (NODE*));
    
        return sp;
    }
    
    // 检测栈是否为空
    // 如果为空返回1,否则返回0
    int STACKempty(STACK* sp)
    {
        if (sp == NULL || sp->index <= 0) // 空
        {
            return 1;
        }
        return 0;
    }
    
    // 压栈操作
    int STACKpush(STACK* sp, NODE* data)
    {
        if (sp == NULL || sp->index >= sp->size) // sp没有被初始化,或者已满
        {
            return 0; // 压栈失败
        }
    
        sp->array[sp->index++] = data; // 压栈
        return 1;
    }
    
    // 弹栈操作
    int STACKpop(STACK* sp, NODE** data_ptr)
    {
        if (sp == NULL || sp->index <= 0) // sp为初始化,或者为空没有元素
        {
            return 0;
        }
    
        *data_ptr = sp->array[--sp->index]; // 弹栈
        return 1;
    }
    
    // 将栈消毁
    void STACKdestroy(STACK* sp)
    {
        free(sp->array);
        free(sp);
    }
    // 以上是栈的操作
    
    // 实现队列的操作
    QUEUE* QUEUEinit(int size)
    {
        QUEUE* qp;
    
        qp = (QUEUE*)util_malloc(sizeof (QUEUE));
        qp->size  = size;
        qp->head  = qp->tail = qp->num = 0;
        qp->array = (NODE**)util_malloc(size * sizeof (NODE*));
    
        return qp;
    }
    
    // 入队列
    int QUEUEenqueue(QUEUE* qp, NODE* data)
    {
        if (qp == NULL || qp->num >= qp->size) // qp未初始化或已满
        {
            return 0; // 入队失败
        }
    
        qp->array[qp->tail] = data; // 入队,tail一直指向最后一个元素的下一个位置
        qp->tail = (qp->tail + 1) % (qp->size); // 循环队列
        ++qp->num;
        return 1;
    }
    
    // 出队列
    int QUEUEdequeue(QUEUE* qp, NODE** data_ptr)
    {
        if (qp == NULL || qp->num <= 0) // qp未初始化或队列内无元素
        {
            return 0;
        }
    
        *data_ptr = qp->array[qp->head]; // 出队
        qp->head = (qp->head + 1) % (qp->size); // 循环队列
        --qp->num;
    
        return 1;
    }
    
    // 检测队列是否为空
    int QUEUEempty(QUEUE* qp)
    {
        if (qp == NULL || qp->num <= 0)
        {
            return 1;
        }
    
        return 0;
    }
    
    // 销毁队列
    void QUEUEdestroy(QUEUE* qp)
    {
        free(qp->array);
        free(qp);
    }
    // 以上是队列的有关操作实现
    
    // 生成多叉树节点
    NODE* create_node()
    {
        NODE* q;
    
        q = (NODE*)util_malloc(sizeof (NODE));
        q->n_children = 0;
        q->level      = -1;
        q->children   = NULL;
    
        return q;
    }
    
    // 按节点名字查找
    NODE* search_node_r(char name[M], NODE* head)
    {
        NODE* temp = NULL;
        int i = 0;
    
        if (head != NULL)
        {
            if (strcmp(name, head->name) == 0) // 如果名字匹配
            {
                temp = head;
            }
            else // 如果不匹配,则查找其子节点
            {
                for (i = 0; i < head->n_children && temp == NULL/*如果temp不为空,则结束查找*/; ++i)
                {
                    temp = search_node_r(name, head->children[i]); // 递归查找子节点
                }
            }
        }
    
        return temp; // 将查找到的节点指针返回,也有可能没有找到,此时temp为NULL
    }
    
    // 从文件中读取多叉树数据,并建立多叉树
    void read_file(NODE** head, char* filename)
    {
        NODE* temp = NULL;
        int i = 0, n = 0;
        char name[M], child[M];
        FILE* fp;
    
        fp = util_fopen(filename, "r"); // 打开文件
    
        while (fscanf(fp, "%s %d", name, &n) != EOF) // 先读取节点名字和当前节点的子节点个数
        {
            if (*head == NULL) // 若为空
            {
                temp = *head = create_node();   // 生成一个新节点
                temp->name = util_strdup(name); // 赋名
            }
            else
            {
                temp = search_node_r(name, *head); // 根据name找到节点
                // 这里默认数据文件是正确的,一定可以找到与name匹配的节点
                // 如果不匹配,那么应该忽略本行数据
            }
            // 找到节点后,对子节点进行处理
            temp->n_children = n;
            temp->children   = (NODE**)malloc(n * sizeof (NODE*));
            if (temp->children == NULL) // 分配内存失败
            {
                fprintf(stderr, "Dynamic allocation error!\n");
                exit(EXIT_FAILURE);
            }
    
            // 如果分配成功,则读取后面的子节点,并保存
            for (i = 0; i < n; ++i)
            {
                fscanf(fp, "%s", child); // 读取子节点
                temp->children[i] = create_node(); // 生成子节点
                temp->children[i]->name = util_strdup(child); // 读子节点赋名
            }
        }
    
        // 读取完毕,关闭文件
        fclose(fp);
    }
    
    // 实现函数1
    // 将多叉树中的节点,按照深度进行输出
    // 实质上实现的是层次优先遍历
    void f1(NODE* head)
    {
        NODE* p = NULL;
        QUEUE* q = NULL; // 定义一个队列
        STACK* s = NULL; // 定义一个栈
        int i = 0;
    
        q = QUEUEinit(100); // 将队列初始化大小为100
        s = STACKinit(100); // 将栈初始化大小为100
    
        head->level = 0; // 根节点的深度为0
        
        // 将根节点入队列
        QUEUEenqueue(q, head);
    
        // 对多叉树中的节点的深度值level进行赋值
        // 采用层次优先遍历方法,借助于队列
        while (QUEUEempty(q) == 0) // 如果队列q不为空
        {
            QUEUEdequeue(q, &p); // 出队列
            for (i = 0; i < p->n_children; ++i)
            {
                p->children[i]->level = p->level + 1; // 对子节点深度进行赋值:父节点深度加1
                QUEUEenqueue(q, p->children[i]);      // 将子节点入队列
            }
            STACKpush(s, p); // 将p入栈
        }
    
        while (STACKempty(s) == 0) // 不为空
        {
            STACKpop(s, &p); // 弹栈
            fprintf(stdout, "   %d %s\n", p->level, p->name);
        }
    
        QUEUEdestroy(q); // 消毁队列
        STACKdestroy(s); // 消毁栈
    }
    
    // 实现函数2
    // 找到从根节点到叶子节点路径上节点名字字母个数最大的路径
    // 实质上实现的是深度优先遍历
    void f2(NODE* head, char* str, char** strBest, int level)
    {
        int   i   = 0;
        char* tmp = NULL;
    
        if (head == NULL)
        {
            return;
        }
    
        tmp = (char*)util_malloc((strlen(str) + strlen(head->name) + 1/*原程序中未加1*/) * sizeof (char));
        sprintf(tmp, "%s%s", str, head->name);
    
        if (head->n_children == 0)
        {
            if (*strBest == NULL || strlen(tmp) > strlen(*strBest))
            {
                free(*strBest);
                *strBest = util_strdup(tmp);
            }
        }
    
        for (i = 0; i < head->n_children; ++i)
        {
            f2(head->children[i], tmp, strBest, level + 1);
        }
    
        free(tmp);
    }
    
    // 消毁树
    void free_tree_r(NODE* head)
    {
        int i = 0;
        if (head == NULL)
        {
            return;
        }
    
        for (i = 0; i < head->n_children; ++i)
        {
            free_tree_r(head->children[i]);
        }
    
        free(head->name);
        // free(head->children); // 消毁子节点指针数组
        free(head);
    }
    
    
    int main(int argc, char* argv[])
    {
        NODE* head = NULL;
        char* strBest = NULL;
    
        if (argc != 2)
        {
            fprintf(stderr, "Missing parameters!\n");
            exit(EXIT_FAILURE);
        }
    
        read_file(&head, argv[1]);
    
        fprintf(stdout, "f1:\n");
        f1(head);
        f2(head, "", &strBest, 0);
        fprintf(stdout, "f2:\n   %s\n", strBest);
    
        free_tree_r(head);
    
        return EXIT_SUCCESS;
    }


    其他: https://my.oschina.net/u/1179554/blog/376524

    ---------------------------------------------------------------------------------------------------------------------------------------------------------

    深度优先遍历

     

    1.深度优先遍历的递归定义

     

      假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。

      图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历

     

    2.基本实现思想:

    (1)访问顶点v;

    (2)从v的未被访问的邻接点中选取一个顶点w,从w出发进行深度优先遍历;

    (3)重复上述两步,直至图中所有和v有路径相通的顶点都被访问到。

     

    3.伪代码

    递归实现

    1)访问顶点v;visited[v]=1;//算法执行前visited[n]=0

    (2)w=顶点v的第一个邻接点;

    (3)while(w存在)  

               if(w未被访问)

                       从顶点w出发递归执行该算法; 
               w=顶点v的下一个邻接点;

     

    非递归实现

     (1)栈S初始化;visited[n]=0;

     (2)访问顶点v;visited[v]=1;顶点v入栈S

     (3)while(栈S非空)

                x=栈S的顶元素(不出栈);

                if(存在并找到未被访问的x的邻接点w)

                        访问w;visited[w]=1;

                        w进栈;

                else

                         x出栈;

     

     

    广度优先遍历

     

    1.广度优先遍历定义

     

     图的广度优先遍历BFS算法是一个分层搜索的过程,和树的层序遍历算法类同,它也需要一个队列以保持遍历过的顶点顺序,以便按出队的顺序再去访问这些顶点的邻接顶点。 

    2.基本实现思想

     

    (1)顶点v入队列。

    (2)当队列非空时则继续执行,否则算法结束。

    (3)出队列取得队头顶点v;访问顶点v并标记顶点v已被访问。

    (4)查找顶点v的第一个邻接顶点col。

    (5)若v的邻接顶点col未被访问过的,则col入队列。

    (6)继续查找顶点v的另一个新的邻接顶点col,转到步骤(5)。

            直到顶点v的所有未被访问过的邻接点处理完。转到步骤(2)。

    广度优先遍历图是以顶点v为起始点,由近至远,依次访问和v有路径相通而且路径长度为1,2,……的顶点。为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问,需设置队列存储访问的顶点。

     

     

    3.伪代码

    (1)初始化队列Q;visited[n]=0;

    (2)访问顶点v;visited[v]=1;顶点v入队列Q;

    (3) while(队列Q非空)   

                  v=队列Q的对头元素出队;

                  w=顶点v的第一个邻接点;

                 while(w存在) 

                         如果w未访问,则访问顶点w;

                         visited[w]=1;

                         顶点w入队列Q;

                         w=顶点v的下一个邻接点。



    
    
    展开全文
  • 一种多叉树的前序遍历C实现算法代码例子 在偶然的机会间涉及到了要对某些多未知数多方程求解其中的多数公因式的工程,然后在寻找他们的公因式时需要对其所有因式进行查找对比,由此自己感兴趣地花了几个时间写了一个...

    一种多叉树的前序遍历C实现算法代码例子

    在偶然的机会间涉及到了要对某些多未知数多方程求解其中的多数公因式的工程,然后在寻找他们的公因式时需要对其所有因式进行查找对比,由此自己感兴趣地花了几个时间写了一个小代码实现其寻找,其剖析开来就是多叉树的前序遍历算法,其中也没使用到指针,但是也是多叉树的数据结构。
    我先介绍一下我当时面对的对象。如下方程式

    a=b+c(d+e+t)-f(g+h(i+j));

    大概是形同这样的若干个的方程式子,其中每个字母可看作一个因式,或者他们结合成因式,然后主要是对他们进行遍历查找其每个因式。
    其多叉树结果如下;

    a
    b
    c<d+e+t>
    -f<g+h<i+j>>
    c
    d+e+t
    d
    e
    t
    -f
    g+h<i+j>
    h<i+j>
    g
    h
    i+j
    i
    j

    针对上叙提出了前序遍历的c实现,使用双向链表:

        struct Node
        {
        	char equation;
    		int brother_sum;//节点的字节点数 
        	int father; //父节点号 
        } ;
        struct Node node[][];
        struct Node current[][];
    	int nest = 0;
    	int j = 1;
    	int A,LA,i,b,c,k,u; 
    	k=1;
    	current.equation = A;
    	current.rank =1;
    	current.brother_sum = 1;
    	while(nest>=0)//返回父节的兄弟点循环 
    	 {
    		   for(j=2;j<=(current.brother_sum+1);j++)//兄弟节点循环 
    			{ 	
    				while(length(current.equation) > 1)//当前节点判断空非空循环 
    				{				
    						nest++;//深度数自加 
    						for(m=1;m<=length(current.equation);m++)//循环创建子节点信息 
    						{
    							child = take_child(current.equation,m);//取当前节点的子节点 
    							node[nest][m].equation = child;//子节点自己信息
    							node[nest][m].brother_sum = length(current.equation);//子本节点有多少个兄弟节点 
    							node[nest][m].father = current.rank;//当前节点排行
    						} 
    						current.brother_sum = length(current.equation);//当前节点兄弟数 
    						current.equation = node[nest][1].equation;//当前分析节点替换为子节点
    						current.father =  current.rank;//当前节点的父亲排行 
    						current.rank = 1;//当前节点在兄弟里的排行  			
    				}
    				current.equation = node[nest][j].equation;//当前节点为上一节点的兄弟 
    				current.rank = j;//当前节点兄弟排行 		
    			}
    			nest--;//返回父亲层 
    			if(nest=0)break;
    			current.equation =  node[nest][current.father+1].equation;//取父亲的兄弟的信息 
    			current.rank =  current.father+1;//取父亲的兄弟排行
    			current.brother_sum =  node[nest][current.father].brother_sum;		
    	}
    

    程序详解,下次再说吧(^ . ^)

    展开全文
  • 多叉树的建立是以前没有遇到过的 可以有这样的一个数据结果 一个结构体:里面保存一些这个节点的信息,以及定义一个vector,vector里面是孩子的信息,既可以是数组实现的动态分配的节点编号,也可以直接在里面装...
  • 关于多叉树的遍历。

    千次阅读 2019-06-26 16:34:49
    经过了一番查询与思考。目前把平常见的Tree的遍历分成3种情况。 递归遍历。非递归广度优先遍历。非递归深度优先遍历。...而非递归广度优先去遍历一个多叉树要用到 队列 这个东西。 目前java 的linkedList 实现了Qu...
  • 看到题目第一时间想到树,而且是多叉树。为什么呢?  首先说说为何不选择顺序表,我们来试想想,如果500万个单词放在顺序表上,不加索引而且乱序,那么搜索一个关键词为开头的单词的时间按最差算要500万次比较,...
  • 本文研究的是如何对一个多叉树进行全路径的遍历,并输出全路径结果。该问题的研究可以用在:Trie树中查看所有字典值这个问题上。本文将对该问题进行详细的模拟及进行代码实现,讨论了递归和非递归两种方法优劣并分别...
  • c语言 多叉树结构相关

    千次阅读 2009-05-31 17:34:00
    实现多叉树时,由于非叶子节点的子节点的个数不同,所以如何动态的创建节点是个问题数据结构:struct list{ /* other data */ int effectif_class_1; int effectif_class_2; struct list *parent; struct list *child...
  • 数据结构之多叉树c实现DFS和BFS

    千次阅读 2016-12-10 20:14:44
    // 从文件中读取多叉树数据,并建立多叉树 void read_file(NODE** head, char * filename) { NODE* temp = NULL; int i = 0 , n = 0 ; char name[MaxLenOfName], child[MaxLenOfName]; FILE* fp; fp...
  • 项目上遇到了一个典型的多叉树应用案例, 记录一下。 (1) //结构 typedef struct st_OriTree { int levelValue; //树的level int orderValue; //排序值 QString nameValue; //当前节点名称 QString ...
  • A family hierarchy is ... } 总结 多叉树的子树需要链式结构储存,按层遍历多叉树用层序遍历较好; 层序遍历同时需要 int End=1; //指向当前出队层的最后一个 int temp; //指向入队那层的最后一个 两个变量辅助;
  • 遍历多叉树

    千次阅读 2018-09-29 10:37:33
    ...  beg4 关注 2018.03.22 15:14* 字数 334 阅读 172评论 0喜欢 1 ...随便画一个,写代码遍历它 OK,的结构这么描述 public class TreeNode { private String name; private TreeNo...
  • 实现一棵多叉树 实现一棵多叉树 这棵树可以有任意多颗子树 0-n 1 2 3 4 5 6 7 8 输入建立二叉树,输入的格式是每个节点的具体数据和拥有的孩子数目 例如上面的树是这样建成的: 1 3 2 2 5 0 6 0 3 1 7 0 4 1 8...
  • 多叉树

    万次阅读 2014-04-24 16:54:49
    原因有二:其一,二叉树是一个树的特例,掌握了二叉树很难以平移到多叉树;其二,二叉树不是一个非常好的数据结构,尽管非常的简单,仍需融入多叉树的性质。 1.1 介绍 1.2 定义 树的每个节点可以...
  • 多叉树的遍历,可以打印出树形结构,也可以只打印叶节点,或打印指定层的节点(一位德国教授写的文章)可以按照文章中给的网址下载源代码,
  • 在做项目的过程中,遇到了多叉树的访问问题,其中要求保存访问至叶子节点的路径,查找网上资料都不是很合心意,故而自己用比较笨的方法保存然后输出 多叉树结构: class DataModel { public string name { get; ...
  • Problem Description Given n labeled vertices, there are nn-2 different trees. The number is too large, but Wiskey want to use a way to encode the tree that make a unique sequence associated with the ...
  • 多叉树的实现

    千次阅读 2013-04-29 21:43:55
    多叉树的结点: template struct multreenode{ T data; //数据 multreenode *parent; //父节点 multreenode *left; //左兄弟 multreenode *right; //又兄弟 multreenode *firstChild,*lastChild; //...
  • 简单的遍历一个形结构数据的几种方法、非递归方法效率最好。 (function (window, undefined) { var treeNodes = [ { id: 1, name: '1', children: [ ...
  • 多叉树的递归和非递归遍历

    万次阅读 2016-04-10 21:58:02
     图的广度优先遍历BFS算法是一个分层搜索的过程,和的层序遍历算法类同,它也需要一个队列以保持遍历过的顶点顺序,以便按出队的顺序再去访问这些顶点的邻接顶点。  2.基本实现思想   (1)顶点...
  • 算法思路主要是先遍历整棵,然后构造出一个哈希表,哈希表里的每个元素都是一个对象(对应c语言里的一个结构体),构造完哈希表之后,以后的每次查找都可以直接从哈希表里找出需要查找的节点,在遍历的过程中把每个...
  • 数据结构之多叉树的定义

    千次阅读 2013-08-17 11:15:52
    利用List构建 import java.util.ArrayList; import java.util.List; /** * 节点 * * @author Oliver * */ public class TreeNode { private String data; private TreeNode parentNode; private ...
  • 多叉树求最优解问题

    2017-07-07 20:36:48
    多叉树求最优解问题
  • Problem Description Given n labeled vertices, there are nn-2 different trees. The number is too large, but Wiskey want to use a way to encode the tree that make a unique sequence associated with the ...
  • #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; typedef struct kk { char ch; int flag; struct kk *left; struct kk *right; }btree; typedef struct stack ... ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 668
精华内容 267
关键字:

c语言多叉树

c语言 订阅