二叉树结好资料

1、二叉树结点typedef struct BiTNode数据char data;左右孩子指针struct BiTNode *lchild,*rchild;BiTNode,*BiTree;按先序序列创建二叉树int CreateBiTree(BiTree & T)char data;，表示空树按先序次序输入二叉树中结点的值(一个字符), scanf(%c,&data);，表示空树if(data = #)T = NULL; elseT = (BiTree)malloc(sizeof(BiTNode);生成根结点T-data = data;构造左子树CreateBiTree(T-lchild);构造右

2、子树CreateBiTree(T-rchild);return 0;void Visit(BiTree T) if(T-data != #)printf(%c ,T-data);先序遍历void PreOrder(BiTree T)if(T != NULL)访问根节点Visit(T);访问左子结点PreOrder(T-lchild);访问右子结点PreOrder(T-rchild);中序遍历void InOrder(BiTree T)if(T != NULL)访问左子结点InOrder(T-lchild);访问根节点Visit(T);访问右子结点InOrder(T-rchild);后序遍历vo

3、id PostOrder(BiTree T)if(T != NULL)访问左子结点PostOrder(T-lchild);访问右子结点PostOrder(T-rchild);访问根节点Visit(T);/*先序遍历(非递归)思路：访问T-data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T, 出栈，再先序遍历T的右子树。*/void PreOrder2(BiTree T) stackvBiTree stack;p是遍历指针BiTree p = T;栈不空或者p不空时循环while(p II !stack.empty()if(p != NULL)存入栈中stack.push(p)

4、;访问根节点printf(%c ,p-data);遍历左子树p = p-lchild;else退栈p = stack.top();stack.pop();访问右子树p = p-rchild;/whilev2中序遍历【思路】：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子 树。先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T,出栈，访问 T-data,再中序遍历T的右子树。cpp view plaincopyvoid InOrder2(BiTree T)stack stack;/p是遍历指针BiTree p = T;栈不空或者p不空时循环while(p II !

5、stack.empty()if(p != NULL)存入栈中stack.push(p);遍历左子树p = p-lchild;else退栈，访问根节点p = stack.top();printf(%c ,p-data);stack.pop();访问右子树p = p-rchild;/while后序遍历【思路】：T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判 断根结点的左右子树是否均遍历过。cpp view plaincopy后序遍历(非递归)typedef struct BiTNodePostBiTree biTree;char tag;BiTNodePost,*BiTre

6、ePost;void PostOrder2(BiTree T)stackvBiTreePost stack;/p是遍历指针BiTree p = T;BiTreePost BT;栈不空或者p不空时循环while(p != NULL II !stack.empty()遍历左子树while(p != NULL)BT = (BiTreePost)malloc(sizeof(BiTNodePost);BT-biTree = p;访问过左子树BT-tag = L; stack.push(BT);p = p-lchild;左右子树访问完毕访问根节点while(!stack.empty() & (stack.

7、top()-tag = R)BT = stack.top();退栈stack.pop();BT-biTree;printf(%c ,BT-biTree-data);遍历右子树if(!stack.empty()BT = stack.top();访问过右子树BT-tag = R;p = BT-biTree; p = p-rchild;/while层次遍历【思路】：按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队 列。cpp view plaincopy层次遍历void LevelOrder(BiTree T)BiTree p = T;队列queuevBiTree queue;

8、根节点入队queue.push(p);队列不空循环while(!queue.empty()对头元素出队p = queue.front();访问p指向的结点printf(%c ,p-data);退出队列queue.pop();左子树不空，将左子树入队if(p-lchild != NULL) queue.push(p-lchild);右子树不空，将右子树入队if(p-rchild != NULL) queue.push(p-rchild);测试用例：输入：ABC#DE#G#F# 输出：代码：cpp view plaincopy #includeviostream #includevstack #i

9、ncludevqueue using namespace std;二叉树结点typedef struct BiTNode数据char data;左右孩子指针struct BiTNode *lchild,*rchild;BiTNode,*BiTree;按先序序列创建二叉树int CreateBiTree(BiTree & T)char data;，表示空树按先序次序输入二叉树中结点的值(一个字符), scanf(%c,&data);，表示空树if(data = #)T = NULL; elseT = (BiTree)malloc(sizeof(BiTNode);生成根结点T-data = dat

10、a;构造左子树CreateBiTree(T-lchild);构造右子树CreateBiTree(T-rchild);return 0;输出void Visit(BiTree T) if(T-data != #)printf(%c ,T-data);先序遍历void PreOrder(BiTree T)if(T != NULL)访问根节点Visit(T);访问左子结点PreOrder(T-lchild);访问右子结点PreOrder(T-rchild);中序遍历void InOrder(BiTree T)if(T != NULL)访问左子结点InOrder(T-lchild);访问根节点Visi

11、t(T);访问右子结点InOrder(T-rchild);后序遍历void PostOrder(BiTree T)if(T != NULL)访问左子结点PostOrder(T-lchild);访问右子结点PostOrder(T-rchild);访问根节点Visit(T);/*先序遍历(非递归)思路：访问T-data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T, 出栈，再先序遍历T的右子树。*/void PreOrder2(BiTree T)stackvBiTree stack;p是遍历指针BiTree p = T;栈不空或者p不空时循环while(p II !stack.emp

12、ty()if(p != NULL)存入栈中stack.push(p);访问根节点printf(%c ,p-data);遍历左子树p = p-lchild;else退栈p = stack.top(); stack.pop();访问右子树p = p-rchild;/while/*中序遍历(非递归)思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子 树。先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T,出栈，访问 T-data,再中序遍历T的右子树。*/void InOrder2(BiTree T)stackvBiTree stack;/p是遍历指针BiTree

13、p = T;栈不空或者p不空时循环while(p II !stack.empty()if(p != NULL)存入栈中stack.push(p);遍历左子树p = p-lchild;else退栈，访问根节点p = stack.top();printf(%c ,p-data);stack.pop();访问右子树p = p-rchild;/while后序遍历(非递归)typedef struct BiTNodePostBiTree biTree;char tag;BiTNodePost,*BiTreePost;void PostOrder2(BiTree T)stackvBiTreePost st

14、ack;/p是遍历指针BiTree p = T;BiTreePost BT;栈不空或者p不空时循环while(p != NULL II !stack.empty()遍历左子树while(p != NULL)BT = (BiTreePost)malloc(sizeof(BiTNodePost);BT-biTree = p;访问过左子树BT-tag = L;stack.push(BT);p = p-lchild;左右子树访问完毕访问根节点 while(!stack.empty() & (stack.top()-tag = R) BT = stack.top();退栈stack.pop();BT-b

15、iTree;printf(%c ,BT-biTree-data);遍历右子树if(!stack.empty()BT = stack.top();访问过右子树BT-tag = R;p = BT-biTree;p = p-rchild;/while层次遍历void LevelOrder(BiTree T)BiTree p = T;队列queuevBiTree queue;根节点入队queue.push(p);队列不空循环while(!queue.empty()对头元素出队p = queue.front();访问p指向的结点printf(%c ,p-data);退出队列queue.pop();左子树不空，将左子树入队 if(p-lchild != NULL) queue.push(p-lchild);右子树不空，将右子树入队 if(p-rchild != NULL) queue.push(p-rchild);int main()BiTree T;CreateBiTree(T); printf(先序遍历：n); PreOrder(T);printf(n);printf(”先序