(计蒜客)二叉树的分裂

爱被打了一巴掌 2022-04-22 10:06 172阅读 0赞

试写一个算法,将一棵二叉查找树,分裂成两棵二叉查找树,使得一棵的关键字都小于或等于x,另一棵的关键字都大于x

本题输入输出广义表达式,空的结点上存在一个-占位符

**输入格式**

输入有两行,第一行为待操作的二叉树广义表达式

第二行输入值为x

**输出格式**

输出也为两行,为分裂后的二叉树广义表达式,第二行数值为x

**样例输入**

5(2,8)
    3

**样例输出**

2
    5(-,8)

解题思路:

这道题有多个难点,第一是广义表的输入和输出,这里有模板可以仿照,但要根据题意稍加改动

比如在读入的时候,空结点要用 - 符号进行代替,然后就是数字在入栈时,如果这个数字是二位数,该怎么处理

Node* Node::buildTree(const string& input)  //根据广义表的建树操作
    {
    	stack<Node*> treeStack;
    	int k = -1;
    	if (input == "") {
    		return nullptr;
    	}
    
    	for (int i = 0; i < input.length(); ++i) {
    		if (input[i] == '(') {
    			k = 0;
    			treeStack.push(new Node(input[i] - 48, nullptr));
    		}
    		else if (input[i] == ',') {
    			k = 1;
    		}
    		else if (input[i] == ')') {
    			treeStack.pop();
    		}
    		else {
    			//空结点忽略
    			if (input[i] == '-') {
    				continue;
    			}
    
    			//读入两位数时的处理方式
    			Node* temp = nullptr;
    			if (input[i] >= 48 && input[i] <= 57 && input[i+1] >= 48 && input[i+1] <= 57) {
    				temp = new Node(10 * (input[i] - 48) + (input[i + 1] - 48), nullptr);
    				i++;
    			}
    			else {
    				temp = new Node(input[i] - 48, nullptr); //暂存
    			}
    
    			if (k == -1) {
    				treeStack.push(temp);
    			}
    			else if (k == 0) {
    				treeStack.pop();  //栈顶元素出栈
    				treeStack.top()->lchild = temp;
    				temp->father = treeStack.top();
    				treeStack.push(temp);
    			}
    			else if (k == 1) {
    				treeStack.pop();
    				treeStack.top()->rchild = temp;
    				temp->father = treeStack.top();
    				treeStack.push(temp);
    			}
    		}
    	}
    	return treeStack.top();   //最后返回的是根节点
    }

输出函数只需在结点为空时加上 - 符号即可

void Node::lambdaprint()
    {
    	cout << data;
    	if (lchild != nullptr) {
    		cout << "(";
    		lchild->lambdaprint();
    		if (rchild == nullptr) {
    			cout << ",-)";
    		}
    	}
    
    	if (rchild != nullptr) {
    		if (lchild == nullptr) {
    			cout << "(-";
    		}
    		cout << ",";
    		rchild->lambdaprint();
    		cout << ")";
    	}
    }

之后是寻找分裂的左节点和右节点:

1找到小于等于x的最大结点max

if (root == nullptr) {
    			return;
    		}
    
    		Node* current_node = root;
    		Node* mmax = nullptr;
    
    		while (1) {
    			if (current_node == nullptr) {
    				break;
    			}
    			if (value == current_node->data) {
    				mmax = current_node;
    				break;
    			}
    			else if (current_node->data < value) {
    				if (mmax == nullptr || current_node->data > mmax->data) {
    					mmax = current_node;
    				}
    				current_node = current_node->rchild;
    			}
    			else {
    				current_node = current_node->lchild;
    			}
    		}

2.求出两棵分裂后的树

if (mmax == nullptr) {
    			cout << endl;
    			root->lambdaprint();
    			return;
    		}
    
    		Node* l = mmax;
    		Node* r = mmax->rchild;
    		mmax->rchild = nullptr;
    
    		while (mmax != root) {
    			if (mmax == mmax->father->lchild) {
    				mmax->father->lchild = r;
    				r = mmax->father;
    			}
    			else {
    				mmax->father->rchild = l;
    				l = mmax->father;
    			}
    			mmax = mmax->father;
    		}
    
    
    		if (l != nullptr) {
    			l->lambdaprint();
    		}
    		cout << endl;
    		if (r != nullptr) {
    			r->lambdaprint();
    		}
    	}

