二叉树的基本性质与遍历

二叉树：

就是一棵树中每个结点最多只有两个结点，可以没有结点，也可以只有一个结点，也可以为空结点

下面说一下二叉树的常见形态：

        

满二叉树与完全二叉树的区别：

        满二叉树就是除了叶子结点之外，每一个结点都有两个孩子

        完全二叉树就是每一个结点不一定有两个孩子，但是如果出现在同一层，完全二叉树结点的i位置与满二叉树结点的 i位置编号相同，就是完全二叉树。

        所以，满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树

然后来说一下二叉树的性质：

        1.在二叉树的i层最多有2^i-1个结点（i>0）

        2.深度为k的二叉树最多有2^k - 1个结点(k>0)

        3.对于任何一棵二叉树，若度为2的结点数有n2个，则叶子数n0必定为n2+1(n0=n2+1)

        4.具有n个结点的完全二叉树深度必为

         5.对于完全二叉树，从上到下，从左到右，则编号为i的结点，其左孩子必为2i,右孩子编号为2*i + 1，其双亲的编号必为i/2(i=1时候为根)

二叉树的遍历：

        大概会分为三种情况，这三种情况的讨论，就是根据到底是先遍历根，还是在中间遍历根，还是说在最后遍历根，也就分为了先序遍历（DLR）,中序遍历(LDR),后序遍历（LRD）

        D：根 L: 左结点 R:右结点

        先来看一个二叉树：

        

        先来说一下先序遍历(DLR)

                先根在左在右：比如一个函数r(从A传入结点),然后先把A打印，毕竟是先序嘛，然后去遍历左边，也就是走下面遍历

                

                这边函数栈就是

                 

         

话不多说，直接上代码：

        

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct _binary_node binary_node;

struct _binary_node
{
	char ch;
	binary_node *lchild;
	binary_node *rchild;
};

void recursion_print(binary_node *node)
{
	if (node == NULL) {
		return;
	} 

	printf("%c ", node->ch);
	recursion_print(node->lchild);
	recursion_print(node->rchild);
}

int main()
{
	//靠靠靠靠靠靠靠
	binary_node node_a = { 'A', NULL, NULL };
	binary_node node_b = { 'B', NULL, NULL };
	binary_node node_c = { 'C', NULL, NULL };
	binary_node node_d = { 'D', NULL, NULL };
	binary_node node_e = { 'E', NULL, NULL };
	binary_node node_f = { 'F', NULL, NULL };


	node_a.lchild = &node_b;
	node_a.rchild = &node_c;

	node_b.rchild = &node_e;
	node_b.lchild = &node_d;

	node_c.rchild = &node_f;

	//靠靠
	recursion_print(&node_a);
	return 1;
}

 运行结果：

        

  当然了，二叉树肯定不至于递归，所以，比如计算二叉树叶子的数目，二叉树的高度，又比如拷贝一棵二叉树，下面上完整代码：

binary_tree.c

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct _binary_node binary_node;

struct _binary_node
{
	char ch;
	binary_node *lchild;
	binary_node *rchild;
};

void recursion_print(binary_node *node)
{
	if (node == NULL) {
		return;
	} 

	printf("%c ", node->ch);
	recursion_print(node->lchild);
	recursion_print(node->rchild);
}

void calc_leaf_num(binary_node *node,int *p)
{
	//程序的结束条件
	if(node == NULL) {
		return ;
	}
	//left and right is null
	if(node->lchild == NULL && node->rchild == NULL) {
		(*p)++;
	}
	calc_leaf_num(node->lchild,p);//传入计算数量变量的地址
	calc_leaf_num(node->rchild,p);
}


//计算树高度
int get_tree_high(binary_node *node)
{
	if(node == NULL) {
		return 0;
	}
	//递归计算左右两边树的高度
	int left_high = get_tree_high(node->lchild);
	int right_high = get_tree_high(node->rchild);
	return left_high > right_high ? left_high + 1 : right_high + 1;
}

//拷贝二叉树就是在堆上面开辟一个空间
//来存放二叉树的每一个结点
//最后返回头部结点
binary_node* copy_tree(binary_node *node)
{
	if(node == NULL){
		return NULL;
	}
	
	//还是要遍历左树，在遍历右树
	binary_node* lnode = copy_tree(node->lchild);
	binary_node* rnode = copy_tree(node->rchild);
	//每一个结点都要干一件事儿
	binary_node *new_node = (binary_node*)malloc(sizeof(binary_node));
	if(new_node != NULL) {
		new_node->ch = node->ch;
		new_node->lchild = lnode;
		new_node->rchild = rnode;
	}
	return new_node;
}

//释放拷贝的这棵树
void free_tree(binary_node *node)
{
	if(node == NULL) {
		return;
	}
	free_tree(node->lchild);
	free_tree(node->rchild);
	//在此之前看一下被释放的结点
	printf("%c被释放了\n",node->ch);
	free(node);//释放这个结点
}
	
	
int main()
{
	binary_node node_a = { 'A', NULL, NULL };
	binary_node node_b = { 'B', NULL, NULL };
	binary_node node_c = { 'C', NULL, NULL };
	binary_node node_d = { 'D', NULL, NULL };
	binary_node node_e = { 'E', NULL, NULL };
	binary_node node_f = { 'F', NULL, NULL };


	node_a.lchild = &node_b;
	node_a.rchild = &node_c;

	node_b.rchild = &node_e;
	node_b.lchild = &node_d;

	node_c.rchild = &node_f;

	recursion_print(&node_a);

	int leaf_num = 0;

	calc_leaf_num(&node_a,&leaf_num);	
	
	printf("叶子结点数目为:%d\n",leaf_num);

	int tree_high = get_tree_high(&node_a);

	printf("叶子数目为:%d\n",tree_high);

	//拷贝二叉树
	binary_node *node = copy_tree(&node_a);

	//然后递归遍历一下这个二叉树
	printf("\n-------------\n");
	recursion_print(node);
	printf("\n-----\n");
	//释放拷贝的每一个结点
	
	//二叉树非递归遍历
	
	free_tree(node);
	return 1;
}