郝斌数据结构6树

太过爱你忘了你带给我的痛 2022-03-02 14:52 194阅读 0赞

1 树的定义  
专业定义：有且只有一个称为根的节点；有若干个互不相交的子树，这些树本身也是一棵树  
通俗的定义：树是由节点和边组成；每个节点只有一个父节点但可以有多个子节点；但有一个节点没有父节点，它叫做根节点

2 树的专业术语  
节点、父节点、子节点、子孙、堂兄弟  
深度：从根节点到最底层节点的层数称之为深度，根节点是第一层  
叶子节点：没有子节点的节点  
非终端节点：实际就是非叶子节点  
度：子节点的个数

3 树的分类  
》》一般树：任意一个节点的子节点的个数都不受限制  
》》二叉树：任意一个节点的子节点的个数最多两个，且子节点的位置不可更改  
分类：  
》》一般二叉树  
》》满二叉树  
在不增加树的层数的前提下，无法再多添加；一个节点的二叉树就是满二叉树  
》》完全二叉树  
如果只是删除了满二叉树最底层最右边的连续若干个点，这样形成的二叉树就是完全二叉树  
满二叉树是完全二叉树的一个特例，就是完全一个都不删就是满  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]  
》》森林：n个互不相交的树的集合

4 二叉树的连续存储  
连续存储->必须转化成完全二叉树进行  
优点：查找某个节点的父节点和子节点（也包括有没有子节点）速度很快  
缺点：耗用内存空间过大

5 二叉树的链式存储

6 一般树的存储  
》》双亲表示法  
》》孩子表示法  
》》双亲孩子表示法  
》》二叉树表示法：把一个普通树转化成二叉树来存储  
具体转换方法：设法保证任意一个节点的左指针域指向它的第一个孩子，右指针域指向它的下一个兄弟。只要能满足此条件，就可以把一个普通的胡转换成二叉树。  
一个普通树转换成的二叉树根节点一定没有右子树  
例子:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20190320175221690.png]  
7 森林的存储

8 先序遍历：【先访问根节点】  
先访问根节点，再先序访问左子树，再先序访问右子树。  
例子1：  
![在这里插入图片描述][20190320175245649.png]  
先：ABDCEFG  
例子2：  
![在这里插入图片描述][20190320175310306.png]  
先：ABCDEFLQMNS  
9 二叉树的中序遍历【中间访问根节点】  
中序遍历左子树，再访问根节点，再中序遍历右子树  
例子1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 2]  
例子2：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 3]  
10 二叉树的后序遍历【最后访问根节点】  
后序遍历左子树，后序遍历右子树，最后访问根节点  
例子1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 4]  
例子2：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 5]  
11 已知两种遍历序列求原始二叉树概述  
通过先序和中序或者中序和后序我们可以还原出原始的二叉树，但是通过先序和后序是无法还原出原始的二叉树的。  
换种说法，只有通过先序和中序，或通过中序和后序，也就是中序必须存在，我们才能唯一的确定一个二叉树。

12 已知先序和中序求后序  
例子1：先序ABCDEFGH 中序BDCEAFHG  
分析： BDCE A FHG 左边是左子树，右边是右子树  
![在这里插入图片描述][20190320183940987.png]  
后序是DECBHGFA  
例子2：先序ABDGHCEFI 中序GDHBAECIF

分析： GDHB A ECIF 左边是左子树，右边是右子树  
![在这里插入图片描述][20190320184150506.png]  
后序：GHDBEIFCA  
13 已知中序和后序求先序  
中：BDCEAFHG 后：DECBHGFA

分析:通过后序知道A是根，通过中序知道BDCE A FHG 左边是左子树，右边是右子树

左子树BDCE在后序中哪个最后出现，哪个就是根节点，所以B是根节点。通过中序知道B没有左子树，在后序中C在最后面，所以C是B的右子树的根。  
FHG中可以F没有左子树，F在后序中最后出现，所以F是A的右子树的根。HG中G在后序中最后面，所以G是F的右子树的根。  
![在这里插入图片描述][20190320184238361.png]  
先序：ABCDEFGH  
14 二叉树的程序

