算法

二叉树是每个结点最多有两个子树的树结构。二叉树有如下类型

  1. 满二叉树

    除了叶子节点其他节点都有两个子节点,且叶子节点都在最后一层。

  2. 完全二叉树

    将满二叉树的最后一层的最右边去掉几个叶子节点,就是完全二叉树

  3. 平衡二叉树

    它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

二叉树的结构简单,应用却很广泛。下面利用 C++ 实现二叉树的构建、操作、判断等函数。

树的样例

先序序列: ABD###CE#G##FH#I##J## 
         A
       /    \
      B        C
     / \    /    \
    D   # E         F
   / \   / \       /  \ 
  #   # #   G     H     J
           / \   / \   / \
          #   # #   I #   #
                   / \
                  #   #                   

接下来我们定义一个二叉树类,实现各种二叉树操作。

1. 二叉树的节点结构

二叉树有两种存储结构:顺序结构和链式结构。一般我比较喜欢用链式结构,下面的代码都是以链式结构讲解。

链式结构要求数据存储在节点中,并且节点需要两个指针分别链接左子节点和右子节点。

struct TreeNode {
	char val;
	TreeNode *lchild;
	TreeNode *rchild;
	TreeNode(char val = '#') : val(val), lchild(NULL), rchild(NULL){}
};

2. 创建二叉树

将数组和索引传入函数,函数会创建一课二叉树并返回根节点。

这里没有做边界检查,如果出现异常那肯定是你传入的字符串有误。

TreeNode* create(char str[], int &i) {
	if (str[i] == '#') return NULL;
	
	TreeNode* node = new TreeNode(str[i]);
	i++;  
	node->lchild = create(str, i);
	i++;
	node->rchild = create(str, i);
	return node;
}

3. 二叉树遍历

  1. 先序遍历

    void preOrder(TreeNode* node){
    	if (node == NULL) return;
       	
    	std::cout << node->val;
    	preOrder(node->lchild);
    	preOrder(node->rchild);
    } 
    
  2. 中序遍历

    void inOrder(TreeNode* node){
    	if (node == NULL) return;
       	
    	inOrder(node->lchild);
    	std::cout << node->val;
    	inOrder(node->rchild);
    } 
    
  3. 后序遍历

    void lastOrder(TreeNode* node){
    	if (node == NULL) return;
       	
    	lastOrder(node->lchild);
    	lastOrder(node->rchild);
    	std::cout << node->val;
    }
    
  4. 层次遍历

    void levelOrder(TreeNode* node){
    	std::queue<TreeNode*> q;
    	q.push(node);
    	while(!q.empty()){
    		TreeNode* currentNode = q.front();
    		q.pop();
    		std::cout << currentNode->val;
       		
    		if(currentNode->lchild) q.push(currentNode->lchild);
    		if(currentNode->rchild) q.push(currentNode->rchild);
    	}
    }
    

4. 二叉树的销毁

void destroy (TreeNode* node){
	if(node){
		destroy(node->lchild);
		destroy(node->rchild);
		delete node;
	}
}

5. 二叉树的深度

int depth(TreeNode* node) {
	if(node == NULL) return 0;
	
	int leftDepth = depth(node->lchild);
	int rightDepth = depth(node->rchild);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

6. 二叉树的节点数

  1. 所有节点

    int nodeNum(TreeNode* node) {
    	if(node == NULL) return 0;
    	return 1 + nodeNum(node->lchild) + nodeNum(node->rchild);
    }
    
  2. 叶子节点

    int leafNum(TreeNode* node){
    	if(node == NULL) return 0;
    	if(node->lchild == NULL && node->rchild == NULL) return 1;
    	return leafNum(node->lchild) + leafNum(node->rchild);
    }
    

7. 平衡二叉树

  1. 判断是否是平衡二叉树

    bool isBalanced(TreeNode* node) {
    	if(node == NULL) return true;
       	
    	int leftDepth = depth(node->lchild);
    	int rightDepth = depth(node->rchild);
       	
    	if(leftDepth - rightDepth <= 1 && rightDepth - leftDepth <= 1) {  // 平衡条件 
    		return isBalanced(node->lchild) && isBalanced(node->rchild);
    	} 
    	return false;
    }
    

8. 判断一个树是否镜像对称

bool isMirror(TreeNode* t1, TreeNode* t2) {
    if(t1 == NULL && t2 == NULL) return true;
    if(t1 == NULL || t2 == NULL) return false;
    if(t1->val == t2->val) {
        return isMirror(t1->left, t2->right)
        && isMirror(t1->right, t2->left);
    }
    return false;
}