二叉树的性质：
1、在二叉树的第i层上至多有个结点（i>=1）。
2、深度为k的二叉树至多有个结点（k>=1）。
3、对任何一棵二叉树T，如果其终端结点数为，度为2的结点数为，则=+1。
4、具有n个结点的完全二叉树的深度为⌊⌋+1（⌊x⌋表示下取整）。
5、如果对一棵有n个结点的完全二叉树（其深度为⌊⌋+1）的结点按层序编号（从第1层到第⌊⌋+1层，每层从左到右），对任一结点i（）有：
①如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点⌊i/2⌋。
②如果n<2i，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
③如果n<2i+1，则结点i无右孩子（结点i为叶子结点）；否则其右孩子是结点2i+1。
#include<iostream> using namespace std; #define TRUE 1 #define FALSE 0 typedef char Elemtype; //二叉链表结点结构定义 typedef struct Node //结点结构 { Elemtype data; //结点数据 struct Node *L; //左孩子指针 struct Node *R; //右孩子指针 }Node,*BTree; int depth=0; //二叉树前序遍历递归算法 void PreOrderTraverse(BTree T) { if(T==NULL) return; cout<<T->data; PreOrderTraverse(T->L); PreOrderTraverse(T->R); } //二叉树中序遍历递归算法 void MiddleOrderTraverse(BTree T) { if(T==NULL) return; MiddleOrderTraverse(T->L); cout<<T->data; MiddleOrderTraverse(T->R); } //二叉树后序遍历递归算法 void PostOrderTraverse(BTree T) { if(T==NULL) return; PostOrderTraverse(T->L); PostOrderTraverse(T->R); cout<<T->data; } //按前序输入二叉树中结点的值，#表示空树，构造二叉链表表示二叉树T void CreateBTree(BTree *T) { Elemtype e; cin>>e; if(e=='#') *T=NULL; else { (*T)=(Node*)malloc(sizeof(Node)); (*T)->data=e; CreateBTree(&(*T)->L); CreateBTree(&(*T)->R); } } //按前序计算二叉树的深度 void PreTreeDepth(BTree T,int h) { if(T==NULL) return; if(h>depth) depth=h; PreTreeDepth(T->L,h+1); PreTreeDepth(T->R,h+1); } int main() { BTree T; //输入ab#d##c## CreateBTree(&T); PreTreeDepth(T,1); cout<<depth<<endl; PreOrderTraverse(T); return 0; }