整体代码如下:

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <stack>
    using namespace std;
    
    class Node {
    public:
    	int data;
    	Node* lchild, *rchild, *father;
    	Node(int _data, Node* _father) {
    		data = _data;
    		lchild = nullptr;
    		rchild = nullptr;
    		father = _father;
    	}
    	~Node() {
    		if (lchild != nullptr) {
    			delete lchild;
    		}
    		if (rchild != nullptr) {
    			delete rchild;
    		}
    	}
    
    	//搜索函数
    	Node* search(int value);
    	Node* buildTree(const string& input);
    	void lambdaprint();
    };
    
    Node* Node::search(int value)
    {
    	if (value == data) {
    		return nullptr;
    	}
    	else if (value > data) {
    		if (rchild == nullptr) {
    			return nullptr;
    		}
    		else {
    			return rchild->search(value);
    		}
    	}
    	else {
    		if (lchild == nullptr) {
    			return nullptr;
    		}
    		else {
    			return lchild->search(value);
    		}
    	}
    }
    
    Node* Node::buildTree(const string& input)
    {
    	stack<Node*> treeStack;
    	int k = -1;
        if (input == "") {
    		return nullptr;
    	}
    
    	for (int i = 0; i < input.length(); ++i) {
    		if (input[i] == '(') {
    			k = 0;
    			treeStack.push(new Node(input[i]-48,nullptr));
    		}
    		else if (input[i] == ',') {
    			k = 1;
    		}
    		else if (input[i] == ')') {
    			treeStack.pop();
    		}
    		else {
    			if (input[i] == '-') {
    				continue;
    			}
    
                Node* temp = nullptr;
    			if (input[i] >= 48 && input[i] <= 57 && input[i+1] >= 48 && input[i+1] <= 57) {
    				temp = new Node(10 * (input[i] - 48) + (input[i + 1] - 48), nullptr);
    				i++;
    			}
    			else {
    				temp = new Node(input[i] - 48, nullptr); //暂存
    			}
                
    			if (k == -1) {
    				treeStack.push(temp);
    			}
    			else if (k == 0) {
    				treeStack.pop();  //栈顶元素出栈
    				treeStack.top()->lchild = temp;
    				temp->father = treeStack.top();
    				treeStack.push(temp);
    			}
    			else if (k == 1) {
    				treeStack.pop();
    				treeStack.top()->rchild = temp;
    				temp->father = treeStack.top();
    				treeStack.push(temp);
    			}
    		}
    	}
    	return treeStack.top();   //最后返回的是根节点
    }
    
    void Node::lambdaprint()
    {
    	cout << data;
    	if (lchild != nullptr) {
    		cout << "(";
    		lchild->lambdaprint();
    		if (rchild == nullptr) {
    			cout << ",-)";
    		}
    	}
    
    	if (rchild != nullptr) {
    		if (lchild == nullptr) {
    			cout << "(-";
    		}
    		cout << ",";
    		rchild->lambdaprint();
    		cout << ")";
    	}
    }
    
    class BinaryTree {
    private:
    	Node* root;
    public:
    	BinaryTree() {
    		root = nullptr;
    	}
    	~BinaryTree() {
    		delete root;
    	}
    
    	void lambdaprint() {
    		if (root != nullptr) {
    			root->lambdaprint();
    		}
    	}
    	
    	void buildTree(const string& input) {
    		root = root->buildTree(input);
    	}
    
    	Node* search(int value) {
    		return root->search(value);
    	}
    
    	void searchAndDivide(int value)
    	{
            if (root == nullptr) {
    			return;
    		}
            
    		Node* current_node = root;
    		Node* mmax = nullptr;
    
    		while (1) {
    			if (current_node == nullptr) {
    				break;
    			}
    			if (value == current_node->data) {
    				mmax = current_node;
    				break;
    			}
    			else if (current_node->data < value) {
    				if (mmax == nullptr || current_node->data > mmax->data) {
    					mmax = current_node;
    				}
    				current_node = current_node->rchild;
    			}
    			else {
    				current_node = current_node->lchild;
    			}
    		}
    
    		if (mmax == nullptr) {
    			cout << endl;
    			root->lambdaprint();
    			return;
    		}
    
    		Node* l = mmax;
    		Node* r = mmax->rchild;
    		mmax->rchild = nullptr;
    	
    		while (mmax != root) {
    			if (mmax == mmax->father->lchild) {
    				mmax->father->lchild = r;
    				r = mmax->father;
    			}
    			else {
    				mmax->father->rchild = l;
    				l = mmax->father;
    			}
    			mmax = mmax->father;
    		}
    		
    	
    		if (l != nullptr) {
    			l->lambdaprint();
    		}
    		cout << endl;
    		if (r != nullptr) {
    			r->lambdaprint();
    		}
    	}
    };
    
    int main() {
    	BinaryTree binaryTree;
    	
    	string input;
    	getline(cin, input);
    	binaryTree.buildTree(input);
    	int value = 0;
    	cin >> value;
    	binaryTree.searchAndDivide(value);
    
    	
    	return 0;
    }