第七天笔记

  • 树的概念和原理
  • 基本概念

日常生活中，很多数据的组织形式本质上是一棵树。比如一个公司中的职员层级关系、一个学校中的院系层级关系、淘汰赛中的各次比赛队伍、一个家族中的族谱成员关系等都是树状逻辑结构。由于树状结构表现出来都是具有层次的，因此也被称为层次结构。

树是一种非线性结构，其严格的数学定义是：如果一组数据中除了第一个节点（第一个节点称为根节点，没有直接前驱节点）之外，其余任意节点有且仅有一个直接前驱，有零个或多个直接后继，这样的一组数据形成一棵树。树中的数据元素之间的逻辑关系是一对多的。

所以树也属于数据结构的一种类型，其实树就是n个结点的有限集，当n=0的时候，此时树就被称为空树，如果是一颗非空树应该满足以下两个条件：

任意的非空树中有且只有一个特定的结点，该结点被称为根或称为根结点，也就是n = 1。

当n>1的时候，其余的结点可以分为m个（m>1）互不相交的有限集 T1、T2、T3………Tm ，每个集合也被称为一棵树，就是根的子树。

对于树状结构，除了根结点之外，其余的结点都可以分为多个不相交的子树，具体如下所示:

可以看到，结点A就是根结点，根结点A下面有两个子树，分别是子树B和子树H，另外结点B和H都是根结点A的子结点。

如果一个结点有子树，则该结点就被称为子树的“双亲”，该结点的子树就被称为结点的“孩子”，另外，具有相同结点的子树就被称为“兄弟”。

可以看到，结点A有2个子结点，分别是B和H，所以子树B和子树H的双亲就是结点A，同理，结点B和H就是结点A的孩子，并且结点B和H是兄弟。

从根结点到某个结点的路径上的所有结点，都被称为该结点的“祖先”，另外，以某个结点为根的子树中的所有结点都被称为该结点的“子孙”。

可以看到，结点D的祖先为A、B、C，结点G的祖先为H、A，另外对于子树B而言，结点C、D、E、F都是结点B的子孙。

一般把一个结点拥有子树的数量称为结点的度，把度为0的结点称为叶子结点，把度不为0的结点称为分支结点，也就是除了叶子结点之外的结点都是分支结点。

可以看到，结点A的度是2，结点B的度是1，结点H的度是2，结点C的度是3。结点D、E、F、G、I都是叶子结点，对于A、B、H、C都是分支结点。

树是分层结构，一般把树的根结点称为第一层，其余的子结点的层次就是在上一层的基础上+1，另外一般把树的最大层数称为树的深度。

可以看到，对于树A一共有4层，所以树A的深度就是4，对于子树B的深度是3，对于子树H的深度是2，树的深度也被称为树的高度。

  • 二叉树的种类说明

二叉树是另一种树状结构，二叉树的特点就是每个结点至多有两颗子树（每个结点的度不会超过2），并且二叉树的子树是有左右之分，如果有两颗子树，就分别叫做左子树和右子树，而且二叉树的子树是有次序的，不能随意更改的，所以二叉树也属于有序树，也就意味着哪怕二叉树只有一个子树，也要区分到底是左子树还是右子树。

二叉树也是n个（n>=0）结点的有限集，一般二叉树有5种形式，分别是空树、根结点（ROOT）、有根结点和左子树以及右子树、左子树（Left Child Tree）、右子树（Right Child Tree）。

  • 斜树

一般只有左子树的二叉树被称为左斜树，一般只有右子树的二叉树被称为右斜树，可以看到斜树退化为线性结构，所以斜树是没有体现二叉树的性能。

  • 满二叉树

一颗高度为h的二叉树，树的结点个数为 2h – 1个就被称为满二叉树，满二叉树所有的结点的度都是2，也就是每个结点都是有左子树和右子树，满二叉树的叶子结点的数量是最多的。另外，叶子结点都集中最下面一层。

  • 完全二叉树

对于一颗树而言，完全二叉树指的是只有树的最下面2层的结点的度可以小于2，并且结点的编号也是按照从上到下，从左到右的顺序进行排列，最下面一层的叶子结点都集中在左树。

