二叉树的简单实现

怼烎@ 2022-06-09 04:26 166阅读 0赞

用c++简单实现了一下二叉树，采用的结构是二叉链表

#include <iostream>
    using namespace std;
    #include <stack>
    #include <queue>
    
    class Node
    {
    private:
    	int data;
    	Node *lchild;
    	Node *rchild;
    public:
    	Node(int val, Node*  left = NULL, Node *right = NULL){data = val; lchild = left; rchild = right;}
    	friend class BinaryTree;
    	int Data()
    	{
    		return data;
    	}
    };
    
    class BinaryTree
    {
    private:
    	Node *root;
    public:
    	BinaryTree(){root = NULL;}
    	BinaryTree(int *data, int n, int &index, int invalid)
    	{
    		root = CreatTree(data, n, index, invalid);
    	}
    	~BinaryTree(){DestoryTree(root);}
    	Node* CreatTree(int *data, int n, int &index, int invalid);
    	void DestoryTree(Node *cur);
    
    	void PreOrder(Node *cur);
    	void PreOrder_s();
    
    	void InOrder(Node *cur);
    	void InOrder_s();
    
    	void PostOrder(Node *cur);
    	void PostOrder_s();
    
    	int DepthTree(Node *cur);
    	int Knum(Node *cur, int k);
    	int TreeNum(Node *cur);
    	Node *Find(Node *cur, int val);
    	Node *GetRoot();
    };
    
    Node* BinaryTree::CreatTree(int *data, int n, int &index, int invalid)
    {
    	Node *froot = NULL;
    	if (index < n && data[index] != invalid)
    	{
    		froot = new Node(data[index]);
    		froot->lchild = CreatTree(data, n, ++index, invalid);
    		froot->rchild = CreatTree(data, n, ++index, invalid);
    	}
    	return froot;
    }
    
    void BinaryTree::DestoryTree(Node *cur)
    {
    	if (cur == NULL)
    		return;
    	DestoryTree(cur->lchild);
    	DestoryTree(cur->rchild);
    	delete cur;
    }
    
    void BinaryTree::PreOrder(Node *cur)
    {
    	if (cur == NULL)
    		return;
    	cout<<cur->data<<" ";
    	PreOrder(cur->lchild);
    	PreOrder(cur->rchild);
    }
    
    void BinaryTree::InOrder(Node *cur)
    {
    	if (cur == NULL)
    		return;
    	
    	InOrder(cur->lchild);
    	cout<<cur->data<<" ";
    	InOrder(cur->rchild);
    }
    
    void BinaryTree::PostOrder(Node *cur)
    {
    	if (cur == NULL)
    		return;
    	
    	PostOrder(cur->lchild);
    	PostOrder(cur->rchild);
    	cout<<cur->data<<" ";
    }
    
    void BinaryTree::PreOrder_s()
    {
    	Node *cur = root;
    	stack<Node *> s;
    	if (cur == NULL)
    		return;
    	while (cur || !s.empty())
    	{
    		while (cur)
    		{
    			s.push(cur);
    			cout<<cur->data;
    			cur = cur->lchild;
    		}
    		Node *top = s.top();
    		s.pop();
    		cur = top->rchild;
    	}
    	cout<<endl;
    }
    
    void BinaryTree::InOrder_s()
    {
    	Node *cur = root;
    	stack<Node *> s;
    	if (cur == NULL)
    		return;
    	while (cur || !s.empty())
    	{
    		while (cur)
    		{
    			s.push(cur);	
    			cur = cur->lchild;
    		}
    		Node *top = s.top();
    		s.pop();
    		cout<<top->data<<" ";
    		cur = top->rchild;
    	}
    	cout<<endl;
    }
    
    void BinaryTree::PostOrder_s()
    {
    	Node *cur = root;
    	Node *pre = NULL;
    	stack<Node *> s;
    	if (cur == NULL)
    		return;
    	while (cur || !s.empty())
    	{
    		while (cur)
    		{
    			s.push(cur);	
    			cur = cur->lchild;
    		}
    		Node *top = s.top();
    		if (top->rchild == NULL || pre == top->rchild)
    		{
    			s.pop();
    			cout<<top->data<<" ";
    			pre = top;
    		}
    		else cur = top->rchild;
    	}
    	cout<<endl;
    }
     void BinaryTree::LevelOrder()
    {
    	queue<Node *>q;
    	Node *temp = root;
    	q.push(temp);
    	while (!q.empty())
    	{
    		Node *top = q.front();
    		cout<<top->data<<" ";
    		q.pop();
    		if (top->lchild)
    			q.push(top->lchild);
    		if (top->rchild)
    			q.push(top->rchild)
    	}
    }
    int BinaryTree::DepthTree(Node *cur)
    {
    	if (cur == NULL)
    		return 0;
    	int left = DepthTree(cur->lchild) + 1;
    	int right = DepthTree(cur->rchild) + 1;
    	return left > right ? left : right;
    } 
    
     
     int BinaryTree::TreeNum(Node *cur)
    {
    	int num = 0;
    	if (cur == NULL)
    		return num;
    	num++;
    	num += TreeNum(cur->lchild);
    	num += TreeNum(cur->rchild);
    	return num;
    }
    
    int BinaryTree::Knum(Node *cur, int k)
    {
    	if (cur == NULL || k < 0)
    		return 0;
    	if (k == 1)
    		return 1;
    	int left = Knum(cur->lchild, k - 1);
    	int right = Knum(cur->rchild, k - 1);
    	return left + right;
    }
    
    Node* BinaryTree::Find(Node *cur, int val)
    {
    	Node *temp = cur;
    	Node *ret = NULL;
    	if (temp == NULL)
    		return NULL;
    	if (cur->data == val)
    		ret = temp;
    	else
    	{
    		ret = Find(temp->lchild, val);
    		if (ret == NULL)
    			ret = Find(temp->rchild, val);
    	}
    	return ret;
    }
    Node *BinaryTree::GetRoot()
    {
    	return root;
    }
    
    void main()
    {
    	int a[] = {1,2,3,-1,-1,4,-1,-1,5,6,-1,-1,7,-1,-1};
    	int n = 15;
    	int index = 0;
    	BinaryTree tree(a, n, index, -1);
    	tree.PreOrder(tree.GetRoot());
    	tree.PreOrder_s();
    	tree.InOrder(tree.GetRoot());
    	tree.InOrder_s();
    	tree.PostOrder(tree.GetRoot());
    	tree.PostOrder_s();
    	cout<<"树的深度为："<<tree.DepthTree(tree.GetRoot())<<endl;
    	cout<<"第三层结点个数为:"<<tree.Knum(tree.GetRoot(), 3)<<endl;
    	cout<<"总结点个数为："<<tree.TreeNum(tree.GetRoot())<<endl;
    	Node *s = tree.Find(tree.GetRoot(), 5);
    	cout<<s->Data()<<endl;
    
    }