数据结构浙大陈姥姥版第三章

矫情吗；* 2023-06-30 08:46 7阅读 0赞

### 文章目录 ###

*  引子
 *   *  什么是树
     *  查找(Searching)
     *   *  静态查找（查字典）
         *  动态查找
 *  树(Tree)
 *   *  树的定义：
     *   *  树与非树
         *  树的一些基本术语
     *  树的表示
     *   *  二叉树（儿子-兄弟表示法）
 *  二叉树
 *   *   *  二叉树的定义
         *  二叉树的几个重要性质
         *  二叉树的抽象数据类型定义
         *  二叉树的存储结构
         *  二叉树的遍历
         *  二叉树的非递归遍历
         *   *  中序遍历非递归遍历算法
         *  层次遍历

# 引子 #

## 什么是树 ##

树：

客观世界中许多事物的**层次关系**

*  家谱
 *  社会组织结构
 *  图书信息管理

为什么要用到树：

分层次组织在管理上效率更高

数据管理的基本操作之一： 查找

## 查找(Searching) ##

给某个关键字K，从集合R中找到关键字与K相同的记录

### 静态查找（查字典） ###

在数组里面查找元素

方法一： 顺序查找

int SequentialSearch (List Tbl, ElementType K)
    { 
    	int i;
    	Tbl->Element[0] = K;//建立哨兵
        //无哨兵
        //for(i = Tbl->Length; i > 0 && Tbl -> Element[i] != K; i--);
    	for(i = Tbl->Length; Tbl->Element[i]!=K; i--);
    	return i;
    }
    typedef struct LNode *List;
    struct LNode{ 
        ElementType Element[MAXSIZE];
        int Length;
    }

方法二： 二分查找(Binary Search)

电话线 杭州到上海的电线杆

前提条件

1.  假设n个数据元素的关键字满足有序（比如从小到大）
2.  并且是连续存放（数组）

### 动态查找 ###

# 树(Tree) #

## 树的定义： ##

n(n >= 0)个结点构成的有限集合。

当n = 0时，为空树

对于任意非空树：

树中有一个称为”根"(Root)，的特殊结点，用r表示；

其余结点分为m个互不交相的有限集，每个集合本身又是一棵树，称为原来的“子树”(SubTree)

### 树与非树 ###

*  子树互不相交
 *  除了根结点，每个结点有且仅只有一个父节点（往上的边只有一条）
 *  一棵N个结点的树有N - 1条边

**树是保证结点连通的边最少的的一种连接方式**

### 树的一些基本术语 ###

1.  结点的度(Degree)：结点的子树个数
2.  树的度：树的所有结点中最大的度数
3.  叶结点(Leaf)：度为0的结点，没有子树的结点
4.  父结点(Parent)：
5.  子结点(Child)：若A结点是B结点的父结点，则称B结点是A结点的子结点
6.  兄弟结点(Sibling)：具有同一父结点的各节点彼此都是兄弟结点
7.  路径和路径的长度：
8.  祖先结点(Ancestor)：树根
9.  子孙结点(Descendant)：某一结点的子树中的所有结点是这个结点的子孙
10. 结点的层次(Level)：规定根结点在1层，其他任一结点的层数是其父结点的层数加1
11. 树的深度(Depth)：树中所有结点中的最大层次是这个树的深度

## 树的表示 ##

### 二叉树（儿子-兄弟表示法） ###

# 二叉树 #

### 二叉树的定义 ###

二叉树T：一个有穷的结点集合

这个集合可以为空

若不为空，则它是由**根结点**和其**左子树T\_L**和**右子树T\_R**的两个不相交的二叉树组成

*  二叉树有5种基本形态
 *  二叉树的子树有左右顺序之分

### 二叉树的几个重要性质 ###

*  一个二叉树第i层的最大结点树为：2^(i-1),i >= 1
 *  深度为k的二叉树的最大结点**总数**为：(2^k) -1, k>=1
 *  对任何非空二叉树T，若n\_0表示叶结点的个数、n\_2是度为2的非叶结点个数，那么两者满足关系n\_0 = n\_2 + 1

