摘要

二叉树是一种非常重要的数据结构，今天我们来讲讲它。

滚粗。。。老子不是遇到很好的知识点，我才懒得理你呢。。。

重要特性

以下性质暗含root node 为第一层

第i层上顶多有2^(i-1)个节点。

证明：数学归纳法。

i=1时，显然2^(1-1) = 2^0 = 1个节点是对的

现在假设对所有的j，1<=j<i,第j层上至多有2^(j-1)个节点，那么可以证明j=i时命题也成立。

由归纳假设，第i-1层上至多有2^(i-2)个节点，由于二叉树的每个度最多为2，故第i层上节点数为第i-1层上的2倍，即2*2^(i-2).

深度为k的二叉树最多有2^k - 1个节点。

证明：根据上面的1，每层最多节点数之和是一个等比数列，故证之。

对于任何一棵二叉树T，其终端节点（叶子节点）为n0，度为2的节点数为n2，则n0= n2+1

证明：设度为1的节点为n1，则二叉树T中节点总数n等于n=n1+n2+n0. 如二叉树T分枝数为B，因为二叉树中除了根节点没有入度，其余节点都有一个入度，所以n=B+1.又因为这些分支由度为1或者2的节点射出的，则B=n1+2n2，所以有 1+n1+2n2=n1+n2+n0 ==> n0=n2+1

具有N个节点的完全二叉树的深度为floor(LOG2N) + 1. (这里是以2为低，对数为N的运算)

以数组表示二叉树

如果使用数组代表二叉树的话，那么数组里的元素依次就是从根节点水平方向读取来的 (也就是依照层进行读取的)

如果根节点在数组的下标是从1开始,那么就有如下性质：

PARENT(i)		return floor(i/2)

LEFT(i)			return 2i

RIGHT(i)		return 2i + 1

如果根节点从数组下标为0开始，那么有如下性质：

PARENT(i)		return floor[(i-1)/2]

LEFT(i)			return 2*i+1

RIGHT(i)		return 2i + 2

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

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

struct TreeNode *newNode(int data) {
	struct TreeNode *p = (struct TreeNode *)malloc(sizeof(struct TreeNode));
	p->val = data;
	p->left = p->right = NULL;
}
struct TreeNode *createBinaryTree(struct TreeNode *root,int *array, int pos, int nums) {
	if ( pos < nums) {
		struct TreeNode *p = newNode(array[pos]);
		root = p;

		// left
		root->left = createBinaryTree(root->left, array, 2*pos + 1, nums);
		root->right = createBinaryTree(root->right, array, 2*pos +2, nums);

	}
	return root;

}
void show(struct TreeNode *p) {
	if(p == NULL)
		return ;
	else {
		show(p->left);
		if(p->val == -1)
			printf("#\t");
		else
			printf("%d\t", p->val);
		show(p->right);
	}
}
int main() {
	//int a[] = {1,4,5,1,9,6,5};
	int a [] = {1,2,3,4,-1,-1,7,-1,9,-1,-1,-1,-1,4};
	int n = sizeof(a)/sizeof(a[0]);
	struct TreeNode *root = createBinaryTree(root,a, 0,n);
	show(root);
	printf("\n");
}

上面的代码就是按层次遍历依次读进二叉树，-1代表空节点。打印的时候是先打印左孩子，再是根节点，最后是右节点。

下面可以看做是有关树的API操作。

以链表表示二叉树

typedef struct Node{
    struct Node* left;
    struct Node* right;
    int data;
}Node;

二叉树的几个操作

新建一个二叉树的结点

Node* newNode(int data)
{
    Node* node=(Node*)malloc(sizeof(Node));
    node->left=node->right=NULL;
    node->data=data;
    return node;
}

得到二叉树的高度

/* 将root == NULL的返回值置为-1或者0，结果不一样*/
int getHeight(Node* root) {
	if(root == NULL)
		return -1;
    /* 返回为0， 结果是从根节点到叶子节点的节点数，
    *  返回为-1， 是经历的路径长度 */
	int left_height = getHeight(root->left);
	int right_height = getHeight(root->right);
	return (left_height > right_height ? left_height  : right_height ) + 1 ;
}

计算节点的数目

/* The number of node*/
int node_num_tree(Node* root)
{
    if(root == NULL)
        return 0;
    /* 这里的返回 0 还是有区别的 */
    return 1 + node_num_tree(root->left) + node_num_tree(root->right);
}

计算叶子的数目

/* the numbers of leaves */
int leaf_num_tree(Node* root)
{
    if(root == NULL)
        return 0;
    if(root->left == NULL && root->right == NULL)
        return 1;
    return leaf_num_tree(root->left) + leaf_num_tree(root->right);

}

代码

二叉树的操作

摘要