【数据结构 - - - 二叉树】一篇文章搞懂二叉树设计、相关操作及OJ题

朱雀 2022-12-04 08:40 64阅读 0赞

# 二叉树 #

## 二叉树概念及结构 ##

1.  **定义**：我们将满足以下两个条件的树形结构叫做**二叉树**：①每个结点的度都**不大于2**；②每个结点的孩子**结点次序**不能任意颠倒
2.  **二叉树的5种基本形态**：空二叉树、只有根结点的二叉树、只有左子树的二叉树、只有右子树的二叉树、左右子树都非空的二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70_pic_center][]

## 二叉树的结构定义 ##

> 一个二叉树结点由三部分组成：数据域、左孩子指针域、右孩子指针域

typedef char ET;	//防止将二叉树中的数据类型写死了
    
    typedef struct BinaryTreeNode
    { 
    	ET data;
    	BinaryTreeNode* leftNode;
    	BinaryTreeNode* rightNode;
    }BTNode;
    
    typedef BTNode* BTree;	//BTree是一个二叉树结点的指针，指向二叉树的根结点

## 二叉树的初始化 ##

void BinaryTreeInitial(BTree *t){ 
    	*t = NULL;	//指针指向NULL
    }

## 二叉树的创建 ##

### 1.通过键盘输入创建二叉树 ###

> 通过键盘输入来创建一颗二叉树，’\#'字符代表建树结束

void BinaryTreeCreate(BTree *t){ 
    	assert(t != NULL);
        
    	ET value;
    	scanf("%c", &value);
        
    	if (value == '#')	//#代表建树结束 
    		*t = NULL;
    	else
        { 
    		*t = (BTNode*)malloc(sizeof(BTNode));
    		assert((*t) != NULL);
    		(*t)->data = value;
            
    		BinaryTreeCreate(&(*t)->leftNode);
    		BinaryTreeCreate(&(*t)->rightNode);
    	}
    }

### 2.通过键盘输入创建二叉树并获得该树 ###

> 通过键盘输入来创建一颗二叉树，’\#'字符代表建树结束，并返回一个指向该树根结点的指针

BTree BinaryTreeGetTree(){ 
    
    	ET val;
    	scanf("%c", &val);
    
    	if (val == '#')
    		return NULL;
    	else
    	{ 
    		BTNode* t = (BTNode*)malloc(sizeof(BTNode));	//创建父结点
    		t->data = val;
    		t->leftNode = BinaryTreeGetTree();				//创建左子结点
    		t->rightNode = BinaryTreeGetTree();				//创建右子结点
    		return t;
    	}
    }

### 3.通过形参中的字符串创建一颗二叉树并获得该树 ###

> 通过形参传入一个字符串，自动根据字符串创建二叉树，并返回指向该树根结点的指针
> 
> 通过变量i来控制在递归中对于字符数组的访问

BTree BinaryTreeStrToTree(const char* str,int* i){ 
    	assert(str != NULL);
    	if (str[*i] == '\0' || str[*i] == '#')
    		return NULL;
    	else
    	{ 
    		BTNode* t = (BTNode*)malloc(sizeof(BTNode));
    		t->data = str[*i];
    		(*i)++;
    		t->leftNode = BinaryTreeStrToTree(str,i);
    		(*i)++;
    		t->rightNode = BinaryTreeStrToTree(str,i);
    		return t;
    	}
    }

--------------------

**☆☆错误写法**

> 错误原因：递归返回时，指针指向未改变

BTree BinaryTreeStrToTree(const char* str){ 
    	assert(str != NULL);
    	if (*str == '\0' || *str == '#')
    		return NULL;
    	else
    	{ 
    		BTNode* t = (BTNode*)malloc(sizeof(BTNode));
    		t->data = *str;
    		t->leftNode = BinaryTreeStrToTree(++str);
    		t->rightNode = BinaryTreeStrToTree(++str);
    		return t;
    	}
    }

### 4.通过前序遍历和中序遍历创建二叉树 ###

