二叉树

二叉树T：一个有穷的结点集合。 这个集合可以为空 若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

完全二叉树Complete Binary Tree)有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为i（1 ≤ i ≤ n）结点与满二叉树中编号为 i 结点在二叉树中位置相同

二叉树的遍历

1.先序遍历

遍历过程为： ① 访问根结点； ② 先序遍历其左子树； ③ 先序遍历其右子树。

先序遍历=> A B D F E C G H I void PreOrderTraversal(BinTree BT) { if (BT) { printf(“ % d”, BT->Data); PreOrderTraversal(BT->Left); PreOrderTraversal(BT->Right); } }

2.中序遍历

遍历过程为： ① 中序遍历其左子树； ② 访问根结点； ③ 中序遍历其右子树。

中序遍历=> D B E F A G H C I void InOrderTraversal(BinTree BT) { if (BT) { InOrderTraversal(BT->Left); printf(“ % d”, BT->Data); InOrderTraversal(BT->Right); } }

3.后序遍历

遍历过程为： ① 后序遍历其左子树； ② 后序遍历其右子树； ③ 访问根结点。

后序遍历=> D E F B H G I C A void PostOrderTraversal(BinTree BT) { if (BT) { PostOrderTraversal(BT->Left); PostOrderTraversal(BT->Right); printf(“ % d”, BT->Data); } }

4.层次遍历

遍历过程为：先根结点入队，然后： ① 从队列中取出一个元素； ② 访问该元素所指结点； ③ 若该元素所指结点的左、右孩子结点非空，则将其左、右孩子的指针顺序入队。

层次遍历=> A B C D F G I E H void LevelorderTraversal ( BinTree BT ) { Queue Q; BinTree T; if ( !BT ) return; /* 若是空树则直接返回 */ Q = CreatQueue(); /* 创建空队列Q */ AddQ( Q, BT ); while ( !IsEmpty(Q) ) { T = DeleteQ( Q ); printf("%d ", T->Data); /* 访问取出队列的结点 */ if ( T->Left ) AddQ( Q, T->Left ); if ( T->Right ) AddQ( Q, T->Right ); } }

二叉树的非递归遍历

1.中序遍历非递归遍历算法

*遇到一个结点，就把它压栈，并去遍历它的左子树； *当左子树遍历结束后，从栈顶弹出这个结点并访问它； *然后按其右指针再去中序遍历该结点的右子树。

void InOrderTraversal(BinTree BT) { BinTree T = BT; Stack S = CreatStack(MaxSize); /*创建并初始化堆栈S*/ while (T || !IsEmpty(S)) { while (T) { /*一直向左并将沿途结点压入堆栈*/ Push(S, T); T = T->Left; } if (!IsEmpty(S)) { T = Pop(S); /*结点弹出堆栈*/ printf("]", T->Data); /*（访问）打印结点*/ T = T->Right; /*转向右子树*/ } } }

2.先序遍历非递归遍历算法

*遇到一个结点，就把它压栈，并去遍历它的左子树； *当左子树遍历结束后，从栈顶弹出这个结点并访问它； *然后按其右指针再去中序遍历该结点的右子树。

void InOrderTraversal(BinTree BT) { BinTree T = BT; Stack S = CreatStack(MaxSize); /*创建并初始化堆栈S*/ while (T || !IsEmpty(S)) { while (T) { /*一直向左并将沿途结点压入堆栈*/ printf("]", T->Data); /*（访问）打印结点*/ Push(S, T); T = T->Left; } if (!IsEmpty(S)) { T = Pop(S); /*结点弹出堆栈*/ T = T->Right; /*转向右子树*/ } } }

3.后序遍历非递归遍历算法

*循环遍历当前结点的左孩子并入栈，直到左孩子空 *判断右孩子是否已访问或者空，若是，出栈，指针返回栈顶，回到2；否则将右孩子入栈回到1

void PostorderTraversal( BinTree BT ) { BinTree T = BT, P = NULL; /* P上一个已被访问的结点 */ Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/ while( T || !IsEmpty(S) )/* 树不空或栈不空 */ { while(T)/*一直向左并将沿途结点压入堆栈*/ { Push(S,T); /* 结点压栈(第一次遇到结点) */ T = T->Left;/* 一直向左 */ } if( !IsEmpty(S)) { T = Pop(S); /* 先弹出结点 */ if(T->Right == P || T->Right == NULL) { /* 右孩子已访问或右孩子不存在, 弹出结点 */ printf("]", T->Data); /* 访问结点 */ P = T; /* P指向被访问结点 */ T = NULL; /* 树置空(该树的左\右\根结点已经访问) */ } else { Push(S,T); /* 否则,不应该弹出结点, 结点再次入栈 */ T = T->Right;/* 继续遍历右子树 */ } } } }