可以知道满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树，大家需要注意。

  • 二叉查找树

二叉查找树英文缩写为BST树（Binary Search Tree），一般也被称为二叉搜索树或者二叉排序树，二叉查找树的结点是有键值key的，如果二叉查找树不是空树则需要遵循以下的特点：

  1. 如果二叉查找树有左子树，则左子树的结点的键值key要小于左子树的根结点的键值key
  2. 如果二叉查找树有右子树，则右子树的结点的键值key要大于右子树的根结点的键值key
  3. 对于二叉查找树而言，左子树和右子树也分别是二叉查找树。

可以看到，左子树的结点的键值都是小于右子树，二叉查找树的结点的键值key是不重复的。

  • 平衡二叉树

平衡二叉树也是有序树，指的是树中任一结点的左子树和右子树的深度之差不超过1，如下图所示：

  • 二叉树的性质说明

性质01：非空二叉树中的叶子结点数量等于双分支结点数量+1，双分支结点指的是就是度为2的结点，假设二叉树的叶子结点数量为n0,二叉树中单分支结点的数量为n1，二叉树中双分支结点的数量为n2，则二叉树中结点的总数 = n0 + n1 + n2。

可以看到，上图二叉查找树中叶子结点的数量为3，度为1的结点的数量为1，度为2的结点数量为2，所以该二叉查找树的结点总数为6，和图中结点数量一致。

性质02：二叉树的第i层上最多有2i-1（i≥1）个结点，因为二叉树结点最多的情况就是满二叉树。

可以看到，满二叉树此时一共有4层，也就是二叉树的高度为4，假设要计算二叉树第4层的结点数量，则带入公式24-1之后得到的结果为8，和图中结点数量一致。

性质03：高度为h的二叉树最多有2h-1（h≥1）个结点。满二叉树就是结点最多的二叉树，所以换句话说，满二叉树前h层结点的数量为2h-1（h≥1）。

可以看到，满二叉树此时一共有4层，也就是二叉树的高度为4，假设要计算满二叉树的结点总数，则带入公式24-1之后得到的结果为15，和图中结点数量一致。

BinarySearchTree.h

/**
* @file         : BinarySearchTree
* @brief        : 创建树，并实现二叉树的添加和删除节点
* @author       : TingFengLuo9@126.com
* @date         : 2026-1-12
* @note         : BST树由节点组成，每个节点中都有一个数据，有一个左指针（左树），有一个右指针（右树），树中包含了一个根节点
*    copyright (c) TingFengLuo9@126.com ALL Rights Reserved
*/

#ifndef __BINARYSEARCHTREE_H_
#define __BINARYSEARCHTREE_H_//防止头文件重复包含

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "drawtree.h"

#if 0
//将int重命名为DataType_t，便于后续用户更改数据类型
typedef int DataType_t;

//定义树几点类型
typedef struct BinarySearchTree
{
    DataType_t data;
    struct BinarySearchTree *lchild;
    struct BinarySearchTree *rchild;
}BSTree_t;
#endif


//创建树
BSTree_t *BSTree_Create(DataType_t data);
//创建新节点
BSTree_t *BSTree_NewNode(DataType_t data);
//添加新节点
bool BSTree_Add(BSTree_t *root,DataType_t data);


#endif

BinarySearchTree.c

#include "BinarySearchTree.h"

/**
* @name         : BSTree_Create
* @brief        : 创建树，并对树初始化
* @param        
           @data: 需要给根传的数据
* @return       : 返回根节点地址
* @note         : NULL 
 */
BSTree_t *BSTree_Create(DataType_t data)
{
    //树中有一个根节点，创建根节点
    BSTree_t *root = (BSTree_t *)calloc(1,sizeof(BSTree_t));
    //判断根节点是否创建出来
    if(NULL == root){
        perror("binary search tree create memory failed for root");
        exit(-1);
    }

    //对根节点初始化
    root->data = data;
    root->lchild = NULL;
    root->rchild = NULL;
    
    return root;
}

/**
* @name         : BSTree_Create
* @brief        : 创建新节点，便于后续插入
* @param        
           @data: 需要给根传的数据
* @return       : 创建成功返回true
* @note         : NULL 
 */