> vlr：前序遍历产生的数据字符串
> 
> lvr：中序遍历产生的数据字符串
> 
> n：结点个数

BTree BinaryTree_VLR_LVR_To_Tree(const char* vlr, const char* lvr,int n){ 
    
    	int k = 0;     
    	while ((*vlr) != (*lvr))
    	{   
    		lvr++;
    		k++;
    	} 
    	if ((*vlr) == '\0')
    		return NULL;
    	else
    	{ 
    		BTNode* t = (BTNode*)malloc(sizeof(BTNode));
    		t->leftNode = BinaryTree_VLR_LVR_To_Tree(vlr, lvr - k, k - 1);
    		t->rightNode = BinaryTree_VLR_LVR_To_Tree(vlr + k, lvr, n - k - 1);
    	}
    }

## 二叉树的遍历 ##

### 1.先序遍历\_递归算法 ###

> 根->左子树->右子树

void BinaryTreeVLR(BTree t){ 
    	if (t != NULL){ 
    		printf("%c ", t->data);
    		BinaryTreeVLR(t->leftNode);
    		BinaryTreeVLR(t->rightNode);
    	}
    }

### 2.中序遍历\_递归算法 ###

> 左子树->根->右子树

void BinaryTreeLVR(BTree t){ 
    	if (t != NULL){ 
    		BinaryTreeLVR(t->leftNode);
    		printf("%c ", t->data);
    		BinaryTreeLVR(t->rightNode);
    	}
    }

### 3.后序遍历\_递归算法 ###

> 左子树->右子树->根

void BinaryTreeLRV(BTree t){ 
    	if (t != NULL){ 
    		BinaryTreeLRV(t->leftNode);
    		BinaryTreeLRV(t->rightNode);
    		printf("%c ", t->data);
    	}
    }

### 4.层次遍历 ###

> 一层一层从左往右访问数据
> 
> 借助**队列**数据结构来实现层次遍历

void BinaryTreeLevel(BTree t){ 
    	if (t != NULL){ 
    		LinkedQueue Q;
    		LinkedQueueInit(&Q);
    
    		LinkedQueueIn(&Q, t);
    		while (!IsEmpty(&Q)){ 	//判断队列是否为空
    			BTNode* p = LinkedQueueGetFront(&Q);	//获取队列队首元素
    			LinkedQueueOut(&Q);						//出队
    			printf("%c ", p->data);
    			if (p->leftNode != NULL)
    				LinkedQueueIn(&Q, p->leftNode);		//左孩子入队
    			if (p->rightNode != NULL)
    				LinkedQueueIn(&Q,p->rightNode);		//右孩子入队
    		}
    	}
    }

### 5.三种遍历方式的非递归算法 ###

> 借助**栈**数据结构来实现非递归遍历

void BinaryTreeVLR_Nor(BTree t){ 
    	if (t != NULL){ 
    		LinkStack st;
    		LinkedStackInitial(&st);
    		LinkedStackAddTop(&st, t);
    		while (LinkedStackIsEmpty(&st))
    		{ 
    			BTNode* p = LinkedStackGetTop(&st);
    			LinkedStackDeletePop(&st);
    			printf("%c ", p->data);
    			if (p->rightNode != NULL)
    				LinkedStackAddTop(&st, p->rightNode);
    			if (p->leftNode != NULL)
    				LinkedStackAddTop(&st, p->leftNode);
    		}
    		LinkedStackDestroy(&st);
    	}
    }
    void BinaryTreeLVR_Nor(BTree t){ 
    	if (t != NULL){ 
    		LinkStack st;
    		LinkedStackInitial(&st);
    		do 
    		{ 
    			while (t != NULL)	//将t置于树的最左侧
    			{ 
    				LinkedStackAddTop(&st, t);
    				t = t->leftNode;
    			}
    			BTNode* p = LinkedStackGetTop(&st);
    			LinkedStackDeletePop(&st);
    			printf("%c ", p->data);
    			if (p->rightNode != NULL)
    				t = p->rightNode;
    		} while (!LinkedStackIsEmpty(&st) || t != NULL);
    	}
    }
    void BinaryTreeLRV_Nor(BTree t){ 
    	if (t != NULL){ 
    		LinkStack st;
    		LinkedStackInitial(&st);
    		BTNode* pre = NULL;
    		do 
    		{ 
    			while (t != NULL)	//将t置于树的最左侧
    			{ 
    				LinkedStackAddTop(&st, t);
    				t = t->leftNode;
    			}
    			BTNode* p = LinkedStackGetTop(&st);
    			
    			
    			if (p->rightNode != NULL || p->rightNode == pre)
    			{ 
    				LinkedStackDeletePop(&st);
    				printf("%c ", p->data);
    				pre = p;
    			}
    			else
    				t = p->rightNode;
    		} while (!LinkedStackIsEmpty(&st));
    	}
    }

