二叉查找树-二叉树-数据结构与算法

以你之姓@ 2022-02-18 20:51 342阅读 0赞

**C++ 语言: 二叉查找树**  
二叉查找树(Binary Search Tree)，又被称为二叉搜索树。  
它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个结点，x节点包含关键字key，节点x的key值记为key\[x\]。  
如果y是x的左子树中的一个结点，则key\[y\] < key\[x\]；如果y是x的右子树的一个结点，则key\[y\] > key\[x\]。  
那么，这棵树就是二叉查找树。如下图所示：

简单的想法：**从根节点往下走，比结点小的放左边，比结点大的放右边**

在二叉查找树中：  
(01) 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；  
(02) 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；  
(03) 任意节点的左、右子树也分别为二叉查找树。  
(04) 没有键值相等的节点（no duplicate nodes）。

// Binary Search Tree 
    #include <iostream>
    using namespace std;
    
    class BSNode
    {
    public:
    	int key;
    	BSNode *left;
    	BSNode *right;
    	BSNode *parent;
    
    	BSNode(int k, BSNode *l, BSNode *r, BSNode *p) :key(k), left(l), right(r), parent(p)
    	{
    	}
    };
    
    
    class BSTree
    {
    private:
    	BSNode* m_Root = NULL;
    
    public:
    	BSTree(){}
    	~BSTree() {}
    	//依次插入元素
    	void insert(int key)
    	{
    		BSNode * newNode = new BSNode(key, NULL, NULL, NULL);
    
    		if (m_Root != NULL)
    		{
    			BSNode * tempRoot = m_Root;
    			BSNode * preNode = NULL;
    			while (tempRoot != NULL)//找到添加元素的位置
    			{
    				preNode = tempRoot;//添加元素的位置 之前的位置
    				if (newNode->key > tempRoot->key)
    					tempRoot = tempRoot->right;
    				else
    					tempRoot = tempRoot->left;
    			}
    
    			if (newNode->key > preNode->key)
    				preNode->right = newNode;
    			else
    				preNode->left = newNode;
    			
    		}
    		else
    		{
    			m_Root = newNode;
    		}
    	}
    
    	//前序遍历
    	void preOrder()	{
    		inOrder(m_Root);
    	}
    	void preOrder(BSNode * root)
    	{
    		if (root == NULL)
    			return;
    		cout << root->key << " ";
    		preOrder(root->left);
    		preOrder(root->right);
    	}
    
    	//中序遍历
    	void inOrder()	{
    		inOrder(m_Root);
    	}
    	void inOrder(BSNode * root)
    	{
    		if (root == NULL)
    			return;
    		inOrder(root->left);
    		cout << root->key << " ";
    		inOrder(root->right);
    	}
    
    	//后序遍历
    	void postOrder()	{
    		postOrder(m_Root);
    	}
    	void postOrder(BSNode * root)
    	{
    		if (root == NULL)
    			return;
    		postOrder(root->left);
    		postOrder(root->right);
    		cout << root->key << " ";
    	}
    
    	//最小值
    	int minValue()
    	{
    		if (m_Root == NULL)
    			return -1;
    		BSNode * tempNode = m_Root;
    		while (tempNode->left != NULL)
    		{
    			tempNode = tempNode->left;
    		}
    		return tempNode->key;
    	}
    
    	//最大值
    	int maxValue()
    	{
    		if (m_Root == NULL)
    			return -1;
    		BSNode * tempNode = m_Root;
    		while (tempNode->right != NULL)
    		{
    			tempNode = tempNode->right;
    		}
    		return tempNode->key;
    	}
    
    	//摧毁树
    	void destoryTree(){
    		destoryTree(m_Root);
    	}
    	void destoryTree(BSNode * root)
    	{
    		if (root == NULL)
    			return;
    		if(root->left != NULL)
    			destoryTree(root->left);
    		if (root->right != NULL)
    			destoryTree(root->right);
    		
    		delete root;
    		root = NULL;
    	}
    
    };
    
    
    static int arr[] = { 4,2,5,6,1,7,8,3,9 }; //{ 1,5,4,3,2,6 };
    #define TBL_SIZE(a) ( (sizeof(a)) / (sizeof(a[0])) )
    
    int main()
    {
    	int i, ilen;
    	BSTree* tree = new BSTree();
    
    	cout << "== 依次添加: ";
    	ilen = TBL_SIZE(arr);
    	for (i = 0; i<ilen; i++)
    	{
    		cout << arr[i] << " ";
    		tree->insert(arr[i]);
    	}
    
    	cout << "\n== 前序遍历: ";
    	tree->preOrder();
    
    	cout << "\n== 中序遍历: ";
    	tree->inOrder();
    
    	cout << "\n== 后序遍历: ";
    	tree->postOrder();
    	cout << endl;
    
    	cout << "== 最小值: " << tree->minValue() << endl;
    	cout << "== 最大值: " << tree->maxValue() << endl;
    
    
    	// 销毁二叉树
    	tree->destoryTree();
    	cout << endl;
    	return 0;
    }