二叉树的系列应用

1. 层次遍历求二叉树宽度、高度

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   //设计一个非递归算法求以二叉链表存储的二叉树的高度、最大宽度 //非递归：层次遍历，设置level记录当前结点所在层数，last指向下一层第一个结点的位置 int Btdepth(BiTree T) { if(!T) return 0; int front=-1, rear=-1; int last=0, level=0; int maxWidth=0; //记录最大宽度 BiTree Q[MaxSize]; Q[++rear]=T; //将根结点入队 BiTree p; while(front<rear){ //队不空，则循环 p=Q[++rear]; //队列元素出队，即正在访问的结点 if(p->lchild) Q[++rear]=p->lchild; if(p->rchild) Q[++rear]=p->rchild; if(front == last) 处理该层的最右结点，此时last指向该层最右结点 level++; 层数加1 last = rear; last指向下一层 maxWidth=maxWidth>(last-front) ? maxWidth : (last-front); } return level; }

2. 根结点左右子树叶子结点最远距离

   1 2 3 4 5 6 7 8 9 10 11 12

   //递归： int ldep=0, rdep=0; //左右子树的高度 int Btdepth2(BiTree *T) { if(T == NULL) return 0; ldep=Btdepth2(T->lchild); rdep=Btdepth2(T->rchild); if(ldep>rdep) return ldep+1; //树的高度为子树最大高度加根结点 else return rdep+1; }