//main.c:
    #include <stdio.h>
    #include <stdlib.h>
    #include "bitree.h"
    #include "linkqueue.h"
    
    int main(int argc, const char *argv[])
    { 
    	bitree *r = NULL;
    
    	if (NULL == (r = bitree_create()))
    	{ 
    		printf("FILE:%s,LINE:%d,bitree_create failed\n",__FILE__,__LINE__);
    		return -1;
    	}
    
    	preorder(r);//先序遍历
    	putchar(10);
    
    	inorder(r);//中序遍历
    	putchar(10);
    
    	postorder(r);//后序遍历
    	putchar(10);
    
    	noorder(r);//层序遍历,用链式队列实现
    	putchar(10);
    
    	return 0;
    }
    
    //bitree.h:
    #ifndef _BITREE_H_
    #define _BITREE_H_
    
    typedef char datatype_t;
    typedef struct node_t
    { 
    	datatype_t data;
    	struct node_t *lchild;
    	struct node_t *rchild;
    }bitree;
    
    bitree * bitree_create();
    void preorder(bitree *);
    void inorder(bitree *);
    void postorder(bitree *);
    void noorder(bitree *);
    #endif
    
    linkqueue.h:
    #ifndef _LINKQUEUE_H_
    #define _LINKQUEUE_H_
    #include "bitree.h"
    
    typedef bitree * datatype;
    typedef struct node
    { 
    	datatype data;
    	struct node *next;
    }linknode;
    
    typedef struct
    { 
    	struct node *front;
    	struct node *rear;
    }queue;
    
    queue *queue_create();
    int enqueue(queue *lq,datatype value);
    datatype dequeue(queue *lq);
    int queue_empty(queue *lq);
    
    #endif
    
    //bitree.c:
    #include <stdio.h>
    #include <stdlib.h>
    #include "bitree.h"
    #include "linkqueue.h"
    
    bitree * bitree_create()
    { 
    	char ch;
    	bitree *r = NULL;
    	scanf("%c",&ch);
    
    	if ('#' == ch)
    	{ 
    		return NULL;
    	}//除了一开始就就输入NULL，这个NULL返回到主函数，往后进入递归，
    	//这个NULL返回到上一层的bitree_create()
    
    	if (NULL == (r = malloc(sizeof(bitree))))
    	{ 
    		printf("FILE:%s,LINE:%d,malloc failed\n",__FILE__,__LINE__);
    		return NULL;
    	}
    	//创建是按照先序遍历的方式创建
    	r->data = ch;
    	r->lchild = bitree_create();//递归
    	r->rchild = bitree_create();
    
    	return r;
    }
    
    void preorder(bitree *r)
    { 
    	if (r == NULL)
    	{ 
    		return;
    	}//这个NULL是下面的递归的preorder()中的r->l/rchild可能是NULL
    
    	printf("%c ",r->data);
    	preorder(r->lchild);
    	preorder(r->rchild);
    }
    
    void inorder(bitree *r)
    { 
    	if (NULL == r)
    	{ 
    		return;
    	}
    
    	inorder(r->lchild);
    	printf("%c ",r->data);
    	inorder(r->rchild);
    }
    
    void postorder(bitree *r)
    { 
    	if (NULL == r)
    	{ 
    		return;
    	}
    
    	postorder(r->lchild);
    	postorder(r->rchild);
    	printf("%c ",r->data);
    }
    
    void noorder(bitree *r)
    { 
    	queue *lq = NULL;
    	bitree *p = NULL;
    
    	if (NULL == (lq = queue_create()))
    	{ 
    		printf("FILE:%s.LINE:%d,queue_creat failed\n",__FILE__,__LINE__);
    		return;
    	}
    
    	printf("%c ",r->data);
    	enqueue(lq,r);
    
    	while (!queue_empty(lq))
    	{ 
    		p = dequeue(lq);
    
    		if (p->lchild != NULL)
    		{ 
    			printf("%c ",p->lchild->data);
    			enqueue(lq,p->lchild);
    		}
    
    		if (p->rchild != NULL)
    		{ 
    			printf("%c ",p->rchild->data);
    			enqueue(lq,p->rchild);
    		}
    
    	}
    }
    
    //linkqueue.c:
    #include <stdio.h>
    #include <stdlib.h>
    #include "linkqueue.h"
    #include "bitree.h"
    
    queue* queue_create()
    { 
    	linknode *p = NULL;
    	queue *lq = NULL;
    
    	if (NULL == (p = malloc(sizeof(linknode))))
    	{ 
    		printf("FILE:%s,LINE:%d,malloc node failed\n",__FILE__,__LINE__);
    		return NULL;
    	}
    
    	if (NULL == (lq = malloc(sizeof(queue))))
    	{ 
    		printf("FILE:%s,LINE:%d,malloc queue failed\n",__FILE__,__LINE__);
    		return NULL;
    	}
    
    	lq->front = p;
    	lq->rear = p;
    
    	return lq;
    }
    
    int enqueue(queue *lq,datatype value)
    { 
    	linknode *p = NULL;
    
    	if (NULL == (p = malloc(sizeof(linknode))))
    	{ 
    		printf("FILE:%s,LINE:%d,malloc node failed\n",__FILE__,__LINE__);
    		return -1;
    	}
    
    	p->data = value;
    	p->next = NULL;
    
    	lq->rear->next = p;
    	lq->rear = p;
    
    	return 0;
    }
    
    datatype dequeue(queue *lq)
    { 
    	linknode *p = NULL;
    	datatype t;
    
    	if (queue_empty(lq))
    	{ 
    		printf("queue is empty\n");
    		return NULL;
    	}
    
    	p = lq->front;
    	lq->front = p->next;
    	t = lq->front->data;
    	free(p);
    	p = NULL;
    
    	return t;
    }
    
    int queue_empty(queue *lq)
    { 
    	return lq->front == lq->rear;
    }