BSTree_t *BSTree_NewNode(DataType_t data)
{
    //创建新节点，并对新节点分配内存
    BSTree_t *new_node = (BSTree_t *)calloc(1,sizeof(BSTree_t));
    //判断新节点是否创建成功
    if(NULL == new_node){
        perror("binary search tree create memory failed for new node");
        exit(-1);
    }

    //对新节点初始化
    new_node->data = data;
    new_node->lchild = NULL;
    new_node->rchild = NULL;

    return new_node;
 }

 /**
* @name         : BSTree_Add
* @brief        : 在树中添加新节点，左树的值都比根节点小，右树的值都比根节点大
* @param        
           @data: 需要给根传的数据
* @return       : 创建成功返回true
* @note         : NULL 
 */
bool BSTree_Add(BSTree_t *root,DataType_t data)
{
    //判断根节点是否存在
    if(NULL == root){
        printf("root node do not exist\n");
        return false;
    }

    //创建变量存储新节点地址
    BSTree_t *new_node = BSTree_NewNode(data);

    //创建变量存储root节点
    BSTree_t *node = root;

    
    //当跟根节点存在
    while(node){
        //当根节点和新节点的值相等时，插入不进去
        if(node->data == data){
            printf("binary search tree root node vlaue is same to date,do not add\n");
            printf("root node value : %d,",root->data);
            printf("new node value : %d\n",new_node->data);
            free(new_node);
            new_node = NULL;
            return false;
        }
        //如果新节点的值大于根节点值，遍历右子树，并把新节点插入
        if(data > node->data){
            if(node->rchild == NULL){
                node->rchild = new_node;
                break;
            }
            node = node->rchild;
        }
        //如果新节点的值小于根节点值，遍历左子树，并把新节点插入
        else if(data < node->data){
            if(node->lchild == NULL){
                node->lchild = new_node;
                break;
            }
            node = node->lchild;
        }

    }

    return true;
    
 }

drawtree.h

///////////////////////////////////////////////////////////
//
//  Copyright(C), 2013-2021, GEC Tech. Co., Ltd.
//
//  文件: lab/tree/headers/drawtree.h
//  日期: 2017-9
//  描述: 使用C语言写一页webpage展示二叉树
//
//   
//
///////////////////////////////////////////////////////////

#ifndef _DRAWTREE_H_
#define _DRAWTREE_H_

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 公共头文件 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
#include <time.h>
#include <fcntl.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <stdbool.h>
#include <strings.h>

#include <sys/stat.h>
#include <sys/types.h>

/* ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 公共头文件 ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ */

#define MAX(a, b) ({ \
		typeof(a) _a = a; \
		typeof(b) _b = b; \
		(void)(&_a == &_b);\
		_a > _b? _a : _b; \
		})



/* ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 用户二叉树节点 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
//指的是BST树中的结点有效键值的数据类型，用户可以根据需要进行修改
typedef int DataType_t;

//定义树几点类型
typedef struct BinarySearchTree
{
    DataType_t data;
    struct BinarySearchTree *lchild;
    struct BinarySearchTree *rchild;
}BSTree_t;
/* ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 用户二叉树节点 ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ */


/* ↓↓↓↓↓ 用户指定二叉树节点 ↓↓↓↓↓ */
#ifndef TREENODE
#define TREENODE BSTree_t
#endif
/* ↑↑↑↑↑ 用户指定二叉树节点 ↑↑↑↑↑ */








/* ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 默认二叉树节点 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
typedef struct _tree_node
{
	int data;
	struct _tree_node *lchild;
	struct _tree_node *rchild;

#ifdef AVL
	int height;
#endif

#ifdef RB
	struct _tree_node *parent;
	int color;
#endif
}_treenode, *_linktree;

// #ifndef TREENODE
// #define TREENODE Tnode_t
// #endif

/* ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 默认二叉树节点 ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ */


/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */

#ifndef QUEUE_TREENODE_DATATYPE
#define QUEUE_TREENODE_DATATYPE TREENODE *
#endif

typedef QUEUE_TREENODE_DATATYPE qn_datatype;

struct _queue_node
{
	qn_datatype data;
	struct _queue_node *next;

};