## 二叉树的相关操作 ##

### 1.计算树结点个数 ###

int  BinaryTreeSize(BTree t){ 
    	assert(t != NULL);
    	if (t == NULL)
    		return 0;
    	else
    		return BinaryTreeSize(t->leftNode) + BinaryTreeSize(t->rightNode) + 1;
    }

### 2.计算树深度 ###

int  BinaryTreeHeight(BTree t){ 
    	if (t == NULL)
    		return 0;
    	else
    	{ 
    		int left_H = BinaryTreeHeight(t->leftNode);
    		int right_H = BinaryTreeHeight(t->rightNode);
    		return (left_H > right_H ? left_H : right_H) + 1;
    	}
    }

### 3.返回某结点左子树 ###

BTNode* BinaryTreeGetLeftTree(BTNode *p){ 
    	if (p == NULL) return NULL;
    	return p->leftNode;
    }

### 4.返回某结点右子树 ###

BTNode* BinaryTreeGetRightTree(BTNode *p){ 
    	if (p == NULL) return NULL;
    	return p->rightNode;
    }

### 5.按值查找 ###

BTNode* BinaryTreeFindNode(BTree t, ET key){ 
    	if (t->data == key || t == NULL)
    		return t;
    	
    	BTNode* p = BinaryTreeFindNode(t->leftNode, key);
    	if (p != NULL)
    		return p;
    	return BinaryTreeFindNode(t->rightNode, key);
    		
    }

### 6.查找p的父节点 ###

BTNode* BinaryTreeGetParentNode(BTree t, BTNode *p){ 
    	if (t == NULL || p == NULL || t == p) return NULL;
    	if (t->leftNode == p || t->rightNode == p)
    		return t;
    	BTNode* q = BinaryTreeGetParentNode(t->leftNode, p);
    	if (q != NULL)
    		return q;
    	return BinaryTreeGetParentNode(t->rightNode, p);
    }

### 7.拷贝一个二叉树返回 ###

BTNode* BinaryTreeCloneTree(BTree t){ 
    	if (t == NULL) return NULL;
    
    	BTNode* t_copy = (BTNode*)malloc(sizeof(BTNode));
    	assert(t_copy != NULL);
    
    	t_copy->data = t->data;		//克隆父节点
    	t_copy->leftNode = BinaryTreeCloneTree(t->leftNode);		//克隆左子树
    	t_copy->rightNode = BinaryTreeCloneTree(t->rightNode);		//克隆右子树
    	return t_copy;
    }

### 8.判断两个二叉树是否相等 ###

bool BinaryTreeEqualTree(BTree t1, BTree t2){ 
    	if (t1 == NULL && t2 == NULL) return true;
    	if (t1 == NULL || t2 == NULL) return false;
    	return (t1->data == t2->data && 
    		BinaryTreeEqualTree(t1->leftNode, t2->leftNode) && 
    		BinaryTreeEqualTree(t1->rightNode, t2->rightNode));
    }

