博客

给出后序遍历序列###ca##ji####spom, 构建二叉树。

上述二叉树实际是一颗二叉排序树，请实现程序

查找c节点，输出从树根到c节点的路径。

删除其中的m节点，使得删除后仍为二叉排序树。

头文件 Binary_node.h 构建二叉树节点

#include<iostream>
struct Binary_node 
{
 char ch;
 struct Binary_node* left; //指向左孩子的指针
 struct Binary_node* right; //指向右孩子的指针
 Binary_node(); //默认的不带参数的构造函数
 Binary_node(char& x); //带有一个参数的构造函数
};
typedef struct Binary_node* ptr;

Binary_node.cpp 节点的实现

#include "Binary_node.h"
Binary_node::Binary_node() 
{
 left = NULL;
 right = NULL;
}
Binary_node::Binary_node(char& x) 
{
 ch = x;
 left = NULL;
 right = NULL;
}

Binary_tree.h 定义二叉树的类

#include "Binary_node.h"
#include<iostream>
using namespace std;
typedef struct Binary_node* ptr;
class Binary_tree {
public:
 Binary_tree();
 void postorder(void (*visit)(char&));
 void BuildTree_Postorder(ptr& aroot, string& postorder, int& index);
 ptr root;
protected:
 void recursive_postorder(ptr& sub_root, void (*visit)(char&));
 int count;
};

Binary_tree.cpp 二叉树的实现

#include "Binary_tree.h"
typedef struct Binary_node* ptr;
Binary_tree::Binary_tree()
{
 root = NULL;
 count = 0;
}
void Binary_tree::postorder(void (*visit)(char&))
{
 recursive_postorder(root, visit);
}
void Binary_tree::recursive_postorder(ptr& sub_root, void (*visit)(char&))
{
 if (sub_root != NULL) 
 {
  recursive_postorder(sub_root->left, visit);
  recursive_postorder(sub_root->right, visit);
  (*visit)(sub_root->ch);
 }
}
void Binary_tree::BuildTree_Postorder(ptr& aroot, string& postorder, int& index)
{
 if (index>=0)
 {
  if (postorder[index] == '#')
   aroot = NULL;
  else 
  {
   aroot = new Binary_node;
   aroot->ch = postorder[index];
   BuildTree_Postorder(aroot->right, postorder, --index);
   BuildTree_Postorder(aroot->left, postorder, --index);
  }
 }
}
``
继承实现二分查找树 Search_tree.h

```cpp
#include "Binary_tree.h"
enum Error_code{success,not_present};
class Search_tree: public Binary_tree
{
public:
 Error_code insert(char &new_data);
 void remove(Binary_node*& root,char &target);
 void tree_search(Binary_node*& root,char &target);
 //ptr search_root;
private: 
    Binary_node* search_for_node(Binary_node*& sub_root, char& target); 
    Error_code remove_root(Binary_node*& sub_root);
    Error_code search_and_destroy(Binary_node*& sub_root,char& target);
};

Search_tree.cpp 二分查找树的实现

#include"Search_tree.h"
void Search_tree::tree_search(Binary_node*& root,char &target)
{
	Binary_node* found = search_for_node(root, target);
	if (found == NULL)
		cout<<"false";
	else
		cout<<"true";
}
Binary_node* Search_tree::search_for_node(Binary_node*& sub_root,char &target) 
{
	if (sub_root == NULL||sub_root->ch == target)
	{
		cout<<sub_root->ch;
		return sub_root;
	}
	else if (sub_root->ch < target)
	{
		cout<<sub_root->ch;
		return search_for_node(sub_root->right, target);
	}
	else 
	{
		cout<<sub_root->ch;
		return search_for_node(sub_root->left, target);
	}
}

void Search_tree::remove(Binary_node*& root,char& target)
{
	Error_code result=search_and_destroy(root,target);
	if(result==success)
	count--;
	else
	cout<<"false";
}
Error_code Search_tree::search_and_destroy(Binary_node*& sub_root,char &target)
{
	if (sub_root == NULL || sub_root->ch == target)
		return remove_root(sub_root);
	else if (target < sub_root->ch)
		return search_and_destroy(sub_root->left, target);
	else
		return search_and_destroy(sub_root->right, target);
}
Error_code Search_tree::remove_root(Binary_node*& sub_root)
{
	//删除左边子树最右边的孩子 
	//没有子树 
	if (sub_root == NULL) 
		return not_present;
	Binary_node* to_delete = sub_root;
	//只有一棵子树为空 
    if (sub_root->right == NULL) 
		sub_root = sub_root->left;
	else if (sub_root->left == NULL) 
		sub_root = sub_root->right;
	else 
	{ 
		//两棵子树都不是空的
		to_delete = sub_root->left;
		Binary_node* parent = sub_root;
		while (to_delete->right != NULL) { 
			parent = to_delete;
			to_delete = to_delete->right;
		} 
		sub_root->ch = to_delete->ch;
		if (parent == sub_root) 
			sub_root->left = to_delete->left;  //左孩子无右孩子
		else 
			parent->right = to_delete->left;  //左孩子有右孩子
	} 
	delete to_delete;
	return success;
}

主函数的实现 main

#include"Search_tree.h"
#include<iostream>
#include<string>
using namespace std;
void print(char& m)
{
	cout<<m;
}
int main()
{
	Binary_tree bt;
	string S;
	cin >> S;
	int length = S.size() - 1;
	bt.BuildTree_Postorder(bt.root,S,length);
	bt.postorder(print);
	cout<<endl;
	Search_tree st;
	char al='c';
	st.tree_search(bt.root,al);
	cout<<endl;
	al='m';
	st.remove(bt.root,al);
	bt.postorder(print);
	return 0;
}