《MY数据结构与算法》----树结构

快来打我* 2022-05-18 11:07 204阅读 0赞

# 一：常见树结构介绍 #

**完全二叉树：**若二叉树的高度是h，除第h层之外，其他（1~h-1）层的节点数都达到了最大个数，并且第h层的节点都连续的集中在最左边。想到点什么没？实际上，完全二叉树和堆联系比较紧密哈~~~

**满二叉树：**除最后一层外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点。

**哈夫曼树：**又称为最优数，这是一种带权路径长度最短的树。哈夫曼编码就是哈夫曼树的应用。

**平衡二叉树：**所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过 1。

**红黑树：**红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

# 二：代码实现 #

**普通二叉树**实现常用功能，树的创建，前中后序遍历，层次遍历，叶子节点个数，等。

注：关于树的知识点，还有**二叉排序树**，**平衡二叉树**，**多路查找树（B树）**，**红黑树**，等特殊的二叉树。  
我们常用这些特殊的二叉树来进行查找操作，关于这些特殊的二叉树的创建，销毁，增删改查等操作。和具体的介绍。待后面有时间再总结吧。

#include <iostream>
    #include <deque>
    #include <stack>
    
    using namespace std;
    
    class BinTreeNode {
    
    private :
    	int data;
    	BinTreeNode * left ;
    	BinTreeNode * right ;
    
    public :
    	BinTreeNode(int val=-1 ,BinTreeNode * pLeft=NULL , BinTreeNode * pRight=NULL): data(val),left(pLeft),right(pRight) {
    
    	}
    	~BinTreeNode() {
    
    	}
    	
    	void setData( int val) {
    		data = val;
    	}
    	int getData() {
    		return data;
    	}
    	void setLeft(BinTreeNode * pLeft) {
    		left = pLeft;
    	}
    	BinTreeNode * getLeft() {
    		return left;
    	}
    	void setRight(BinTreeNode * pRight) {
    		right = pRight;
    	}
    	BinTreeNode * getRight() {
    		return right;
    	}
    };
    
    class BinTree {
    
    private :
    	BinTreeNode * root;
    
    public :
    	BinTree( BinTreeNode * pRoot=NULL) {
    		root = pRoot;	
    	}
    	~BinTree() {
    	}
    
    	void setRoot(BinTreeNode * pRoot) {
    		root = pRoot;
    	}
    	BinTreeNode * getRoot() {
    		return root;
    	}
    
    	BinTreeNode * create_tree(void) ;
    	void pre_order( BinTreeNode * root) ;
    	void level_order(BinTreeNode * root);
    	int get_leaf_num(BinTreeNode * root);
    	int get_tree_height(BinTreeNode * root);
    	bool is_in_tree(BinTreeNode * r , BinTreeNode * t);
    	BinTreeNode * get_nearest_common_father(BinTreeNode * root , BinTreeNode * p1 , BinTreeNode *p2);
    
    };
    
    
    BinTreeNode * BinTree::get_nearest_common_father( BinTreeNode * r , BinTreeNode * p1 ,BinTreeNode * p2)
    {
    	if( NULL == r )
    		return NULL;
    	
    	if( true==is_in_tree(p1,p2) ) {
    		return p1;
    	} else if ( true == is_in_tree(p2,p1) ) {
    		return p2;
    	} else {
    
    		bool p1InLeft = is_in_tree(r->getLeft() , p1);		
    		bool p2InLeft = is_in_tree(r->getLeft() , p2);		
    		bool p1InRight = is_in_tree(r->getRight() , p1);		
    		bool p2InRight = is_in_tree(r->getRight() , p2);		
    
    		if( (p1InLeft==true&&p2InRight) || (p1InRight==true && p2InLeft==true) )
    			return r;
    		else if (p1InLeft==true&& p2InLeft==true) {
    			return get_nearest_common_father(r->getLeft() , p1,p2);
    		}else if (p2InRight && p1InRight) {
    			return get_nearest_common_father(r->getRight() , p1,p2);
    		}else {
    			return NULL;
    		}
    	}
    }
    
    bool BinTree::is_in_tree(BinTreeNode * r , BinTreeNode * t) {
    	if( NULL == r )
    		return false;
    	else if( r==t)
    		return true;
    	else {
    		return is_in_tree(r->getLeft(),t) || is_in_tree(r->getRight() , t);
    	}
    }
    
    
    int BinTree::get_tree_height(BinTreeNode * root) {
    	if( NULL == root )
    		return 0;
    	else if( (NULL==root->getLeft()) && (NULL==root->getRight()) ) {
    		return 1;
    	}else {
    		int lNum = get_tree_height(root->getLeft());
    		int rNum = get_tree_height(root->getRight());
    
    		return lNum>rNum ? lNum+1 : rNum+1;
    	}
    }
    
    BinTreeNode * BinTree::create_tree() {
    	char item;
    	BinTreeNode * root=NULL;
    	cin >> item;
    	if(item != '#') {
    		root = new BinTreeNode(item-'0');
    		root->setLeft(create_tree());
    		root->setRight(create_tree());
    	}else {
    		return root;
    	}
    }
    
    void BinTree::pre_order( BinTreeNode * pRoot )  {
    
    	if( NULL == pRoot )
    		return ;
    	
    	cout << pRoot->getData() << " ";
    	pre_order(pRoot->getLeft());
    	pre_order(pRoot->getRight());
    }
    
    void BinTree::level_order( BinTreeNode * pRoot)
    {
    	if( NULL==pRoot )
    		return ;
    	deque<BinTreeNode * >q;
    	q.push_back(pRoot);
    	while(q.empty()==false) {
    		BinTreeNode * pTemp = q.front();
    		cout << pTemp->getData() << " ";
    		q.pop_front();
    		if( NULL!=pTemp->getLeft() )
    			q.push_back(pTemp->getLeft());
    		if( NULL!=pTemp->getRight() )
    			q.push_back(pTemp->getRight());
    	}
    	
    	
    }
    
    int BinTree::get_leaf_num( BinTreeNode * r ) {
    	if( NULL == r )
    		return 0;
    	else if( (NULL==r->getLeft()) && (NULL==r->getRight()) ) {
    		return 1;
    	}
    	else {
    		return get_leaf_num(r->getRight()) + get_leaf_num(r->getLeft());
    	}
    }
    
    
    int main()
    {
    	BinTree tree;
    	tree.setRoot(tree.create_tree());
    	tree.pre_order(tree.getRoot());
    	cout << endl;
    	tree.level_order(tree.getRoot());
    	cout << endl;
    
    	cout << "叶子节点个数：" << tree.get_leaf_num( tree.getRoot() );
    	cout << endl;
    	
    	cout << "树的深度： " << tree.get_tree_height( tree.getRoot() );
    	cout << endl;
    
    	BinTreeNode  *p1 = tree.getRoot()->getRight()->getLeft();
    	BinTreeNode  *p2 = tree.getRoot()->getRight()->getRight();
    	cout << p1->getData() << " and " << p2->getData() << " common father : " << tree.get_nearest_common_father(tree.getRoot(),p1,p2)->getData() << endl;
    	
    }