bool BinaryTreeEqualTree(BTree t1, BTree t2){ 
    	if (t1 == NULL && t2 == NULL) return true;
    	if (t1 == NULL || t2 == NULL) return false;
    	if (t1->data != t2->data)
    		return false;
    	return BinaryTreeEqualTree(t1->leftNode, t2->leftNode) && BinaryTreeEqualTree(t1->rightNode, t2->rightNode);
    }

## 二叉树LeetCode题 ##

### 144.二叉树的前序遍历 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        void _preorderTraversal(TreeNode* p,vector<int>& v)
        { 
            if(p == NULL)
                return;
            else
            { 
                v.push_back(p->val);
                _preorderTraversal(p->left,v);
                _preorderTraversal(p->right,v);
            }
        }
        vector<int> preorderTraversal(TreeNode* root) { 
            vector<int> v;
            _preorderTraversal(root,v);
            return v;
        }
    
    };

### 94.二叉树的中序遍历 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        void _inorderTraversal(TreeNode* p,vector<int>& v)
        { 
            if(p == NULL)
                return;
            else
            { 
                _inorderTraversal(p->left,v);
                v.push_back(p->val);
                _inorderTraversal(p->right,v);
            }
        }
        vector<int> inorderTraversal(TreeNode* root) { 
            vector<int> v;
            _inorderTraversal(root,v);
            return v;
        }
    };

### 145.二叉树的后序遍历 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        void _postorderTraversal(TreeNode* p,vector<int>& v)
        { 
            if(p == NULL)
                return;
            else
            { 
                _postorderTraversal(p->left,v);
                _postorderTraversal(p->right,v);
                v.push_back(p->val);
            }
        }
        vector<int> postorderTraversal(TreeNode* root) { 
            vector<int> v;
            _postorderTraversal(root,v);
            return v;
        }
    };

### 100.相同的树 ###

### 572.另一棵树的子树 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
    bool isSameTree(struct TreeNode* p,struct TreeNode* q){ 
        if(p==NULL && q==NULL)
            return true;
        if(p==NULL || q==NULL)
            return false;
        return (p->val==q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right));
    }
    
    bool isSubtree(struct TreeNode* s, struct TreeNode* t){ 
        if(t == NULL)   return true;
        if(s == NULL)   return false;
        if(s->val == t->val && isSameTree(s,t)){ 
            return true;
        }
        return (isSubtree(s->right,t) || isSubtree(s->left,t));
    }

### 104.二叉树的最大深度 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
    
    
    int maxDepth(struct TreeNode* root){ 
        if(root == NULL)
            return 0;
        if(root->left == NULL && root->right == NULL)
            return 1;
        struct TreeNode* p = root;
        if(p == NULL)
            return 0;
        else
        { 
            int Left_Height = maxDepth(p->left);
            int Right_Height = maxDepth(p->right);
            return (Left_Height > Right_Height ? Left_Height : Right_Height) + 1;
        }
    }

### 110.平衡二叉树 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
    
    int maxDepth(struct TreeNode* root){ 
        if(root == NULL){ 
            return 0;
        }else{ 
            int left_h = maxDepth(root->left);
            int right_h = maxDepth(root->right);
            return (left_h > right_h ? left_h : right_h) + 1;
        }
    }
    bool isBalanced(struct TreeNode* root){ 
        if(root == NULL){ 
            return true;
        }
        return abs(maxDepth(root->left) - maxDepth(root->right)) < 2 && isBalanced(root->left) && isBalanced(root->right);
    }

### 101.对称二叉树 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
    bool _isSymmetric(struct TreeNode* t1,struct TreeNode* t2){ 
        if(t1 == NULL && t2 == NULL)    return true;
        if(t1 == NULL || t2 == NULL)    return false;
        return (t1->val == t2->val) && _isSymmetric(t1->left,t2->right) && _isSymmetric(t1->right,t2->left);
    }
    
    bool isSymmetric(struct TreeNode* root){ 
        if(root == NULL)    return true;
    
        return _isSymmetric(root->left,root->right);
    }