运行结果:  
我如果想创造这样的二叉树  
![在这里插入图片描述][20190320184446930.png]  
就这样输入  
![在这里插入图片描述][20190320184507545.png]  
输入的时候注意问题:不要输入A回车B回车D……这样输入是得不出结果的，因为  
![在这里插入图片描述][20190320184532500.png]  
scanf()这里使用%c输入，第一次scanf()接收的是A，递归进入的scanf()接收的不是B，而是A完后的回车……scanf()使用%c输入的问题一定要注意！  
我如果想创造这样的二叉树  
![在这里插入图片描述][201903201845539.png]  
就这样输入  
![在这里插入图片描述][20190320184611331.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]: /images/20220302/b4ff1637237f46a0ad51609c857c79be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 1]: /images/20220302/3f887c1fcb9c47fbaded24c45153e175.png
[20190320175221690.png]: /images/20220302/c42d43cc09e248c4853a72d893f49d35.png
[20190320175245649.png]: /images/20220302/93dc8ca596034936b2dd6089fca47f31.png
[20190320175310306.png]: /images/20220302/bcbb7416a219488cbc82cce3f61388e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 2]: /images/20220302/3e9bb1b50b9e4293bd1bb1b67194531e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 3]: /images/20220302/11276ac9733448f98e4f7b9f01d6c5a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 4]: /images/20220302/e09bc6c8645e40018aadd4585efd4f36.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 5]: /images/20220302/e4d3748dc8f44e5a998831384122ade7.png
[20190320183940987.png]: /images/20220302/5f63a928b290405d8b23a5bd6e5c6ce2.png
[20190320184150506.png]: /images/20220302/c62bc8b9b36b426eb8aec46aa48959e8.png
[20190320184238361.png]: /images/20220302/53b503dafca04db9ac860e09a241804c.png
[20190320184446930.png]: /images/20220302/2578f24fb0be4bffa28665eca92e9275.png
[20190320184507545.png]: /images/20220302/42b4dd068aca49ae979182e32a65716e.png
[20190320184532500.png]: /images/20220302/20117ccd75f94088873320a4d1e64e55.png
[201903201845539.png]: /images/20220302/39e4dc73a07548a39e8a05606757952d.png
[20190320184611331.png]: /images/20220302/2b86ca2a816b4442b215536dec8c8a83.png