二叉树

二叉树

搜索二叉树：左边比根小，右边比根大；子树也满足这个特征。

搜索二叉树还有一个特征：去走一个中序是一个升序的状态。所以搜索二叉树可以叫做二叉排序树或二叉查找树。

模板不喜欢用T了，因为喜欢用K（关键字）。

推荐一般用BinarySearchTree，二叉搜索树，不要用SearchTreeBinary，因为简写出来是SBTree。

template<class K>
struct BSTreeNode {
	BSTreeNode<K>* _left;	
	BSTreeNode<K>* _right;
	K _key;
};


template<class K>
class BSTree {
	//喜欢在类里进行类型重定义，因为受到类域的限制
	typedef BSTreeNode<K> Node;
public:
	bool Insert(const K& key)
	{
	}
private:
	Node* _root = nullptr; //构造函数懒得给了，直接写一个缺省值
};

我们先进行一个插入：

插入有成功也有失败：

当我们想进行插入12和13时，可以和各个树的根结点进行比较，确定插入的位置。默认的搜索二叉树是不允许冗余的，有相同的值会插入失败。

根的值是怎么来的？插入的第一个值就是根。所以如果是同样的值，插入的顺序不同树的形状就不同。

bool Insert(const K& key)
	{
		if (_root == nullptr)//确定是否是插入的第一个值
		{
			_root = new Node(key);
			return true;
		}
		//当根不是空时，找对应的位置
		Node* cur = _root;
		while (cur)//cur不等于空就继续，等于空就结束
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur - > _left;
			}
			else
			{ 
				return false;
			}
		}
		cur = new Node(key);
		return true;
		 
	}

直接用cur = new Node(key)，可不可以？不可以，没有和树链接起来，出了作用域就找不到这个结点了。我们可以通过定义parent找到父节点。