### 606.根据二叉树创建字符串 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
    void _tree2str(struct TreeNode* t, char *str){ 
        if(t == NULL)  return;
        char buf[10] = { 0};
        sprintf(buf,"%d",t->val);
        strcat(str,buf);
    
        if(t->left == NULL){ 
            if(t->right != NULL){ 
                strcat(str,"()");
            }else{ 
                return ;
            }
        }else{ 
            strcat(str,"(");
            _tree2str(t->left,str);
            strcat(str,")");
        }
        
        if(t->right == NULL){ 
            return ;
        }else{ 
            strcat(str,"(");
            _tree2str(t->right,str);
            strcat(str,")");
        }
    }
    
    char * tree2str(struct TreeNode* t){ 
        int n = 50000;
        char *str = (char*)malloc(sizeof(char) * n);
        memset(str,0,n);
    
        _tree2str(t,str);
    
        return str;
    }

### 102.二叉树的层序遍历 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
    
    
    /** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */
    int height(struct TreeNode* root)
    { 
        if(root == NULL)
            return 0;
        else
        { 
            int lefh_h = height(root->left);
            int right_h = height(root->right);
            return (lefh_h>right_h?lefh_h:right_h) + 1;
        }
    }
    
    int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){ 
        if(root == NULL)
        { 
            *returnSize = 0;
            return NULL;
        }
        int max_level = height(root);
        *returnSize = max_level;
    
        int** levelArray = (int**)malloc(sizeof(int*) * max_level);
        *returnColumnSizes = (int*)malloc(sizeof(int) * max_level);
    
        struct TreeNode* q1[1000],*q2[1000];
        int q1_size = 0,q2_size = 0;
    
        q1[0] = root;
        q1_size++;
    
        int level = 0;
        while(level < max_level)
        { 
            levelArray[level] = (int*)malloc(sizeof(int) * q1_size);
            for(int i = 0;i<q1_size;i++)
            { 
                levelArray[level][i] = q1[i]->val;
            }
            (*returnColumnSizes)[level] = q1_size;
    
            for(int i = 0;i<q1_size;i++){ 
                if(q1[i]->left != NULL)
                    q2[q2_size++] = q1[i]->left;
                if(q1[i]->right !=NULL)
                    q2[q2_size++] = q1[i]->right;
            }
    
            memcpy(q1,q2,sizeof(struct TreeNode*) * q2_size);
            q1_size = q2_size;
            q2_size = 0;
            level++;
        }
        return levelArray;
    }

### 236.二叉树的最近公共祖先 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
     bool findNode(struct TreeNode* t,struct TreeNode* p){ 
         if(t == NULL) return false;
         if(p == t) return true;
         return findNode(t->left,p) || findNode(t->right,p);
     }
    struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) { 
        if(root == NULL) return NULL;
        if(p == root || q == root) return root;
    
        bool pInleft,pInright,qInleft,qInright;
        if(findNode(root->left,p))
        { 
            pInleft = true;
            pInright = false;
        }
        else
        { 
            pInleft = false;
            pInright = true;
        }
        if(findNode(root->right,q))
        { 
            qInleft = false;
            qInright = true;
        }
        else
        { 
            qInleft = true;
            qInright = false;
        }
    
        if(pInleft && qInleft)
            return lowestCommonAncestor(root->left,p,q);
        else if(pInright && qInright)
            return lowestCommonAncestor(root->right,p,q);
    
        return root;
    }

### 105.从前序与中序遍历序列构造二叉树 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
    
    
    struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize)
    { 
        if(preorderSize == 0)
            return NULL;
        
        int k = 0;
        while(inorder[k] != preorder[0])	//找根结点
            k++;
        
        struct TreeNode *t = (struct TreeNode*)malloc(sizeof(struct TreeNode));	//创建根结点
        assert(t != NULL);
        t->val = inorder[k];
    
        t->left = buildTree(preorder+1, k, inorder, k);
        t->right = buildTree(preorder+k+1, preorderSize-k-1, inorder+k+1, inorderSize-k-1);
        return t;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/4c9f253067874c5e99e7774f5c8a77e8.png