二叉树的一些特点

性质

1. 第i层的节点数为 2^(i-1);
2. 深度为k的节点数为2^k-1 (k>=1);
3. n0=n2+1 n0为度为0的节点就是叶节点，n2为度为2的节点
4. n个节点数，则深度为(log2n)+1
5. ①如果i>1,双亲节点就是i/2;②2i>n结点i无左儿子，否则左孩子节点是2i;③2i+1>n则节点没有右孩子，否则右
   孩子为2i+1;

二叉树的遍历

二叉树有前序遍历，中序遍历和后续遍历。

如上图所示的一棵二叉树，对应的遍历结果分别是：

1. 前序（NLR）：A B D C E G H F I
2. 中序（LNR）：D B A G E H C F I
3. 后序（LRN）：D B G H E I F C A
4. 层序：A B C D E F G H I

按照程序的思想去理解这三种遍历

前序遍历

1
2
3
4
5
6
7

void preOrderTraverse(Bitree T){
   if(T == NULL)
       return;
   printf("%d",T->val);
   preOrderTraverse(T->lchild);//先序遍历左子树
   preOrderTraverse(T->rchild);//先序遍历右子树
}

中序遍历

1
2
3
4
5
6
7

void preOrderTraverse(Bitree T){
   if(T == NULL)
       return;
   preOrderTraverse(T->lchild);//中序遍历左子树
   printf("%d",T->val);
   preOrderTraverse(T->rchild);//中序遍历右子树
}

后序遍历

1
2
3
4
5
6
7

void preOrderTraverse(Bitree T){
   if(T == NULL)
       return;
   printf("%d",T->val);
   preOrderTraverse(T->lchild);//后序遍历左子树
   preOrderTraverse(T->rchild);//后序遍历右子树
}

推导遍历结果

已知前序遍历为ABCDEF 中序遍历为CBAEDF 求后序遍历结果

因为先序遍历可以知道根节点，中序遍历可以知道左右树。
所以A为根，CB为左子树，EDF为右子树。
CB当中B为根,B为A的左儿子，C为B的儿子，因为在中序遍历中C先打印做C为B的左儿子。
DEF中D为根，E为D的左儿子，F为右儿子。
图1

图2

图3

已知中序是ABCDEFG,后续是BDCAFGE,求先序遍历的结果。

根节点可以通过后续得知，中序知道左右子树，所以可以求出先序。
结果为EACBDGF
注意：前序遍历和后续遍历结果知道不能求出中序，因为两者都是只能得出根节点，左右子树不能确定。