[算法与数据结构] - No.7 二叉树建立及其前序、中序、后序遍历

本文主要是介绍[算法与数据结构] - No.7 二叉树建立及其前序、中序、后序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

什么叫树？

树的定义    

树是由 n (n >= 0) 个结点的有限集合。如果 n = 0，称为空树；

如果 n = 1，则有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；

如果 n > 1，除根以外的其它结点划分为 m (m >0) 个互不相交的有限集 T1, T2 ,…, Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。

树的其他概念：

结点：一个数据元素及指向其子树的分支。
结点的度：结点拥有的子树个数。
叶结点：度为零的结点。
子女：结点子树的根。
兄弟：同一结点子女。
祖先：根到该结点路径上的所有结点。
子孙：某结点为根的子树上的任意结点。
结点层次：从根开始，根为第一层，根的子女为第二层，以此类推。
树的深度（高度）：树中结点的最大层次数。
有序树：树中结点的子树由左向右有序。
森林：m(m >= 0)棵互不相交的树。

定义树的数据结构：

typedef struct TreeNode
{char data;struct TreeNode *lchild, *rchild;
}TreeNode,*Tree;

这里解释一下这个数据结构，我们定义了名为TreeNode的结构体，并且使用typedef关键字，这样我们在后续的使用中直接使用TreeNode 和Tree作为类型来定义

例：

TreeNode p = (TreeNode)malloc(sizeof(TreeNode)) 声明一个TreeNode结构

Tree p = (Tree)malloc(sizeof(TreeNode)) 声明一个TreeNode的指针

前序建立树：

void createTree(Tree *T)
{char mychar;cin>>mychar;if(mychar!='#'){*T = (Tree)malloc(sizeof(TreeNode));(*T)->data = mychar;createTree(&(*T)->lchild);createTree(&(*T)->rchild);}else{*T = NULL;}
}

这里不容易理解的是Tree *T；由于我们的Tree已经是TreeNode的指针了，这里为什么还是用了Tree的指针呢？也就是说，我们在这里使用了二级指针。为什么要这样呢？因为我们这里的函数是无返回值的，并且，我们在函数中，改变了Tree 变量的指向，即我们使这个指针指向了其他的地方。还记得我们在学习swap函数的时候么？我们如果想要交换a,b两个值，应该传入a,b指针（一级指针），使得他们指向的地址存储的值为a,b。这里，我们在函数中，不是改变了指针的值，而是改变了指针的指向，所以需要使用二级指针。（如果你有兴趣可以尝试使用Tree T，这样不会得到任何结果，同时你的造成了内存泄漏）

树的遍历（递归）：

树的前序，中序，后序都特别好理解。所谓前序，中序，后序其实就是我们决定什么时候访问本节点，什么时候访问左右子的问题。

如果我们在访问一棵树的时候，首先访问根节点，然后再访问左右子，那么就是前序。

如果我们在访问一棵树的时候，首先访问左子树，在左子树全部访问完毕后，访问根节点，然后访问右子树，那么就是中序

同理，后序就是访问左右子完毕以后再访问根节点

代码如下：

void preOrderTraverse(Tree T)
{if(T==NULL){return;}cout<<T->data;preOrderTraverse(T->lchild);preOrderTraverse(T->rchild);
}
void midOrderTraverse(Tree T)
{if(T==NULL){return;}midOrderTraverse(T->lchild);cout<<T->data;midOrderTraverse(T->rchild);
}
void postOrderTraverse(Tree T)
{if(T==NULL){return;}postOrderTraverse(T->lchild);postOrderTraverse(T->rchild);cout<<T->data;
}

注意，这里我们只访问节点，所以可以使用一级指针
非递归遍历：非递归遍历，其实就是使用栈来保存我们还没有访问到的一些节点，但是思路和上边是一样的

前序：由于我们上来就把当前节点访问了，所以我们在栈中依次保存右子，左子。然后取出栈顶元素，迭代该过程

中序，由于我们先访问左子树，所以我们在栈中依次保存右子，父节点。然后取出栈顶元素，迭代该过程

后序：后序相对前两种复杂了一些，因为最后才会访问父节点。那么我们就维护一个last变量，记录上一次访问的指针

1. 获取栈定元素

1. 当前节点左右都是空，或者上次访问的是右子或者是上次访问的是左子但是右子是空，遍历该节点，弹出栈定

2. 否则将右子和左子依次压入

代码：

void preOrderTraverse(Tree T)
{stack<Tree>mystack;while(!mystack.empty()){mystack.pop();}mystack.push(T);TreeNode *p;while(!mystack.empty()){p = mystack.top();cout<<p->data<<" ";mystack.pop();if(p->rchild!=NULL)mystack.push(p->rchild);if(p->lchild!=NULL)mystack.push(p->lchild);}
}void midOrderTraverse(Tree T)
{stack<Tree>mystack;while(!mystack.empty()){mystack.pop();}mystack.push(T);TreeNode *p;while(!mystack.empty()){while(mystack.top()!=NULL){p = mystack.top();mystack.push(p->lchild);}mystack.pop();if(!mystack.empty()){p = mystack.top();cout<<p->data<<" ";mystack.pop();mystack.push(p->rchild);}}
}void postOrderTraverse(Tree T)
{stack<Tree>mystack;while(!mystack.empty()){mystack.pop();}mystack.push(T);TreeNode *last = T;TreeNode *p;while(!mystack.empty()){p = mystack.top();if((p->lchild == NULL && p->rchild == NULL) || last == p->rchild || (p->rchild == NULL && last == p->lchild)){cout << p->data<<" ";last = p;mystack.pop();}else{if(p->rchild!=NULL){mystack.push(p->rchild);}if(p->lchild!=NULL){mystack.push(p->lchild);}}}
}

P.S. 文章不妥之处还望指正

这篇关于[算法与数据结构] - No.7 二叉树建立及其前序、中序、后序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---