KJHの博客

1、概念：

二叉查找树，也称排序二叉树，是指一棵空树或者具备下列性质的二叉树(每个节点都不能有多于两个儿子的树)：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树
4. 没有键值相等的节点

从其性质可知，定义排序二叉树树的一种自然的方式是递归的方法，其算法的核心为递归过程，由于它的平均深度为O(logN)，所以递归的操作树，一般不必担心栈空间被耗尽。

树的深度：对于任意节点Ni，Ni的深度为从根到Ni的惟一路径的长。

线性队列和线性堆栈有点相似，但队列里面的数据是“先进先出”。实际应用时大多是采用循环队列，关于队列的循环实现，需要两件事情要警惕：1、检测队列是否为空；2、检测队列是否已满。下面就简单的介绍循环队列的一些基本操作

1、队列的数据节点

栈也是一种很重要的数据结构，具备“先进后出”的特点。程序中的函数调用以及递归都涉及栈这一数据结构，熟悉栈有利于我们更好地理解函数的调用过程(主要是形参，局部变量以及函数的返回值)和递归算法的实现过程

1、栈的数据节点

双向链表较单向链表有更好的灵活性，具备前后指针，可以更方便的对链表进行操作，但程序设计也更复杂，需要同时考虑前后指针。这里同样对照单链表的基础操作，讨论链表的创建、尾端添加元素、指定位置插入元素、删除指定单个元素节点、删除指定元素所有节点、删除指定位置节点等基础操作。
1、双向链表的数据结构

1
2
3
4
5
6

typedef struct _Node
{
	int value;
	struct _Node *prev;
	struct _Node *next;
}Node;

2、创建一个双向非循环链表

着重实现《剑指Offer》上面的单向链表操作。