二叉树、二叉排序树及其遍历

文章目录

• • 先序创建二叉树
  • 二叉树的中序、后须、层次遍历
  • 二叉排序树的建立

先序创建二叉树

/*二叉链表存储结构*/
typedef struct BiTNode {TElemType data;struct BiTNode* lchid, * rchid;
}BiTNode,*BiTree;/*先序创建二叉树*/
BiTree CreateBiTree(){BiTree T;//根节点TElemType item;cin >> item;if (item == '#') { //叶节点数据标志T = NULL;  //若某一节点为叶子节点，则其左右子树均为NULL，0表示建空树}else {T = (BiTree)malloc(sizeof(BiTNode));T->data = item;T->lchid = CreateBiTree();T->rchid = CreateBiTree();}return T;
}

二叉树的中序、后须、层次遍历

/*非递归中序遍历*/
void InOrderTraverse(BiTree t)
{SqStack S;InitStack(S);BiTree p = t;while (p||!StackEmpty(S)){if (p) {Push(S, (SElemType)p);p = p->lchid;}else {Pop(S, (SElemType&)p);cout << p->data;p = p->rchid;}}}
/*递归后序遍历*/
void PostOrder(BiTree t) {if (t) {PostOrder(t->lchid);PostOrder(t->rchid);cout << t->data;}
}/*递归层序遍历*/
void LevelOrder(BiTree t)
{if (t){LinkQueue  Q;InitQueue(Q); //设置一空队列        EnQueue(Q, (int)t); //根结点入队while (!QueueEmpty(Q)) //当队非空时重复执行下列操作{DeQueue(Q, (int&)t);// Visit(p->data); //出队访问cout << t->data;if (t->lchid) {EnQueue(Q, (QElemType)t->lchid);}if (t->rchid) {EnQueue(Q, (QElemType)t->rchid);}}DestoryQueue(Q);}
}

二叉排序树的建立

/*二叉链表存储结构*/
typedef struct BiTNode {int data;struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;int SearchBST(BiTree T, int key, BiTree f, BiTree& p)
//查找成功，参数p指向查找到的结点，f指向它的双亲；否则p指向key应插入的父结点或指向空（当T为空时）
{if (!T){p = f;return 0;}else if (key == T->data){p = T;return 1;}else if (key < T->data)return (SearchBST(T->lchild, key, T, p));elsereturn (SearchBST(T->rchild, key, T, p));
}int InsertBST(BiTree& T, int e)
//在二叉排序树中插入值为elem的元素，T指向二叉排序树根结点
{BiTree p = NULL, f = NULL;if (!SearchBST(T, e, f, p)) // 如果查找不成功{BiTree s = (BiTree)malloc(sizeof(BiTNode));s->data = e;s->lchild = s->rchild = NULL;if (!p) // 若二叉树为空被插结点作为树的根结点T = s; else if (e< p->data) //被插结点插入到p的左子树中p->lchild = s;else  //被插结点插入到p的右子树中p->rchild = s; return 1;}else // 查找成功,不插return 0; 
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！