c语言基本概念讲解.doc

二叉树 二叉树的定义 typedef char ElementType; typedef struct BiTreeNode { ElementType data; struct BiTreeNode* lchild; struct BiTreeNode* rchild; }BiTreeNode, *BiTree; 2、 二叉树的建立和销毁 (1)利用先序序列递归建立二叉树 //递归的建立一棵二叉树 //输入为二叉树的先序序列 void createBiTree(BiTree T) { char data; data = getchar(); if(data == #) { T = NULL; } else { T = new BiTreeNode; T-data = data; createBiTree(T-lchild); createBiTree(T-rchild); } } (2)利用广义表建立二叉树 //通过广义表建立二叉树 void createBiTreeWithGenList(BiTree T) { stackBiTree s;//存放待输入孩子的结点 BiTree p = NULL;//用于生成新的结点 int k = 0;//记录期待的结点, k==1表示期待左孩子结点，k==2期待右孩子结点 char ch = getchar(); //处理根结点 if(ch!=#) { p = new BiTreeNode; p-data = ch; p-lchild = NULL; p-rchild = NULL; T = p;//根结点 } while((ch=getchar())!=#) { switch(ch) { case (: s.push(p);//上一个生成的结点，即p入栈，p有孩子 k = 1; //下一个插入的应为左孩子结点 break; case ,: k = 2; //下一个插入的应为右孩子结点 break; case ): s.pop();//结点完成孩子的输入，出栈 break; default: p = new BiTreeNode; p-data = ch; p-lchild = NULL; p-rchild = NULL; if(k==1) s.top()-lchild = p; else s.top()-rchild = p; } } } (3)输出二叉树的广义表表示 //以广义表的方式输出二叉树 void printBiTreeWithGenList(const BiTreeT) { if(T) { coutT-data; if(T-lchild ||T-rchild)//左右子树不全空 { cout(; printBiTreeWithGenList(T-lchild);//递归输出左子树 ，可能为空 if(T-rchild) { cout,; printBiTreeWithGenList(T-rchild); } cout); } } } (4)二叉树的销毁 //递归销毁一棵二叉树 void destroyBiTree(BiTree T) { if(T) { destroyBiTree(T-lchild); destroyBiTree(T-rchild); delete T; T = NULL; } } 3 、二叉树的递归遍历 先序递归遍历 //递归先序遍历二叉树 void preOrderTraverse(const BiTree T) { if(T) { coutT-data ;//输出根节点值 preOrderTraverse(T-lchild);//遍历左子树 preOrderTraverse(T-rchild);//遍历右子树 } } 中序递归遍历 //递归中序遍历二叉树 void inOrderTraverse(const BiTree T) { if(T) { inOrderTraverse(T-lchild);//遍历左子树 coutT-data ;//输出根节点值 inOrderTraverse(T-rchild);//遍历右子树 } } 后序递归遍历 //递归后序遍历二叉树 void postOrderTraverse(co