目录
1.遍历的算法实现
1.先序遍历
代码示例：
2.中序遍历
代码示例：
3.后序遍历
代码示例：
4.遍历算法的分析
2.遍历二叉树的非递归算法
1.中序遍历非递归算法
代码示例：
3.二叉树的层次遍历
代码示例：
4.二叉树遍历算法的应用
1.二叉树的建立
代码示例：
2.复制二叉树
代码示例：
3.计算二叉树深度
代码示例：
4.计算二叉树结点总数
代码示例：
5.计算二叉树叶子结点数
代码示例：
5.线索二叉树
1.线索二叉树的结构
代码示例：
2.先序线索二叉树
3.中序线索二叉树
4.后序线索二叉树
5.练习
6.树和森林
1.树的存储结构
1.双亲表示法
2.孩子链表
3.孩子兄弟表示法
2.树和二叉树的转换
3.将二叉树转换为树
7.树和森林的遍历
1.遍历的算法实现
1.先序遍历
代码示例：
int preordertraverse(bitree t)
{if(t == NULL) return 0;else{printf("%d\t",t -> data);preordertraverse(t -> lchild);preordertraverse(t -> rchild);}
}void pre(bitree t)
{if(t != NULL){printf("%d\t",t -> data);pre(t -> lchild);pre(t -> rchild);}
}2.中序遍历
代码示例：
int inordertraverse(bitree t)
{if(t == NULL) return 0;else{inordertraverse(t -> lchild);printf("&d\t",t -> data);inordertraverse(t -> rchild);}
}3.后序遍历
代码示例：
int postordertraverse(bitree t)
{if(t == NULL) return 0;else{postordertraverse(t -> lchild);postordertraverse(t -> rchild);printf("%d\t",t -> data);}
}4.遍历算法的分析
2.遍历二叉树的非递归算法
1.中序遍历非递归算法
代码示例：
int inordertraverse2(bitree t)
{bitree p,q;initstack(s);p = t;while(p || !stackempty(s)){if(p != NULL){push(s,p);p = p -> lchild;}else{pop(s,q);//使栈顶元素弹出，并且将栈顶元素的地址赋给qprintf("%c",q -> data),p = q -> rchild;}return 1;}
}3.二叉树的层次遍历
代码示例：
typedef struct{btnode data[100];int front,rear;
}sqqueue;void levelorder(btnode *b)
{btnode *p;sqqueue *qu;initqueue(qu);enqueue(qu,b);while(!queueempty(qu)){dequeue(qu,p);printf("%c",p -> data);if(p -> lchild != NULL) enqueue(qu,p -> lchild);if(p -> rchild != NULL) enqueue(qu,p -> rchild);}
}4.二叉树遍历算法的应用
1.二叉树的建立
代码示例：
int createbitree(bitree &t)
{cin >> ch;if(ch == '#') t = NULL;else{t = new bitnode;t -> data = ch;createbitree(t -> lchild);createbitree(t -> rchild);}return 1;
}2.复制二叉树
代码示例：
int copy(bitree t,bitree &newt)
{if(t == NULL){newt = NULL;return 0;}else{newt = new bitnode;newt -> data = t -> data;copy(t -> lchild,newt -> lchild);copy(t -> rchild,newt -> lchild);}
}3.计算二叉树深度
代码示例：
int depth(bitree t)
{if(t == NULL) return 0;else{int m,n;m = depth(t -> lchild);n = depth(t -> rchild);if(m > n) return m + 1;else return n + 1;}
}4.计算二叉树结点总数
代码示例：
int nodecount(bitree t)
{if(t == NULL) return 0;else{return nodecount(t -> lchild) + nodecount(t -> rchild) + 1;}
}5.计算二叉树叶子结点数
代码示例：
int leafcount(bitree t)
{if(t == NULL) return 0;if(t -> lchild == NULL && t -> rchild == NULL) return 1;else return leafcount(t -> lchild) + leafcount(t -> rchild);
}5.线索二叉树
1.线索二叉树的结构
代码示例：
typedef struct bithrnode{int data;int ltag,rtag;struct bithrnode *lchild,*rchild;
}bithrnode,*bithrtree;2.先序线索二叉树
3.中序线索二叉树
4.后序线索二叉树
5.练习
6.树和森林
1.树的存储结构
1.双亲表示法
2.孩子链表
3.孩子兄弟表示法
2.树和二叉树的转换
3.将二叉树转换为树
7.树和森林的遍历
8.总的代码
typedef struct binode{int data;struct binode *lchild,*rchild;
}binode,*bitree;int preordertraverse(bitree t)
{if(t == NULL) return 0;else{printf("%d\t",t -> data);preordertraverse(t -> lchild);preordertraverse(t -> rchild);}
}void pre(bitree t)
{if(t != NULL){printf("%d\t",t -> data);pre(t -> lchild);pre(t -> rchild);}
}int inordertraverse(bitree t)
{if(t == NULL) return 0;else{inordertraverse(t -> lchild);printf("&d\t",t -> data);inordertraverse(t -> rchild);}
}int postordertraverse(bitree t)
{if(t == NULL) return 0;else{postordertraverse(t -> lchild);postordertraverse(t -> rchild);printf("%d\t",t -> data);}
}int inordertraverse2(bitree t)
{bitree p,q;initstack(s);p = t;while(p || !stackempty(s)){if(p != NULL){push(s,p);p = p -> lchild;}else{pop(s,q);//使栈顶元素弹出，并且将栈顶元素的地址赋给qprintf("%c",q -> data),p = q -> rchild;}return 1;}
}typedef struct{btnode data[100];int front,rear;
}sqqueue;void levelorder(btnode *b)
{btnode *p;sqqueue *qu;initqueue(qu);enqueue(qu,b);while(!queueempty(qu)){dequeue(qu,p);printf("%c",p -> data);if(p -> lchild != NULL) enqueue(qu,p -> lchild);if(p -> rchild != NULL) enqueue(qu,p -> rchild);}
}int createbitree(bitree &t)
{cin >> ch;if(ch == '#') t = NULL;else{t = new bitnode;t -> data = ch;createbitree(t -> lchild);createbitree(t -> rchild);}return 1;
}int copy(bitree t,bitree &newt)
{if(t == NULL){newt = NULL;return 0;}else{newt = new bitnode;newt -> data = t -> data;copy(t -> lchild,newt -> lchild);copy(t -> rchild,newt -> lchild);}
}int depth(bitree t)
{if(t == NULL) return 0;else{int m,n;m = depth(t -> lchild);n = depth(t -> rchild);if(m > n) return m + 1;else return n + 1;}
}int nodecount(bitree t)
{if(t == NULL) return 0;else{return nodecount(t -> lchild) + nodecount(t -> rchild) + 1;}
}int leafcount(bitree t)
{if(t == NULL) return 0;if(t -> lchild == NULL && t -> rchild == NULL) return 1;else return leafcount(t -> lchild) + leafcount(t -> rchild);
}typedef struct bithrnode{int data;int ltag,rtag;struct bithrnode *lchild,*rchild;
}bithrnode,*bithrtree;