### 二叉树的抽象数据类型定义 ###

**类型名称**： 二叉树

数据对象集：一个有穷的结点集合

操作集

常见的遍历方法：

*  void PreOrderTraversal(BinTree BT): 先序—根、左子树、右子树
 *  void InOrderTraversal(BinTree BT): 中序—左子树、根、右子树
 *  void PostOrderTraversal(BinTree BT): 后序—左子树、右子树、根
 *  void LevelOrdreTraversal(BinTree BT): 层次遍历—从上到下、从左到右

### 二叉树的存储结构 ###

1.  顺序存储结构
    
    完全二叉树：按从上到下、从左到右顺序存储n个结点
    
     *  非根结点的**父结点**的序号\*\*\[i/2\]\*\*
     *  结点 i 的左儿子的结点序号为 **2i**；右儿子序号为 **2i + 1**
    
    一般二叉树也可以采用这种结构，但会造成空间浪费
2.  链表存储

typedef struct TreeNode *BinTree;//结构指针
    typedef BinTree Position;//结构指针重命名为Position
    struct TreeNode{ 
    	ElementType Data;
    	BinTree Left;
    	BinTree Right;
    }

### 二叉树的遍历 ###

1）先序遍历

遍历过程：

*  访问根结点；
 *  先序遍历其左子树
 *  先序遍历其右子树

void PreOrderTraversal(BinTree BT)
    { 
    	if(BT){ 
    		printf("%d",BT->Data);//打印根节点
    		PreOrderTraversal(BT->Left);
    		PreOrderTraversal(BT->Right);
    		}
    }

2）中序遍历

遍历过程：

*  中序遍历其左子树
 *  访问根结点
 *  中序遍历其右子树

void InOrderTraversal(BinTree BT)
    { 
    	if(BT)
    	{ 
    		InOrderTraversal(BT->Left);
    		printf("%d", BT->Data);
    		InOrderTraversal(BT->Right);
    	}
    }

1.  后序遍历

遍历过程：

*  后序遍历其左子树
 *  后序遍历其右子树
 *  访问根结点

void PostOrderTraversal(BinTree BT)
    { 
    	if(BT)
    	{ 
    		PostOrderTraversal(BT->Left);
            PostOrderTraversal(BT->Right);
    		printf("%d", BT->Data);
    		
    	}
    }

### 二叉树的非递归遍历 ###

#### 中序遍历非递归遍历算法 ####

基本思想：**使用堆栈**

*  遇到一个结点，就把他压入栈，并去遍历它的左子树
 *  当左子树遍历结束后，从栈顶弹出这个结点并访问
 *  然后按右指针再去中序遍历该结点的右子树

void InOrderTraversal(BinTree BT)
    { 
    	BinTree T = BT;
    	Stack S = CreatStack(MaxSize);
    	while(T || !IsEmpty(S)){ 
    		while(T){ 
    			Push(S,T);
    			T = T->Left;
    		}
    		if(!IsEmpty(S)){ 
    			T = Pop(S);
    			printf("%5d", T->Data);
    			T = T->Right;
    		}
    	}
    }

### 层次遍历 ###

二叉树遍历的核心问题：二维结构的线性化

队列实现：

遍历从根结点开始，首先将根结点入队，

然后开始执行行循环：①结点出队、②访问该结点、③另其左右儿子入队

void LevelOrderTravesal(BinTree BT)
    { 
    	Queue Q; 
    	BinTree T;
    	if(!BT)
    		return;
    	Q = CreatQueue(MaxSize);//创建并初始化队列
    	AddQ(Q, BT);//把根结点放到队列里面
    	while(!IsEmptyQ(Q)){ 
    		T = DeleteQ(Q);//①从队列抛出元素
    		printf("%d\n", T->Data);//②访问去出队列的结点
    		if(T->Left)
    			AddQ(Q, T->Left);
    		if(T->Right)
    			Add(Q, T->Right);
    	}
    	
    }