【数据结构】-二叉树(链式存储)

超、凢脫俗 2023-03-02 10:07 49阅读 0赞

### 二叉链表 ###

*  1.头文件及类型定义
 *  2.二叉链表结点类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 先序建立二叉树
     *  4.2 求树的深度
     *  4.3 寻找中序前驱
     *   *  4.3.1 辅助全局变量
         *  4.3.2 访问结点
         *  4.3.3 遍历
     *  4.4 main函数
     *  4.5 测试
     *   *  4.5.1 二叉树结构
         *  4.5.2 测试结果
 *  5.小结

# 1.头文件及类型定义 #

#include<stdio.h>
    #include<stdlib.h>
    #define ElemType char

# 2.二叉链表结点类型定义 #

//二叉链表结点类型定义
    typedef struct BiTNode {
        
    	ElemType data;		//结点中的数据域
    	struct BiTNode* lchild, * rchild;	//左右孩子指针
    }BiTNode, * BiTree;

# 3.函数声明 #

/*函数声明*/
    void CreateBiTree(BiTree& T);	//1.先序建立二叉树
    int TreeDepth(BiTree T);		//2.求树的深度
    void visit(BiTNode* q);			//3-1.找中序前驱-访问结点
    void FindPre(BiTree T);			//3-2.找中序前驱-中序遍历

# 4.基本操作 #

## 4.1 先序建立二叉树 ##

//1.先序建立二叉树
    void CreateBiTree(BiTree& T) {
        
    	char c;
    	scanf("%c", &c);
    	if (c == '#')
    		T = NULL;
    	else {
        
    		T = (BiTNode*)malloc(sizeof(BiTNode));
    		T->data = c;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }

## 4.2 求树的深度 ##

//2.求树的深度(实质上是后序遍历)
    int TreeDepth(BiTree T) {
        
    	if (T == NULL)
    		return 0;
    	else {
        
    		int l = TreeDepth(T->lchild);		//递归求出左子树深度
    		int r = TreeDepth(T->rchild);		//递归求出右子树深度
    		return l > r ? l + 1 : r + 1;		//树的深度=Max(左子树深度，右子树深度)+1 
    	}
    }

## 4.3 寻找中序前驱 ##

### 4.3.1 辅助全局变量 ###

//3-1辅助全局变量，用于查找p的前驱
    BiTNode* p;					//p指向目标结点
    BiTNode* pre = NULL;		//pre指向当前访问结点的前驱
    BiTNode* final = NULL;		//用于记录最终结果

### 4.3.2 访问结点 ###

//3-2.找前驱-访问
    void visit(BiTNode* q) {
        
    	if (q == p)			//当前访问结点刚好是p
    		final = pre;	//找到p的前驱，用final记录
    	else
    		pre = q;		//pre指向当前访问的结点，继续递归
    }

### 4.3.3 遍历 ###

//3-3.中序前驱-遍历
    void FindPre(BiTree T) {
        
    	if (T != NULL) {
        
    		FindPre(T->lchild);		//递归遍历左子树
    		visit(T);				//访问根结点
    		FindPre(T->rchild);		//递归遍历右子树
    	}
    }

## 4.4 main函数 ##

int main() {
        
    	BiTree T;	//声明一个二叉树
    
    	/*1、先序创建二叉树*/
    	printf("先序创建二叉树：");
    	CreateBiTree(T);	
    
    	/*2、求二叉树的深度*/
    	printf("该二叉树的深度为：%d\n", TreeDepth(T));
    
    	/*3、寻找指定结点的在中序遍历中的前驱*/
    	p = T;			//此处仅用根结点作测试
    	FindPre(T);
    	printf("根结点的中序前驱为：%c", final->data);
    }

## 4.5 测试 ##

### 4.5.1 二叉树结构 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70]

### 4.5.2 测试结果 ###

![在这里插入图片描述][2020072817090018.png]

# 5.小结 #

1.  **关于二叉树的顺序存储**  
    根据二叉树的性质，**完全二叉树和满二叉树适合顺序存储**。对于一般的二叉树来说，顺序存储的空间利用率较低，因此，*二叉树一般都采用链式存储结构*。因此，顺序存储的二叉树不做介绍。
2.  **关于二叉树的链式存储**  
    对于链式存储结构的二叉树，用链表结点来存储二叉树中的每个结点。因此，链式存储的二叉树又叫二叉链表。本文简单介绍了二叉链表的先序创建、求树的深度、求中序前驱，其中，关于上述中序前驱的操作仍有不足，在后续文章会继续介绍。
3.  重要结论  
    *在含有**n个结点**的二叉链表中，含有**n+1个空链域**。*  
    这个结论非常重要，后续的文章中将会利用这些空链域来组成另一种链表结构——线索链表。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70]: /images/20230208/51cbc4893dad42b6921467af2e969f81.png
[2020072817090018.png]: /images/20230208/49af92ea05664d3392eb83a089807eed.png