typedef struct
{
	struct _queue_node *front;
	struct _queue_node *rear;
#ifdef QUEUE_SIZE
	int size;
#endif
}_queuenode, *_linkqueue;


static _linkqueue init_queue(void)
{
    _linkqueue q = (_linkqueue)malloc(sizeof(_queuenode));
	q->front = q->rear =
		(struct _queue_node *)malloc(sizeof(struct _queue_node));
	q->rear->next = NULL;

	return q;
}

static bool is_empty_q(_linkqueue q)
{
	return (q->front == q->rear);
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static bool out_queue(_linkqueue q, qn_datatype *pdata)
{
	if(is_empty_q(q))
		return false;

	struct _queue_node *p = q->front;

	q->front = q->front->next;
	free(p);
	*pdata = q->front->data;

	return true;
}

static bool en_queue(_linkqueue q, qn_datatype data)
{
	struct _queue_node *pnew;
	pnew = (struct _queue_node *)malloc(sizeof(struct _queue_node));
	if(pnew == NULL)
		return false;

	pnew->data = data;
	pnew->next = NULL;

	q->rear->next = pnew;
	q->rear = pnew;

	return true;
}

#ifdef QUEUE_SIZE
int queue_size(_linkqueue *q)
{
	return q->size;
}
#endif
/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */


static void pre_travel(TREENODE *root, void (*handler)(TREENODE *))
{
	if(root == NULL)
		return;
	
	handler(root);
	pre_travel(root->lchild, handler);
	pre_travel(root->rchild, handler);
}

static void mid_travel(TREENODE *root, void (*handler)(TREENODE *))
{
	if(root == NULL)
		return;
	
	mid_travel(root->lchild, handler);
	handler(root);
	mid_travel(root->rchild, handler);
}

static void post_travel(TREENODE *root, void (*handler)(TREENODE *))
{
	if(root == NULL)
		return;

	post_travel(root->lchild, handler);
	post_travel(root->rchild, handler);
	handler(root);
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static void level_travel(TREENODE *root, void (*handler)(TREENODE *))
{
	if(root == NULL)
		return;

    _linkqueue q;
	q = init_queue();

	en_queue(q, root);

    TREENODE *tmp;
	while(1)
	{
		if(!out_queue(q, &tmp))
			break;

		handler(tmp);

		if(tmp->lchild != NULL)
			en_queue(q, tmp->lchild);
		if(tmp->rchild != NULL)
			en_queue(q, tmp->rchild);
	}
}
/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static char page_begin[] = "<html><head><title>tree map"
                           "</title></head><body>"
			   "<table border=0 cellspacing"
                           "=0 cellpadding=0>";
static char line_begin[] = "<tr>";
static char line_end  [] = "</tr>";
static char space     [] = "<td>&nbsp;</td>";
static char underline [] = "<td style=\"border-bottom:"
	 		   "1px solid #58CB64\">&nbsp;"
                           "</td>";

#ifdef RB
static char data_begin_red[] = "<td bgcolor=\"#FF0000\";style="
			       "\"border:1px sol"
                               "id #58CB64;background-colo"
                               "r:#DDF1D8;PADDING:2px;\" t"
                               "itle=\"level: 1\">";
static char data_begin_blk[] = "<td bgcolor=\"#000000\";style="
			       "\"border:1px sol"
                               "id #58CB64;background-colo"
                               "r:#DDF1D8;PADDING:2px;\" t"
                               "itle=\"level: 1\"><font color"
				"=\"#FFFFFF\">";
static char data_end_red[] = "</td>";
static char data_end_blk[] = "</font></td>";
#else
static char data_begin[] = "<td style=\"border:1px sol"
                           "id #58CB64;background-colo"
                           "r:#DDF1D8;PADDING:2px;\" t"
                           "itle=\"level: 1\">";
static char data_end  [] = "</td>";
#endif

static char page_end  [] = "</table></body></html>";

#define MAX_TREENODES_NUMBER 100
#define FILENAME 32

static int central_order[MAX_TREENODES_NUMBER];

static void putunderline(int fd, int num)
{
	int i;
	for(i=0; i<num; i++)
	{
		write(fd, underline, strlen(underline));
	}
}


static void putspace(int fd, int num)
{
	int i;
	for(i=0; i<num; i++)
	{
		write(fd, space, strlen(space));
	}
}
/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
#ifdef RB
static void putdata(int fd, TREENODE * p)
{
	char s[50];
	bzero(s, 50);

	snprintf(s, 50, "%d", p->data);

	switch(p->color)
	{
	case RED:
		write(fd, data_begin_red, strlen(data_begin_red));
		write(fd, s, strlen(s));
		write(fd, data_end_red, strlen(data_end_red));
		break;
	case BLACK:
		write(fd, data_begin_blk, strlen(data_begin_blk));
		write(fd, s, strlen(s));
		write(fd, data_end_blk, strlen(data_end_blk));
	}
}
#else
static void putdata(int fd, int data)
{
	char s[50];
	bzero(s, 50);

	snprintf(s, 50, "%d", data);
	write(fd, data_begin, strlen(data_begin));
	write(fd, s, strlen(s));
	write(fd, data_end, strlen(data_end));
}
#endif

static int Index = 0;
static void create_index(TREENODE * root)
{
	if(Index >= MAX_TREENODES_NUMBER-1)
		return;

	central_order[Index++] = root->data;
}


static int get_index(int data)
{
	int i;
	for(i=0; i<100; i++)
	{
		if(central_order[i] == data)
			return i;
	}
	return -1;
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static void data_leftside(int fd, TREENODE * root, int spaces)
{
	if(root == NULL)
		return;

	int s_line=0;

	if(root->lchild != NULL)
	{
		s_line = get_index(root->data)-
			 get_index(root->lchild->data)-1;
	}
	putspace(fd, spaces-s_line);
	putunderline(fd, s_line);
}


static int data_rightside(int fd, TREENODE * root)
{
	if(root == NULL)
		return 0;

	int s_line=0;

	if(root->rchild != NULL)
	{
		s_line = get_index(root->rchild->data)-
			 get_index(root->data)-1;
	}

	putunderline(fd, s_line);
	return s_line;
}


static void start_page(int fd)
{
	write(fd, page_begin, strlen(page_begin));
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static void end_page(int fd)
{
	write(fd, page_end, strlen(page_end));
}


static void draw(TREENODE * root)
{
	if(root == NULL)
		return;

	time_t t;
	time(&t);
	static char filename[FILENAME];
	bzero(filename, FILENAME);
	snprintf(filename, FILENAME, "%u.html", (unsigned)t);
	int fd = open(filename, O_CREAT | O_TRUNC | O_RDWR, 0644);
	if(fd == -1)
	{
		perror("open() failed");
		exit(1);
	}

	Index = 0;
	mid_travel(root, create_index);

    _linkqueue q = init_queue();

	TREENODE * tmp = root;
	int ndata = 1;

	start_page(fd);
	while(1)
	{
		write(fd, line_begin, strlen(line_begin));

		int i, n = 0;
		int nextline = 0;
		for(i=0; i<ndata; i++)
		{
			int index = get_index(tmp->data);

			data_leftside(fd, tmp, index-n);

			#ifdef RB
			putdata(fd, tmp);
			#else
			putdata(fd, tmp->data);
			#endif
			int rightline = data_rightside(fd, tmp);

			if(tmp->lchild != NULL)
			{
				nextline++;
				en_queue(q, tmp->lchild);
			}
			if(tmp->rchild != NULL)
			{
				nextline++;
				en_queue(q, tmp->rchild);
			}
			if(!out_queue(q, &tmp))
				return;

			n = index + rightline;
			n++;
		}
		write(fd, line_end, strlen(line_end));
		ndata = nextline;
	}
	end_page(fd);
	close(fd);
}
#endif

main.c

#include "BinarySearchTree.h"
#include "drawtree.h"

int main(int argc,const char *argv[]){
    //创建变量存储根节点
    BSTree_t *root = BSTree_Create(50);
    if(NULL == root){
        printf("root node do not exist\n");
        return -1;
    }

    BSTree_Add(root,15);
    BSTree_Add(root,16);
    BSTree_Add(root,68);
    BSTree_Add(root,48);
    BSTree_Add(root,20);
    BSTree_Add(root,30);
    BSTree_Add(root,75);
    BSTree_Add(root,80);
    BSTree_Add(root,10);
    BSTree_Add(root,35);
    draw(root);
}

效果图：

笔试题：

笔试题：

笔试题：

笔试题：

笔试题：

  • 二叉树的存储结构
  • 顺序结构

二叉树的顺序结构就是采用一组地址连续的内存单元（数组）按照从上到下，从左到右的顺序依次存储二叉树中的结点，也就是把二叉树中编号为i的结点存储在数组下标为i-1的元素空间中。

如果按照二叉树的性质而言，满二叉树以及完全二叉树使用顺序存储比较合适，好处是可以最大程序的节约内存空间，并且可以利用数组下标查找数据。

对于一般的二叉树而言，也可以使用顺序结构进行存储，为了可以使用数组来表示结点的逻辑关系，需要数组的一些元素空间来存储空结点，会导致浪费空间。0表示不存在的空结点。

  • 链式结构

链式结构就可以有效的解决数组中存储空结点的问题，链式结构不受内存的限制，由于一个结点最多可能存在两个子结点，所以应该采用双向不循环链表的方案来实现。

  • 二叉树的遍历说明

通过遍历二叉树可以得到二叉树的所有信息，对二叉树做出全面的了解，对于二叉树遍历结点而言，绝大多数是采用二叉查找树（BST树）来实现，接下来就以二叉查找树为例进行讲解：

思考：如果按照思路把n个结点插入到二叉查找树中，请问应该如何验证程序的正确性???

1.需要包含drawtree.h头文件，并需要把源文件和该头文件处于同一个路径中，双引号包含

2.修改drawtree.h头文件中关于二叉树的数据类型以及二叉树结点的类型，操作如下图所示

3.在用户设计的源文件中调用drawtree.h头文件中的函数即可，然后把根结点传入该函数！！

  • 编译源程序，当编译运行之后，会自动在当前目录内生成一个网页，打开网页即可验证！！

对于二叉树的遍历，指的是从根结点出发，依次访问二叉树中所有的结点，每个结点只会被访问一次，一共提供了三种方案实现二叉树结点的遍历：前序遍历、中序遍历、后序遍历。

  • 前序遍历（根结点—>左子树—>右子树） A  B  D  G  H  C  E  I  F
  • 中序遍历（左子树—>根结点—>右子树）  G  D  H  B  A  E  I  C  F
  • 后序遍历（左子树—>右子树—>根结点）  G  H  D  B  I  E  F  C  A

笔试题：一颗二叉树的前序遍历顺序为ABDEGHCF，中序遍历顺序为DBGEHACF，请写出后序遍历的顺序。 

笔试题：

笔试题：

笔试题：

笔试题：

算法题01：

算法题02：

算法题03：

  • 删除二叉查找树中的结点

从二叉查找树删除某个结点比插入结点要麻烦一点，但是删除结点之后也必须遵循“小–中–大”的原则。删除结点的时候就可能会出现以下几种情况：

  • 要删除的结点的键值比根结点小，则在根结点的左子树进行递归的删除
  • 要删除的结点的键值比根结点大，则在根结点的右子树进行递归的删除
  • 如果要删除的结点恰好是根结点，也会遇到以下三种情况：
  1. 如果根结点有左子树，需要从左子树中找到键值最大的结点去替换根结点，然后在左子树中把原来的键值最大的结点递归的删掉
  2. 如果根结点有右子树，需要从右子树中找到键值最小的结点去替换根结点，然后在右子树中把原来的键值最小的结点递归的删掉
  3. 如果根结点没有左子树和右子树，则直接把根结点删掉

可以看到，如果要删除的结点是15，该结点有左子树，所以需要从左子树中找到键值最大的结点，也就是13，然后把13替换到15的位置，最后把多余13删掉即可。

可以看到，如果要删除的结点是25，该结点有右子树，所以需要从右子树中找到键值最小的结点，也就是26，然后把26替换到25的位置，最后把多余26删掉即可。

作业：根据二叉查找树的删除结点原理以及二叉查找树的特性，设计删除结点的函数并验证。