[数据结构与算法]C语言----二叉树相关

1，平衡二叉树

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

/**
 * 
 * @param pRoot TreeNode类 
 * @return bool布尔型
 */
int depth(struct TreeNode* pRoot)
{
    if(pRoot == NULL)  return 0;
    int left = depth(pRoot->left);
    if(left == -1)  return -1;
    int right = depth(pRoot->right);
    if(right == -1)  return -1;
    if(abs(left-right)>1)  
        return -1;
    else
        return (left>right?left:right)+1;
}
bool IsBalanced_Solution(struct TreeNode* pRoot ) 
{
    // write code here
    return depth(pRoot) == -1?false:true;
}

?2，二叉树的最大深度

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxDepth(TreeNode* root)
    {
        // write code here
        if(root == NULL) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return (left>right?left:right)+1;
    }
};

3，根据前序和中序重建二叉树

#include<stdio.h>
#include<stdlib.h>
typedef struct BinaryTreeNode{
	int data;
	struct BinaryTreeNode * lchild;
	struct BinaryTreeNode * rchild;
} binarytreenode, *binarytreeroot_ptr;

binarytreeroot_ptr rebulit_binarytree(int *start_preorder, int *end_preorder, int *start_inorder, int * end_inorder);
int Find_location(int n, int *a);
void display_preorder(binarytreeroot_ptr root);
void display_inorder(binarytreeroot_ptr root);
void display_postorder(binarytreeroot_ptr root);
binarytreeroot_ptr construct(int *pre, int *in, int length);
void main(){
	int pre[] = {1,2,4,7,3,5,6,8}, in[] = {4,7,2,1,5,3,8,6}, length;
	length = sizeof(pre)/sizeof(int);
	struct BinaryTreeNode* root;
	root = (struct BinaryTreeNode *)malloc(sizeof(struct BinaryTreeNode));
	root = construct(pre, in, length); 
	display_preorder(root);
	printf("\n");
	display_inorder(root);
	printf("\n");
	display_postorder(root);
	
}
binarytreeroot_ptr construct(int *pre, int *in, int length){初始判断
	if(pre == NULL || in == NULL || length <= 0){
		printf("\t输入非法序列\n");
		exit(1);
	}
	return (binarytreeroot_ptr)rebulit_binarytree(pre, pre + length - 1, in, in + length - 1);
}
binarytreeroot_ptr rebulit_binarytree(int *start_preorder, int *end_preorder, int *start_inorder, int * end_inorder){重建二叉树
	
	int root_location;
	binarytreeroot_ptr root;
	root = (binarytreeroot_ptr)malloc(sizeof(binarytreenode));
	root->data = *start_preorder;
	root->lchild = NULL;
	root->rchild = NULL;
	root_location = Find_location(start_preorder[0],start_inorder);
	if(start_preorder == end_preorder && start_inorder == end_inorder){
		if (*start_preorder == *start_inorder){
			return root;//叶子结点（只有自己，所有的序列都是自己） 
		}
	}
	if(root_location > 0) {
		root->lchild = rebulit_binarytree(start_preorder+1, start_preorder + root_location, start_inorder, start_inorder + root_location - 1);
	}
	if((start_inorder + root_location) < end_inorder){
		root->rchild = rebulit_binarytree(start_preorder + root_location + 1, end_preorder, start_inorder + root_location + 1, end_inorder);
	
	}
	return root; //非叶子结点，赋值完左右子树，返回 
} 
int Find_location(int n, int *a){//返回差值
	int count = 0;
	while(*(a + count) != n){
		count ++;
	}
	//
	return count;
}
void display_preorder(binarytreeroot_ptr root){//前序 输出
	if(root == NULL){
		return ;
	}
	printf("\t%d",root->data);
	display_preorder(root->lchild);
	display_preorder(root->rchild);
}
void display_inorder(binarytreeroot_ptr root){//中序 输出
	if(root == NULL){
		return ;
	}
	display_inorder(root->lchild);
	printf("\t%d",root->data);
	display_inorder(root->rchild);
}
void display_postorder(binarytreeroot_ptr root){//后序 输出
	if(root == NULL){
		return ;
	}
	display_postorder(root->lchild);
	display_postorder(root->rchild);
	printf("\t%d",root->data);
}

4，二叉树的右视图

/* 输出二叉树的右视图 */
void printRightView(TreeNode *pstNode, int iLeval, int *piRight, int *piSize)
{
    if(NULL == pstNode)
        return;
 
    if(iLeval > *piSize)
    {
        *piSize = iLeval;
        piRight[iLeval] = pstNode->val;
    }
 
    printRightView(pstNode->right, iLeval+1, piRight, piSize);
    printRightView(pstNode->left, iLeval+1, piRight, piSize);
 
    return;
}