数据结构（C语言）-二叉树-学习笔记06

• 1. 基本介绍
• 2. 二叉树性质
• 3. 顺序存储
• 4. 链式存储
• • 4.1 定义
  • 4.2 bitree_create()
  • 4.3 遍历

所有代码实现：Tian-hy/c_ds

• 以下图为例，1是根节点，根节点没有父节点
• 2和3是1的子节点，2是左子节点，3是右子结点，1是2和3的父节点
• 树高为4
• 8、5、9、10和7是叶节点，叶结点没有子节点

• 二叉树的第i层上最多有 2 i − 1 2^{i-1} 2i−1个节点

• 一个高为i的二叉树最多有 2 i − 1 2^i-1 2i−1个节点

• 特殊二叉树

  • 满二叉树：一个高为i的二叉树且有 2 i − 1 2^i-1 2i−1个节点
  • 完全二叉树：只有最下面两层有度数小于2的节点，且最下面的叶节点集中在最左边的若干位置上
    

• 有n个节点的完全二叉树的深度是 f l o o r ( l o g 2 n ) + 1 floor(log_2^n)+1 floor(log2n​)+1

• 假设一个完全二叉树有n个节点
• 完全二叉树的编号方式如上图所示
• 若父节点是 i i i，当 2 ∗ i ≤ n 2*ile n 2∗i≤n则有左子节点，左子节点是 2 ∗ i 2*i 2∗i
• 若父节点是 i i i，当 2 ∗ ( i + 1 ) ≤ n 2*(i+1)le n 2∗(i+1)≤n则有左子节点，右子节点是 2 ∗ ( i + 1 ) 2*(i+1) 2∗(i+1)
• 假设子节点编号是i，父节点编号是 f l o o r ( i / 2 ) floor(i/2) floor(i/2)
• 当i为奇数且不为1时，有左兄弟，左兄弟节点是 i − 1 i-1 i−1；否则则没有左兄弟
• 当i为偶数且小于n时，有右兄弟，右兄弟节点是 i + 1 i+1 i+1；否则则没有右兄弟

#ifndef _TREE_H_
#define _TREE_H_

typedef char data_t;

typedef struct node_t{
	data_t data;
	struct node_t *lchild, *rchild;
}bitree;

bitree *bitree_create();
void preorder(bitree *r);
void inorder(bitree *r);
void postorder(bitree *r);
void layerorder(bitree *r);

#endif

bitree *bitree_create(){
	data_t ch;
	scanf("%c", &ch);
	if (ch == '#')
		return NULL;
	bitree *p;
	if ((p=(bitree *)malloc(sizeof(bitree))) == NULL){
		printf("malloc failedn");
		return NULL;
	}
	p->data = ch;
	p->lchild = bitree_create();
	p->rchild = bitree_create();
	return p;
}

可以通过递归来解决问题，之后都以下面这棵树举例，创建树时在终端输入AB#CD###E#FGH##I###

1. 先序遍历
   • 先访问树根，再访问左子树，最后访问右子树
   • 举例：ABCDEFGHI
2. 中序遍历
   • 先访问左子树，再访问树根，最后访问右子树
   • 举例：BDCAEHGIF
3. 后序遍历
   • 先访问左子树，再访问右子树，最后访问树根
   • 举例：DCBHIGFEA
4. 层次遍历
   • 需要依靠一个队列来实现这个功能
   • 举例：ABECFDGHI

• 实现

void preorder(bitree *r){
	if (r == NULL){
		return;
	}
	printf("%c", r->data);
	preorder(r->lchild);
	preorder(r->rchild);
}

void inorder(bitree *r){
	if (r == NULL){
		return;
	}
	inorder(r->lchild);
	printf("%c", r->data);
	inorder(r->rchild);
}

void postorder(bitree *r){
	if (r == NULL){
		return;
	}
	postorder(r->lchild);
	postorder(r->rchild);
	printf("%c", r->data);
}


void layerorder(bitree *r){
	linkqueue *lq;
	if ((lq = create()) == NULL)
		return;

	if (r == NULL)
		return;
	printf("%c", r->data);
	enqueue(lq, r);
	while (!empty(lq)){
		r = dequeue(lq);
		if (r->lchild){
			printf("%c", r->lchild->data);
			enqueue(lq, r->lchild);
		}
		if (r->rchild){
			printf("%c", r->rchild->data);
			enqueue(lq, r->rchild);
		}
	}
}